A PAC-Bayesian bound for Lifelong Learning

Introduction

Today, many problems can be solved equally well or better by machine learning algorithms as by humans. However, these algorithms typically require large amount of training data to achieve acceptable results, whereas humans are able to learn new concepts from just a few examples. Presumably this difference comes from the fact that most machine learning systems are trained from scratch for each task at hand, whereas humans exploit context and knowledge they acquired previously while solving other tasks.

This observation motivates research on transfer learning: how can information from previously learned tasks be used for solving new tasks? Several scenarios of how this question can be formalized have been identified. Here, we discuss some that are most relevant in the context of supervised learning. As general setup, one assumes that one or more learning tasks have been observed, typically in form of labeled training sets. The methods then differ in how this information is meant to be used. In the multitask setting (Caruana, 1997), the goal is simply to perform well on all of the tasks. In domain adaptation (Bridle & Cox, 1990), the goal is to perform well on a new task for which only unlabeled or very few labeled data samples are observed. Finally, in lifelong learning or learning to learn (Thrun & Mitchell, 1995), the goal of the learner is to perform well on future tasks, for which so far no data has been observed. In this work we focus on the third setting.

For lifelong learning to make sense, one must assume a relation between the observed tasks and the future tasks. To formalize this, Baxter (2000) introduced the notion of a task environment as a set of possible tasks that might need to be solved at some time. The observed tasks are sampled randomly from the environment according to an unknown task distribution. In this setting, Baxter also provided the first theoretical guarantees by proving generalization bounds in the framework of VC theory (Vapnik, 1998). After this work, however, progress on the theoretical understanding of lifelong machine learning slowed down. Many algorithms for transfer learning were developed and found empirically to work well in many cases. However, except for a few exception, such as (Maurer, 2009; Maurer et al., 2013), their theoretical justifications are so far not well understood.

In this work, we aim at making progress on the theoretical justifications of lifelong learning. In Section 2 we prove a general PAC-Bayesian generalization bound for lifelong learning that allows quantifying the relation between the expected loss on a future learning task to the average loss on the observed tasks. In contrast to Baxter’s results, our bound has the advantage that its value depends on the representation of the data and on the learning algorithm used to solve the tasks. This makes it possible to interpret the bound as a quality measure of the transferred information. Therefore, by optimizing the measure we obtain principled algorithms for lifelong learning.

In Sections 2.1 and 2.2 we demonstrate this process in two cases: assuming that the solutions to all tasks can be represented by a single parameter vector plus small task-specific perturbation (Evgeniou & Pontil, 2004), we obtain an algorithm that resembles previously proposed methods for regularizing the weight vectors of future tasks using linear combinations of weight vectors of previous tasks, such as (Yang et al., 2007; Aytar & Zisserman, 2011).

An alternative assumption is that the solution vectors to tasks can differ significantly, but that they all lie in a common feature subspace of low dimension. In this setting, our bound provides an algorithm in which the observed tasks are used to identify the most promising subspace of features, such that learning for future tasks needs to take place only within the reduced feature space. This procedure is related to existing methods for representation and dictionary learning, e.g. (Argyriou et al., 2008; Kumar & Daumé III, 2012), which have also successfully been applied in the lifelong learning setting (Ruvolo & Eaton, 2013). In a case of linear regression, Maurer (2009) used this assumption to prove a generalization bound in the PAC framework, by using the concept of environment of tasks from Baxter (2000) and Rademacher complexity. Similar results were obtained in (Maurer et al., 2013) in the case of sparsity constraints.

The PAC-Bayesian framework.

For the convenience of readers who are not familiar with the PAC-Bayesian framework, we introduce the most relevant concepts from the literature here. For more details, see (Langford, 2005; Seeger, 2003; Catoni, 2007).

PAC-Bayesian theory studies the properties of randomized predictors, called Gibbs predictors. Formally, let $\mathcal{X}$ be an input set, $\mathcal{Y}$ an output set and $H\subset\{h:\mathcal{X}\to\mathcal{Y}\}$ a set of prediction functions (hypotheses). For any probability distribution $P$ over $H$, the Gibbs predictor associated with $P$ is the stochastic predictor that for any $x\in\mathcal{X}$ randomly samples a hypothesis $h\sim P$ and then returns $h(x)$.

where $P$ is a reference or prior distribution over $H$ that must be chosen before observing the samples $S$, and $\operatorname{\operatorname{\textsl{KL}}}(Q||P)$ is the Kullback-Leibler divergence, i.e. a measure how different $Q$ is from $P$. As such, the bound resembled the typical trade-off in regularized risk minimization between the training loss and a regularizer (Vapnik, 1998).

Inequality (1) is uniform with respect to $Q$, so it holds regardless of which $Q$ we choose. In particular, we can choose it after seeing $S$, and for this reason $Q$ is typically referred to as posterior distribution in this context.

Choosing $Q$ such that it minimizes the right hand side of the bound we obtain a Gibbs predictor that can be expected to be a good choice for the learning task at hand, since its expected loss is controlled by a hopefully small quantity. While the inequality (1) holds regardless the agreement between the data distribution and the prior distribution $P$, the value of the right hand side of the bound strongly depends on the choice of $P$. Therefore, one would prefer a prior that allows learning a posterior that is at the same time close to the prior ($KL(Q||P)$ is small) and shows good performance on the training set ($\widehat{\operatorname{er}}(Q)$ is small).

PAC-Bayesian Lifelong Learning

The goal of the agent is to use the information contained in the observed tasks to identify prior knowledge that will cause as good as possible performance on new (so far unobserved) tasks from the same environment. This setting is strictly harder than multi-task learning or domain adaptation, since no data for the future tasks to be solved is available at the time the agent makes its decision. In particular, previously developed techniques for learning priors are not directly applicable: first, note that we cannot use ordinary generalization bounds, such as (1), to identify optimal priors, since they only hold uniformly in $Q$ if the prior is chosen independently from the training set. Catoni (2007) derived an expression for the overall ”best” prior, i.e. the distribution resulting in the smallest possible bound value. However, it is generally of a non-parametric form and uncomputable without full information about the data distribution. Parrado-Hernández et al. (2012) showed that priors can be learned by splitting the available training data into two parts, one for learning a prior, one for learning the predictor. This, however, requires training data for the task at hand, which is not available in the lifelong setting.

Our first contribution in this work is the insight that one should treat the prior $P$ itself as a random variable. Let $\mathcal{P}$ be an initial distribution over all possible priors, which we call hyperprior in concordance with the Bayesian nomenclature. For learning a prior the agent uses the observed tasks to adjust its original hyperprior into a hyperposterior distribution $\mathcal{Q}$ over the set of priors. This randomized setting allows us to follow a PAC-Bayesian path analogous to classical results. We will obtain a bound that requires a fixed hyperprior $\mathcal{P}$ but that holds uniformly with respect to the hyperposterior $\mathcal{Q}$. The hyperposterior that minimizes the bound will provide us with the most promising distribution from which to obtain priors for future tasks.

Formally, the goal of the agent is to find $\mathcal{Q}$ that minimizes the expected loss $\operatorname{er}(Q_{t})$ of a randomly sampled new task $t$ with training set $S_{t}$ and prior $P$ sampled from $\mathcal{Q}$. We write

where $Q_{t}(S_{t},P)$ is the posterior obtained by training the learning algorithm with prior $P$ and training sample $S_{t}$. We call this quantity the transfer risk.

We cannot compute $\operatorname{er}(\mathcal{Q})$ because the distributions over the tasks and the tasks’ data are both unknown. However, we can approximate it by its empirical counterpart, based on $n$ observed tasks

Our main result is a theorem that bounds the difference between the two quantities defined above.

For any $\delta>0$ the following inequality holds with probability at least $1-\delta$ (over the training samples $\{S_{1},\dots,S_{n}\}$) for all hyperposterior distributions $\mathcal{Q}$

where $(\mathcal{Q},Q^{n})=\mathcal{Q}\times\prod_{i=1}^{n}Q_{i}$ denotes the distribution in which we first sample $P$ according to $\mathcal{Q}$ and then use it and the data $S_{i}$ to produce a posterior $Q_{i}$ for each task $t_{i}$. $(\mathcal{P},P^{n})=\mathcal{P}\times\prod_{i=1}^{n}P$ denotes the distribution in which we sample $P$ according to $\mathcal{P}$ and use it as a posterior for all tasks. $\bar{m}=\left(\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{i}}\right)^{-1}$ is the harmonic mean of the sample sizes.

Proof To prove Theorem 1 we introduce an intermediate quantity that can be seen as an expected multi-task risk

First we will bound the uncertainty on the task environment level by bounding the difference between transfer error, $\operatorname{er}(\mathcal{Q})$, and expected multi-task error, $\widetilde{\operatorname{er}}(\mathcal{Q})$. Then we will bound the uncertainty within observed tasks by bounding the difference between expected multi-task error, $\widetilde{\operatorname{er}}(\mathcal{Q})$, and its empirical approximation, $\widehat{\operatorname{er}}(\mathcal{Q})$. Our main tool in both cases will be the following lemma.

Let $f$ be a random variable taking values in $A$ and let $X_{1},\dots,X_{l}$ be $l$ independent random variables with each $X_{k}$ distributed according to $\mu_{k}$ over the set $A_{k}$. For functions $g_{k}:A\times A_{k}\rightarrow[a_{k},b_{k}],\;k=1\dots l$, let $\xi_{k}(f)=\operatorname*{\operatorname{\mathbf{E}}}_{X_{k}\sim\mu_{k}}g_{k}(f,X_{k})$ for any fixed value of $f$. Then for any fixed distribution $\pi$ on $A$ and any $\lambda,\delta>0$ the following inequality holds with probability at least $1-\delta$ (over sampling $X_{1},\dots,X_{l}$) for all distributions $\rho$ over $A$

For the proof of this lemma, see the Appendix A.

In order to bound the difference between $\operatorname{er}(\mathcal{Q})$ and $\widetilde{\operatorname{er}}(\mathcal{Q})$ we treat each task $t$ with the corresponding training sample $S_{t}$ as a random variable and apply Lemma 2. Formally, we set $\rho=\mathcal{Q}$, $\pi=\mathcal{P}$, $X_{k}=(t_{k},S_{k})$, $l=n$, $f=P$ and $g_{k}(f,X_{k})=\frac{1}{n}\underset{h\sim Q_{k}}{\mathbf{E}}\underset{(x,y)\sim D_{k}}{\mathbf{E}}l(h(x),y)$ and apply Lemma 2 with $\lambda=\sqrt{n}$. Since $a_{k}=0$ and $b_{k}=\frac{1}{n}$ we obtain with probability at least $1-\delta/2$ that for all $\mathcal{Q}$

Now (4) follows by a union bound from (7) and (8). To get a better understanding of Theorem 1, we rewrite (4) in the following way:

We see that the bound contains two types of complexity terms that correspond to two levels of our model: $\operatorname{\operatorname{\textsl{KL}}}(\mathcal{Q}\|\mathcal{P})$ belongs to the level of task environment in general, while each $\operatorname{\operatorname{\textsl{KL}}}(Q_{i}(S_{i},P)\|P)$ corresponds specifically to the $i$-th task.

To better understand their roles, we look at the following limit cases: when the agent has access to sufficiently many tasks ($n\to\infty$) but tasks come with a finite amount of data ($\bar{m}$ is finite), the first complexity term converges to as $1/\sqrt{n}$. The second complexity term converges to an average $\operatorname{\operatorname{\textsl{KL}}}$-divergence over tasks and may therefore remain non-zero. This means that observing many task gives the agent full knowledge about the task environment, but it cannot overcome the uncertainty within each task. In the opposite case, if the agent observes unlimited data for each tasks, but only for a finite number of tasks ($\bar{m}\to\infty$, $n$ is finite), the second complexity term converges to as $1/\sqrt{\bar{m}}$, while the first one does not, so there is still uncertainty on the task environment level. Only when both comes together, sufficiently many tasks and sufficient amounts of data per task, it is guaranteed that the empirical multi-task risk $\widehat{\operatorname{er}}(\mathcal{Q})$ converges to the transfer risk $\operatorname{er}(\mathcal{Q})$.

A second important aspect of Theorem 1 is that the bound (4) consists only of observable quantities. Therefore, we can treat it as a quality measure for hyperposteriors $\mathcal{Q}$. By minimizing it, we obtain a hyperposterior distribution over priors that is adjusted to the particular environment of learning tasks. Since the bound holds uniformly with respect to $\mathcal{Q}$, the guarantees of Theorem 1 also hold for the resulting learned hyperposterior, so we can expect priors sampled according to the learned hyperposterior to work well even for future tasks.

In the following sections, we discuss two instantiations of this procedure and show how they relate to previous work on transfer learning.

where $w_{pr}$ is some function of weight vectors of previously observed tasks, e.g. just their average, $w_{pr}=\frac{1}{n}\sum_{i=1}^{n}w_{i}$.

Theorem 1 allows us to learn an “optimal” $w_{pr}$ from the data, instead of fixing the rule for computing it. For this, we choose $P=\mathcal{N}(w_{P},I_{d})$ and $Q=\mathcal{N}(w_{Q},I_{d})$, i.e. unit variance normal distributions with means $w_{P}$ and $w_{Q}$, respectively. The mean $w_{P}$ is a random variable distributed first according to the hyperprior distribution, $\mathcal{P}$, which we set as $\mathcal{N}(0,\sigma I_{d})$ and later according to the hyperposterior, $\mathcal{Q}$, which we model as $\mathcal{Q}=\mathcal{N}(w_{\mathcal{Q}},I_{d})$. The task of the learning consists of identifying the best $w_{\mathcal{Q}}$.

As underlying learning algorithm we use Equation (10) with regularizer centered at a prior vector. For any $w_{P}$ and training set $S=\{(x_{i},y_{i})_{i=1,\dots,m}\}$ the posterior, $Q(S,P)=\mathcal{N}(w_{Q},I_{d})$, is given by

where $X$ is the matrix with columns $x_{1},\dots,x_{m}$, $Y$ is a column of labels $(y_{1},\dots,y_{m})^{\top}$, $A=\left(I_{d}+\frac{C}{m}XX^{\top}\right)^{-1}$ and $b=\frac{C}{m}AXY$.

Computing the complexity terms from (9) we obtain

We insert Equations (13) into the inequality (9) and obtain

where \Phi(z)=\frac{1}{2}\big{(}1-\operatorname{erf}(\frac{z}{\sqrt{2}})\big{)} and $\operatorname{erf}(z)=\frac{2}{\sqrt{\pi}}\int_{0}^{z}e^{-t^{2}}dt$ is the Gauss error function.

For a practical algorithm, one typically would prefer a bound on the loss of a deterministic classifier rather than of the stochastic Gibbs classifier. For $0/1$-loss Theorem 1 provides this, since the Gibbs error is at most twice smaller than the expected error of the classifier defined by $A_{i}w_{\mathcal{Q}}+b_{i}$ (McAllester, 2003; Laviolette & Marchand, 2007). Inserting (15) in (14) and multiplying the left hand side by $\frac{1}{2}$ we obtain the following inequality:

Minimizing the right hand side of (16) or (17) with respect to $w_{\mathcal{Q}}$, we obtain a data-dependent hyperposterior that induces prior distributions that are adjusted optimally (in the sense of the bound) to the task environment.

2 Representation Transfer

A second assumption commonly made in multitask or lifelong learning is that the weight vectors for all tasks lie in low-dimensional subspace. Theorem 1 also allows us to learn such a subspace in a principled way.

where $C_{1}={}_{0}F_{1}(\frac{1}{2}d,\frac{1}{4}M^{\top}M)$. The only free parameter is $M\in V_{d,k}$, i.e. a $d\times k$ matrix with $M^{\top}M=I_{k}$ that represents the ”most promising subspace”. Equation (19) can be interpreted as an analog of the Gaussian distribution on $V_{d,k}$, with mode $M$ and unit variance. In the special case of $k=1$, it reduces to the better known Von Mises distribution on the unit circle (Downs, 1972).

As in the previous section we use Gaussian distributions for prior and posterior, but defined only within the subspaces sampled from $\mathcal{P}$ or $\mathcal{Q}$. For the prior, $P$, we choose a Gaussian with zero mean and variance $\sigma I_{k}$. The posterior, $Q$, is a shifted Gaussian with variance $\sigma I_{k}$ and mean $w_{Q}$ in the same subspace. As in the previous section we use ridge regression as learning algorithm, but again only within the subspace determined by the prior,

where $B$ is the matrix representing the subspace, such that $B^{\top}x$ is the projected representation of the training data in this subspace.

where $w_{i}(B)=\frac{C}{m_{i}}\left(I_{k}+\frac{C}{m_{i}}B^{\top}X_{i}X_{i}^{\top}B\right)^{-1}\!\!B^{\top}X_{i}Y_{i}$. We see that a representation, $M$, can be considered promising for future tasks, if itself as well as the subspaces close to it allow classification with small loss and small weight vector norm (i.e. large margin) for all observed tasks.

Experiments

In this section, we demonstrate how learning priors distributions by minimizing the bounds (16), (17) and (2.2) can improve prediction performance in real prediction tasks. To position our results with respect to previous work on parameter and representation transfer, we compare to adaptive ridge regression (ARR), i.e. Equation (10) the prior $w_{pr}$ set to the average of the weight vectors from the observed tasks, and with the ELLA algorithm (Ruvolo & Eaton, 2013) that learns a subspace representation using structured sparsity constraints, also with squared loss. We also report results for ordinary ridge regression without any knowledge transfer.

We perform experiments on three public datasets:

Land Mine Detection (Xue et al., 2007). This dataset consists of 14820 data points. For each data point there are 9 features extracted from radar images and a binary label or $1$ corresponding to landmine or clutter. We also add a bias term, resulting in $d=10$ features. Data points are collected from 29 geographical regions and we treat each region as a binary classification task.

London School Data. This is a regression dataset, containing exam scores of 15362 students from 139 schools. Each student is described by 4 school-specific, 3 student-specific features and a year of examination. We use the same procedure as in (Argyriou et al., 2008; Kumar & Daumé III, 2012; Ruvolo & Eaton, 2013) to encode them in a set of binary features. We also add a bias term, so the final data dimensionality is $d=28$. Each school constitutes a task.

Animals with Attributes Dataset (Lampert et al., 2013). This dataset contains 30475 images from 50 classes. Each image comes with a 2000-dimensional feature vector, that we reduced to 100 dimensions using PCA. We $l_{2}$-normalize the resulting feature vectors and add a bias term. We select the largest class, collie, and form 49 binary classification tasks, each of them is a classification of collie versus one of the remaining classes. For each task we use $2\%$ of the data (approximately 20 images) available for collie class and the same amount of images from the another task, such that data between different tasks does not overlap.

We first perform experiments on prior learning in the setup of parameter transfer, as described in Section 2.1, calling the resulting algorithm Prior Learning with Gaussian hyperprior (PL-G). For the classification tasks (Landmine and Animals), we optimize the bound (16). To do so we replace $\Phi$ by its convex relaxation, $\Phi_{\textit{cvx}}(z)=\frac{1}{2}-\frac{z}{\sqrt{2\pi}}$, if $z\leq 0$ and $\Phi_{\textit{cvx}}(z)=\Phi(z)$ otherwise, and use the conjugate gradient method for finding the minimum.

For the regression tasks (Schools) we first divide labels (examination scores) by their maximum value. This allows us to assume that the squared loss will not exceed $1$. We optimize (17), and due to the squared loss, the problem has a closed form solution:

To make results comparable with the baseline algorithms, we report the squared error multiplied by the squared value of the maximum examination score.

2 Representation Transfer

In a second set of experiments, we implement the idea of representation transfer from Section 2.2, calling the algorithm Prior Learning with Langevin hyperprior (PL-L).

As in the case of parameter transfer, we use $0/1$ loss to measure the quality in classification tasks. For the regression task we apply the same scaling procedure as discussed in Section 3.1 and use truncated squared loss. Both of these loss functions can be upper-bounded by the standard squared loss, which we do to obtain tractable expressions for the right hand side of the Inequality (2.2). To be able to optimize the expression (2.2) numerically, we approximate it by replacing all expectations over $\mathcal{Q}$ by their values at its mode, $M$. Furthermore, we replace the error of any Gibbs predictor by the error of the deterministic predictor defined by the mode of the posterior distribution, $w_{i}(M)$. The result is a quadratic optimization problem over the Stiefel manifold, which we solve using gradient descent with curvilinear search (Wen & Yin, 2013).

3 Evaluation procedure

To get reliable estimates of the transfer risk, we repeat the following experimental procedure 100 times for each dataset and calculate the mean prediction errors and standard errors of the mean.

In each experiment, we set aside a subset of tasks as unobserved (9 in Landmines, 39 in Schools, 9 in Animals). These are not used during any part of training, but only to evaluate the methods on ”future” tasks. Of the remaining tasks we use different fractions to measure the effect of a different number of observed tasks. The algorithms described in Section 3.1 and 3.2 and ARR have one free parameter, the regularization strength $C\in\{10^{-3},\dots,10^{3}\}$. We choose this using 3-fold cross-validation in the following way. We split the data of each task into three parts: we use the first third of all tasks jointly to learn a prior. To evaluate this prior, we then train individual predictors using the second part of the data, and test their quality on the third part. For the ELLA algorithm, we use the same procedure to set the regularization strength $\mu$, the remaining parameters we leave at their default values. For the baseline, we set the regularization using ordinary 3-fold cross-validation.

4 Results

The results of the experiments on all three datasets are shown in Figure 1. Since classes in Landmine dataset are unbalanced, for this problem we report the value of area under the ROC curve (AUC, bigger value means better prediction). Tasks in the Animals dataset are balanced, so for them we report the standard mean $0/1$ error. Since the dataset was too large for the subspace methods, we only report results for the parameter transfer techniques. For the experiment on Schools dataset we report the mean squared error (MSE, smaller values mean better prediction).

As a first observation, Figure 1 confirms the findings of previous work that better prediction can be achieved by transferring information from related tasks. Overall, it shows that PL-G and PL-L are comparable to the existing, manually designed, techniques. Given sufficiently many tasks, they are able to improve the prediction accuracy over the baseline. As an illustration of the hyperprior concept, we show results for PL-G with two different values for the Gaussian hyperprior variance (Figures 1(a), 1(b), 1(c)). For $\sigma=1$, the adaption pursues in a very conservative way and many tasks are needed to find a reliable hyperposterior. With $\sigma=10$, convergence is faster, and PL-G achieves results comparable with ARR or even slightly better. For practical tasks, the hyperprior should possibly be chosen by model selection.

The results for representation transfer (Figures 1(d) and 1(e)) show that the improvements achieved by PL-L are comparable to the ELLA algorithm. As in the case of parameter transfer, we show results for two different values of the Gaussian prior variance: $\sigma=1$ and $\sigma=10$. While for the Landmine dataset (Figure 1(d)), there is no significant difference in the performance for different values of parameters $k$ and $\sigma$, for the Schools dataset (Figure 1(e)) the choice of these parameters plays a bigger role. We see that the improvements of PL-L with $\sigma=10$ are almost the same as the one achieved by ELLA, while for $\sigma=1$ they are smaller. This might be the effect of too strict hyperparameters that cause the method to be more conservative than necessary. Another possible reason for the difference in accuracy is that ELLA makes additional sparsity assumption, which PL-L does not.

Conclusion

In this work we studied lifelong learning from a theoretical perspective. Our main result is a generalization bound in a PAC-Bayesian framework (Theorem 1). On the one hand, the bound is very general, allowing us to recover two existing principles for transfer learning as special cases: the transfer of classifier parameters, and the transfer of subspaces/representations. On the other hand, the bound consists only of observable quantities, such that it can be used to derive principled algorithms for lifelong learning that achieve results comparable with existing manually designed methods.

A further use of the bound we see is in using it to study the implicit assumptions of possible learning methods. For example, a method obtained by means of a unimodal hyperposterior will require all tasks to be related to each other. In future work, we plan to explore the potential of integrating more realistic assumptions, such as hierarchical or multi-modal hyperposteriors. A second interesting direction will be to relax the condition that tasks are sampled i.i.d. from an environment, e.g. into the direction of learning tasks of continuously improving difficulty (Bengio et al., 2009).

We thank Shai Ben-David, Olivier Catoni and Emilie Morvant for helpful discussions. This work was in parts funded by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 308036.

Appendix A Proof of Lemma 2

In the proof we will make use of Hoeffding’s Lemma:

(Hoeffding, 1963) Let $X$ be a real-valued random variable such that $Pr(X\in[a,b])=1$ and let $\xi=\operatorname*{\operatorname{\mathbf{E}}}\{X\}$. Then

We will also require the following property of the Kullback-Leibler divergence that holds for any $\lambda>0$ and can be proved by convex duality (Seeger, 2003):

We now prove Lemma 2. First, we apply (25) to $g(f)=\sum_{k=1}^{l}\xi_{k}(f)-\sum_{k=1}^{l}g_{k}(f,X_{k})$, obtaining

since for any fixed $f$ the factors are independent. This allows us to apply Hoeffding’s Lemma 3 to each factor:

By taking the expectation over $f\sim\pi$ we obtain

Since $\pi$ is fixed and does not depend on $X_{1},\dots,X_{l}$, we can exchange the order of expectations. By applying Markov’s inequality with respect to expectations over $X_{1},\dots,X_{l}$ we obtain that with probability at least $1-\delta$:

We obtain (2) by combining (30) and (26).

References