Incremental Learning-to-Learn with Statistical Guarantees

INTRODUCTION

Learning-to-learn (LTL) or meta learning aims at finding an algorithm that is best suited to address a class of learning problems (tasks). These tasks are sampled from an unknown meta distribution and are only partially observed via a finite collection of training examples, see and references therein. This problem plays a large role in artificial intelligence in that it can improve the efficiency of learning from human supervision. In particular, substantial improvement over “learning in isolation” (also known as independent task learning) is to be expected when the sample size per task is small, a setting which naturally arises in many applications .

LTL is particularly appealing when considered from an online or incremental perspective. In this setting, which is sometimes referred to as lifelong learning (see, e.g. ), the tasks are observed sequentially – via corresponding sets of training examples – from a common environment and we aim to improve the learning ability of the underlying algorithm on future yet-to-be-seen tasks from the same environment. Practical scenarios of lifelong learning are wide ranging, including computer vision , robotics , user modelling and many more.

Although LTL is naturally suited for the incremental setting, surprisingly theoretical investigations are lacking. Previous studies, starting from the seminal paper by Baxter , have almost exclusively considered the setting in which the tasks are given in one batch , that is, the meta algorithm processes multiple datasets from the environment jointly and only once as opposed to sequentially and indefinitely. The papers present results in an online framework which applies to a finite number of tasks using different performance measures. Perhaps most related to our work is , where the authors consider a general PAC-Bayesian approach to lifelong learning based on the exponentially weighted aggregation procedure. Unfortunately, this approach is not efficient for large scale applications as it entails storing the entire sequence of datasets during the meta learning process. LTL also bears strong similarity to multitask learning (MTL) and much work has been done on the theoretical study of both batch and online multitask learning algorithms. However multitask learning aims to solve the different – and perhaps less challenging – problem of learning well on a prescribed set of tasks (the learned model is tested on the same tasks used during training) whereas LTL aims to extrapolate to new tasks.

The principal contribution of this paper is to propose an incremental approach to learning-to-learn and to analyse its statistical guarantees. This incremental approach is appealing in that it efficiently processes one dataset at the time, without the need to store previously encountered datasets. We study in detail the case of linear representation learning, in which an underlying learning algorithm receives in input a sequence of datasets and incrementally updates the data representation so as to better learn future tasks. Following previous work on LTL , we measure the performance of the incremental meta algorithm by the transfer risk, namely the average error obtained by running the underlying algorithm with the learned representation, over tasks sampled from the meta distribution.

Specifically, in this work we choose the underlying algorithm to be Ridge Regression parameterized by a positive semidefinite matrix. The incremental LTL approach we propose aims at optimizing the future empirical error incurred by Ridge Regression over a class of linear representations. For this purpose, we propose to apply Projected Stochastic Subgradient Algorithm (PSSA). We show that the objective function of the resulting meta algorithm is convex and we give a non-asymptotic convergence rate for the algorithm in high probability. A remarkable feature of our learning bound is that it is comparable to previous bounds for batch LTL. Our proof technique leverages previous work on learning-to-learn with tools from online convex optimization, see and references therein.

The paper is organized as follows. In Sec. 2, we review the LTL problem and describe in detail the case of linear feature learning with Ridge Regression. In Sec. 3, we present our incremental meta algorithm for linear feature learning. Sec. 4 contains our bound on the excess transfer risk for the proposed algorithm and in Sec. 5 we compare the bound to a previous bound for the batch setting. In Sec. 6, we report preliminary numerical experiments for the proposed algorithm and, finally, Sec. 7 summarizes the paper and highlight directions of future research.

PROBLEM FORMULATION

A well-established approach to tackle the learning problem is offered by regularized empirical risk minimization. This corresponds to the family of algorithms $A_{\phi}$ such that, for any $Z\in{\cal Z}^{n}$,

where $\phi:{\cal X}\to{\cal F}_{\phi}$ is a feature map, ${\cal F}_{\phi}$ is the Hilbert space of functions $f:{\cal X}\to{\cal Y}$ such that $f(x)=\langle f,\phi(x)\rangle$ for any $x\in{\cal X}$ and

denotes the empirical risk of function $f$ on the set $Z$.

Since for any linear feature map $\phi$ there exists a PSD matrix $D$ such that Eq. (2) and Eq. (4) are equivalent, in the following we will refer to $D$ as the representation used by algorithm $A_{D}$.

2 Learning to Learn DD

A natural question is how to choose a good representation $D$ for a given family of related learning problems. In this work we consider the approach of learning it from data. In particular, following the seminal work of , we consider a setting where we are provided with an increasing number of tasks and our goal is to find a joint representation $D$ such that the corresponding algorithm $A_{D}$ is suited to address all such learning problems. The underlying assumption is that all tasks that we observe share a common structure that algorithm $A_{D}$ can leverage in order to achieve better prediction performance.

More formally, we assume that the tasks we observe are independently sampled from a meta distribution $\rho$ on the set of probability measures on ${\cal Z}$. According to the literature on the topic (see e.g. ) we refer to the meta distribution $\rho$ as the environment and we identify each task sampled from $\rho$ by its corresponding distribution $\mu$, from which we are provided with a training dataset $Z\sim\mu^{n}$ of $n$ points sampled independently from $\mu$. While it is possible to consider a more general setting, for simplicity in this work we study the case where for each task we sample the same number $n$ of training points. In line with the independent task learning setting, the goal of a “learning to learn” algorithm is therefore to find the best parameter $D$ minimizing the so-called transfer risk

over a set ${\mathfrak{D}}$ of candidate representations.

The term ${\cal E}(D)$ is the expected risk that the corresponding algorithm $A_{D}$, when trained on the dataset $Z$, would incur on average with respect to the distribution of tasks $\mu$ induced by $\rho$. That is, to compute the transfer risk, we first draw a task $\mu\sim\rho$ and a corresponding $n$-sample $Z\in\mathcal{Z}^{n}$ from $\mu^{n}$, we then apply the learning algorithm to obtain an estimator $A_{D}(Z)$ and finally we measure the risk of this estimator on the distribution $\mu$.

The problem of minimizing the transfer risk in Eq. (5) given a finite number $T$ of training datasets $Z_{1},\dots,Z_{T}$ sampled from the corresponding tasks $\mu_{1},\dots,\mu_{T}$, has been subject of thorough analysis in the literature . Most work has been focused on the so-called “batch” setting, where all such training datasets are provided at once. However, by its nature, LTL is an ongoing (possibly never ending) process, with training datasets observed a few at the time. In such a scenario the meta algorithm should allow for an evolving representation $D$, which improves over time as new datasets are observed. In the following we propose a meta algorithm to learn $D$ online with respect to the tasks, allowing us to transfer past experience about the environment in an efficient manner, without requiring the memorization of training data, which could be prohibitive in large scale applications. We will study the theoretical guarantees of the proposed algorithm and compare it to its batch counterpart in terms of both statistical and empirical performance.

3 Connection with Multitask Learning

LTL is strongly related to multitask learning (MTL) and in fact, as we will see later for the algorithm in Eq. (4), approaches developed for MTL can be used as inspiration to design algorithms for LTL. In multi-task learning a fixed number of tasks $\mu_{1},\dots,\mu_{T}$ is provided up front and, given $T$ datasets $Z_{1},\dots,Z_{T}$, each sampled from its corresponding distribution, the goal is to find a joint representation $D$ incurring a small average expected risk $\frac{1}{T}\sum_{t=1}^{T}{\cal R}_{\mu_{t}}(A_{D}(Z_{t}))$. In this sense, the main difference between LTL and MTL is that the former aims to guarantee good prediction performance on future tasks, while the latter goal is to guarantee good prediction performance on the same tasks used to train $D$.

A well-established approach to MTL is multitask feature learning . This method consists in solving the optimization problem

where $\textrm{Int}({{\mathfrak{D}}_{\lambda}})$ is the interior of ${{\mathfrak{D}}_{\lambda}}$, namely the set of PSD invertible matrices with trace strictly smaller than $1/\lambda$. This leads to the equivalent problem

ONLINE LEARNING-TO-LEARN

Motivated by the above connection with multitask learning, we propose an online LTL approach to approximate the solution of the learning problem

over the set ${{\mathfrak{D}}_{\lambda}}$ introduced in Eq. (7). We consider the setting in which we are provided with a stream of independent datasets $Z_{1},\dots,Z_{T},\dots$, each sampled from an individual task distribution $\mu_{1},\dots,\mu_{T},\dots$ and our goal is to find an estimator in ${{\mathfrak{D}}_{\lambda}}$ that improves incrementally as the number of observed tasks $T$ increases.

A key observation motivating the online procedure proposed in this work, is that in the independent task learning setting, standard results from learning theory (see e.g. ) allow one to control the statistical performance of regularized empirical risk minimization, providing bounds on the generalization error of $A_{D}$ as

where $G(\cdot,n)$ is a decreasing function converging to $0$ as $n\to+\infty$, while $G(D,\cdot)$ is a measure of complexity of $D$, which is large for more “expressive” representations and smaller otherwise.

Eq. (11) suggests us to use the empirical risk ${\cal R}_{Z}$ as a proxy for the expected risk ${\cal R}_{\mu}$. Therefore, we introduce the so-called future empirical risk ,

which in the sequel, introducing the shorthand notation ${\cal L}_{Z}(D)={\cal R}_{Z}(A_{D}(Z))$ for any PSD matrix $D$, will be rewritten as

Problem (14) can be approached with stochastic optimization strategies. Such methods proceed by sequentially sampling a point (dataset in this case) $Z$ and performing an update step. In recent years, stochastic optimization, finding its origin in the Stochastic Approximation method by Robbins and Monro , has been effectively used to deal with large scale applications. We refer to for a more comprehensive discussion about this topic. We therefore propose to apply Projected Stochastic Subgradient Algorithm (PSSA) , to solve the optimization problem in Eq. (14). The candidate representation coincides in this case with the mean after $T$ iterations $\bar{D}_{T}$ and it is known as Polyak-Ruppert averaging scheme in the optimization literature. Algorithm 1 reports the application of PSSA to $\hat{\cal E}$ when ${\cal L}_{Z}$ is convex on the set of PSD matrices. It requires iteratively: $i)$ sampling a dataset $Z$, $ii)$ performing a step in the direction of a subgradient of ${\cal L}_{Z}$ at the current point, and $iii)$ projecting onto the set ${{\mathfrak{D}}_{\lambda}}$ (which can be done in a finite number of iterations, see 16 in Appendix E ). Note that in this case, since the function ${\cal L}_{Z}$ is convex, there is no ambiguity in the definition of the subdifferential $\partial{\cal L}_{Z}$ (see e.g. ) and we can rely on the convergence of Algorithm 1 to a global minimum of $\hat{\cal E}$ over ${{\mathfrak{D}}_{\lambda}}$ for a suitable choice of step-sizes, as discussed in Sec. 4.

2 LTL with Ridge Regression

Plugging this solution in the definition of ${\cal L}_{Z}(D)$, a direct computation yields that

${\cal L}_{Z}$ is convex on the set of PSD matrices.

${\cal L}_{Z}$ is $2$-Lipschitz w.r.t. the Frobenius norm.

$\nabla{\cal L}_{Z}$ is $6$-Lipschitz w.r.t. the Frobenius norm.

The proposition above establishes the convexity of Problem (13) for the case of the square loss. This fact is important in that it guarantees no ambiguity in applying Algorithm 1 to our setting and moreover, since ${\cal L}_{Z}$ is differentiable, Algorithm 1 becomes a Projected Stochastic Gradient Algorithm.

THEORETICAL ANALYSIS

In this section, we study the statistical properties of Algorithm 1 for the case of the square loss. Below we report the main result of this work, which characterizes the non-asymptotic behavior of the estimator $\bar{D}_{T}$ produced by Algorithm 1 with respect to a minimizer $D_{*}\in\textrm{argmin}_{D\in{{\mathfrak{D}}_{\lambda}}}{\cal E}(D)$. To present our results we introduce the $d\times d$ matrix

denoting the covariance of the input data, obtained by averaging over all input marginals sampled from $\rho$. This quantity plays a key role in identifying the environments $\rho$ for which it is favorable to adopt a LTL strategy instead of solving the tasks independently, see for a discussion. We also denote with $\|C_{\rho}\|_{\infty}$ the operator norm of $C_{\rho}$, which corresponds to the largest singular value.

with probability at least $1-\delta$ with respect to the independent sampling of tasks $\mu_{t}\sim\rho$ and training sets $Z_{t}\sim\mu_{t}^{n}$ for any $t\in\{1,\dots,T\}$.

In Sec. 5, we will compare Thm. 2 with the statistical bounds available for state of the art LTL batch procedures. We will see that the statistical behaviour of these two approaches is essentially equivalent, with Online LTL being more appealing given the lower requirements in terms of both number of computations and memory.

In the rest of this section we give a sketch of the proof for Thm. 2. Proofs of intermediate results are reported in the appendix.

The statistical analysis of Algorithm 1 hinges upon the following decomposition for the excess transfer risk of the estimator $\bar{D}_{T}$:

where the matrix $\hat{D}_{*}$ denotes a minimizer of the future empirical risk over ${{\mathfrak{D}}_{\lambda}}$, that is, $\hat{D}_{*}\in\textrm{argmin}_{D\in{{\mathfrak{D}}_{\lambda}}}\hat{\cal E}(D)$.

Eq. (4.1) decomposes ${\cal E}(\bar{D}_{T})-{\cal E}(D_{*})$ in a uniform generalization error, implicitly encoding the complexity of the class of algorithms parameterized by $D$ and an excess future empirical risk, measuring the discrepancy between the estimator $\bar{D}_{T}$ and the minimizer $\hat{D}_{*}$ of $\hat{\cal E}$. In the following we describe how to bound these two terms.

2 Bounding the Uniform Generalization Error

Results providing generalization bounds for the class of regularized empirical risk minimization algorithms $A_{D}$ considered in this work are well known. The following result, which is taken from , leverages an explicit estimate of the generalization bound $G(D,n)$ introduced in Sec. 3.1 for independent task learning (see Eq. (11)) to obtain a uniform bound over the class of algorithms parametrized by ${{\mathfrak{D}}_{\lambda}}$.

For completeness, we report the proof of this proposition in Appendix B.3.

3 Bounding the Excess Future Empirical Risk

Providing bounds for the excess future empirical risk introduced in Eq. (4.1) consists in studying the convergence rates of Algorithm 1 to the minimum of $\hat{\cal E}$ over ${{\mathfrak{D}}_{\lambda}}$ in high probability with respect to the sample of $T$ tasks $\mu_{t}$ from $\rho$ and datasets $Z_{t}$ from $\mu_{t}^{n}$ for any $t\in\{1,\dots,T\}$.

To this end, we leverage classical results from the online learning literature . In online learning, the performance of an online algorithm returning a sequence $\{D^{(t)}\}_{t=1}^{T}$ over $T$ trials is measured in terms of its regret, which in the context of this work corresponds to

Differently from the statistical setting considered in this work, in the online setting no assumption is made about the data generation process of $Z_{1},\dots,Z_{T}$, which could be even adversely generated. Therefore, an algorithm that is able to solve the online problem (i.e. if its regret vanishes as $T\to\infty$) can be also expected to solve the corresponding problem in the statistical setting. This is indeed the case for Algorithm 1, for which the following lemma provides a non-asymptotic regret bound.

This lemma is a corollary of Prop. 1 combined with classical results on regret bounds for Projected Online Subgradient Algorithm . We refer the reader to Appendix D.1 for a more in-depth discussion and for a detailed proof.

In our setting, the datasets $Z_{1},\dots,Z_{T}$ are assumed to be independently sampled from the underlying environment. Combining this assumption with the regret bound in 4, we can control the excess future empirical risk by means of so-called online-to-batch conversion results , leading to the following proposition.

The result above follows by combining Prop. 1 with online-to-batch results (see e.g. Thm. $9.3$ in and ). In Appendix D.2 we provide the complete proof of this statement together with a more detailed discussion about this topic. At this point we are ready to give the proof of Thm. 2.

The claim follows by combining Prop. 3 and Prop. 5 in the decomposition of the error ${\cal E}(\bar{D}_{T})-{\cal E}(D_{*})$ given in Eq. (4.1). ∎

ONLINE LTL VERSUS BATCH LTL

In this section, we compare the statistical guarantees obtained for our online meta algorithm with a state of the art batch LTL method for linear feature learning. We also comment on the computational cost of both procedures.

Given a finite collection ${\bf Z}=\{Z_{1},\dots,Z_{T}\}$ of datasets, a standard approach to approximate a minimizer of the future empirical risk $\hat{\cal E}$ is to take a representation $\hat{D}_{T}$ minimizing the multitask empirical risk

over the set ${{\mathfrak{D}}_{\lambda}}$. Such a choice has been extensively studied in the LTL literature . Here we report a result analogous to Thm. 2, characterizing the discrepancy between the transfer risks of $\hat{D}_{T}$ and $D_{*}$.

The result above is obtained by further decomposing the error ${\cal E}(\hat{D}_{T})-{\cal E}(D_{*})$ as done in Eq. (4.1). In particular, since the multitask empirical error provides an estimate for the future empirical risk, it is possible to to control the overall error by further bounding the term $|\hat{\cal E}(D)-\hat{\cal E}_{\bf Z}(D)|$ uniformly with respect to $D\in{{\mathfrak{D}}_{\lambda}}$. This last result was originally presented in ; in Appendix C we report the complete analysis of such decomposition, leading to the bound in Thm. 6.

2 Statistical Considerations

We now are ready to compare the bounds on the excess transfer risk for the representations resulting from the application of the online procedure (see Thm. 2) and the batch one (see Thm. 6); this provides a first indication of the behavior of the different algorithms. However, it should be kept in mind that we are comparing upper bounds, hence our considerations are not conclusive and further analysis by means of lower bounds for both algorithms would be valuable.

At first, we observe that both bounds reflect the fact that the LTL setting is more challenging than the MTL setting. As we have remarked in Sec. 2.3, MTL aims at bounding the excess averaged expected risk relative to a fixed set of $T$ tasks. Such bounds can be expressed as a function $B(n,T)$, with $B(n,T)\to 0$ as $n\to\infty$ for any $T$. In LTL, the bounds study the behavior of the excess transfer risk, measuring how well the candidate estimator will work on a new task sampled from the environment. Therefore, it is no longer possible that $B(T,n)\to 0$ for $n\to\infty$ for any $T$, we only have that $B(T,n)\to 0$ when $n$ and $T$ simultaneously tend to infinity.

Thm. 2and Thm. 6 are both composed of three terms. The first term is exactly the same for both procedures and this is obvious looking at the decompositions used to deduce both results. This term can be interpreted as a within-task-estimation error, that depends on the number of points $n$ used to train the underlying learning algorithm (in our case Ridge Regression with a linear feature map). This term, similarly to the MTL setting, highlights the advantage of exploiting the relatedness of the tasks in the learning process in comparison to independent task learning (ITL). Indeed, if the inputs are distributed on a high dimensional manifold, then $\|C_{\rho}\|_{\infty}\ll 1$, while upper bounds for ITL have a leading constant of 1. In particular, $\|C_{\rho}\|_{\infty}=1/d$ if the marginal distributions of the tasks are uniform on the $d-1$ dimensional unit sphere; see also for a more detailed discussion. The last term in the bounds expresses the dependency on the confidence parameter $\delta$ and it is again approximately the same for the batch and the online case. It follows that the main role in the comparison between the online and batch bounds is driven by the middle term, which expresses the dependency of the bound on the number of tasks $T$. This term originates in different ways: in the batch approach it is derived from the application of uniform bounds and it can be interpreted as an inter-task estimation error, while in the online approach, it plays the role of an optimization error. Despite the different derivations, we can ascertain from the explicit formula of the bounds that this term is approximately the same for both procedures. This is remarkable since it implies that the representation resulting from our online procedure enjoys the same statistical guarantees than the batch one, despite its more parsimonious memory and computational requirements.

3 Computational Considerations

After discussing the theoretical comparison between the online and the batch LTL approach, in this section we point out some key aspects regarding the computational costs of both procedures.

Memory. The batch LTL estimator corresponds to the minimizer of the empirical risk in Eq. (28) over all tasks observed so far. The corresponding approach would therefore require storing in memory all training datasets as they arrive in order to perform the optimization. This is clearly not sustainable in the incremental setting, since tasks are observed sequentially and, possibly indefinitely, which would inevitably lead to a memory overflow. On the contrary, in line with most stochastic methods, online LTL has a small memory footprint, since it requires to store only one dataset at the time, allowing to “forget” it as soon as one gradient step is performed.

Time. Online LTL is also advantageous in terms of the number of iterations performed whenever a new task is observed. Indeed, for every new task, online LTL performs only one step of gradient descent for a total of $T$ steps after $T$ tasks. On the contrary, batch LTL requires finding a minimizer for Eq. (28), which cannot be obtained in closed form but requires adopting an iterative method such as Projected Gradient Descent (see e.g. ). These methods typically require $k$ iterations to achieve an error of the order of $O(1/k)$ from the optimum (better rates are possible adopting accelerated methods). However, since for any new task batch LTL needs to find a minimizer for the multitask empirical error in Eq. (28) from scratch, this leads to a total of $Tk$ iterations after $T$ tasks. Noting that every such iteration requires to compute $T$ gradients of ${\cal L}_{Z}$ in contrast to the single one of PSSA, this shows that online LTL requires much less operations. In the batch case, a “warm-restart” strategy can be adopted to initialize the Projected Gradient Descent with the representation learned during the previous step, however, as we empirically observed in Sec. 6, online LTL is still significantly faster than batch.

EXPERIMENTS

In this section, we report preliminary empirical evaluations of the online LTL strategy proposed in this work. In particular we compare our method with its batch (or offline) counterpart and independent task learning (ITL) with standard Ridge Regression.

In the online setting the training datasets arrive incrementally and a few at the time. Therefore model selection is performed in parallel: the system keeps track of all candidate representation matrices $\bar{D}_{\lambda_{1}},\dots,\bar{D}_{\lambda_{m}}$ and whenever a new training task is presented, these matrices are all updated by incorporating the corresponding new observations. The best representation is then returned at each iteration, based on its performance on the validation set ${\bf Z}_{\rm va}$.

Figure 1 reports the comparison between the baseline ITL and the proposed online LTL approach in terms of the relative difference of the prediction error on test tasks for the two methods. More precisely, given the mean squared errors (MSE) $R_{\rm oLTL}$ of online LTL and $R_{\rm ITL}$ of ITL averaged across the test tasks, we report the ratio $(R_{\rm ITL}-R_{\rm oLTL})/R_{\rm ITL}$ as a percentage improvement. Results are reported across a range of $T_{\rm tr}$ and $n$. We note that the regime considered for these experiments is particularly favorable to LTL, consistently outperforming ITL, which does not leverage any shared structure. As noted in Sec. 5.2, when the number of training points per task is small, the LTL algorithm is unable to capture the underlying representation, even if several tasks are provided in training. To provide further evidence of the performance of online LTL, Figure 2 compares the prediction error of online LTL, batch LTL, and ITL as the number of training tasks $T_{\rm tr}$ increases from $1$ to $50$ and the number of samples per task is fixed to $n=25$. In particular we considered the setting where the task datasets are provided incrementally one at the time and the different methods update their corresponding representation accordingly. We also report the performance of the multitask algorithm (MTL) described in Sec. 2.3, performing trace norm regularization on the test set. Clearly, MTL does not fit the learning to learn setting since it optimizes the representation on the test set. In this sense, loosely speaking, the MTL performance provides a lower bound on the performance that we can expect from an “ideal” LTL algorithm. Indeed, we note that MTL consistently outperforms all LTL methods which, however, tend to converge to it as more training tasks are provided.

Interestingly, the online approach is able to rapidly close the gap with batch LTL as the number of training tasks increases. This is particularly favorable since, from the computational perspective, online LTL is significantly faster than its batch counterpart. To further emphasize this aspect, Table 1 compares the computational times required on average by online LTL and batch LTL as $T_{\rm tr}$ and $n$ vary. Online LTL is clearly faster then batch LTL. Indeed, as discussed in Sec. 5.3, whenever a new training task is provided, batch LTL requires to perform hundreds or thousands iterations of gradient descent to converge to a minimizer, even when “warm restarting” by initializing with the representation found at the previous step. On the other hand online LTL performs a single gradient step for each new task.

CONCLUSION AND FUTURE WORK

In this work, we have proposed an incremental approach to LTL which estimates a linear data representation that works well on regression tasks coming from a meta distribution. Compared with its batch (or offline) counterpart, this incremental approach is computationally more efficient both in terms of memory and number of operations, while enjoying the same generalization properties. Preliminary experiments have highlighted the favorable learning capability of the proposed learning-to-learn strategy. To our knowledge this is the first efficient incremental algorithm for meta learning for which statistical guarantees have been proved. Previous works either relied on algorithms which require to store the entire data sequence or which do not have statistical guarantees . Our analysis open several directions that will be worth investigating in the near future. First, it would be valuable to extend our analysis to a general class of loss functions. Although not allowing for a closed form expression as in the case of Ridge Regression, we suspect that it would be still be possible to extend our results by leveraging the regularity properties of the underlying learning algorithm. Second, we would like to depart from the feature learning setting by considering a more general family of learning-to-learn algorithms. Inspiration towards this direction is offered by the literature on multitask learning.

APPENDIX

Appendix A PROOF of Prop. 1

Recall the definition of the function ${\cal L}_{Z}$ in Eq. (17). In order to provide the proof of Prop. 1 we need the following Lemma.

$\big\|\bigl(G_{i}+\gamma I\bigr)^{-1}\big\|_{\infty}\leq{\gamma}^{-1}$.

$\big\|\bigl(G_{1}+\gamma I\bigr)^{-1}-\bigl(G_{2}+\gamma I\bigr)^{-1}\big\|_{\infty}\leq{\gamma^{-2}}\big\|G_{1}-G_{2}\big\|_{\infty}$.

Let $w_{1}$ and $w_{2}$ satisfy $\bigl(G_{i}+\gamma I\bigr)w_{i}={\bf y}$ for some ${\bf y}$, for $i=1,2$. Then we have that

Moreover, the following formula, which is a direct consequence of Eq. ($33$) and Eq. ($53$) in , holds:

and since, for every $k,h\in\{1,\dots,n\}$, we have that

and exploiting the symmetry of $M(D)$, we can rewrite:

This last equation contains the elements of the Jacobian in the statement of the proposition.

where in the first inequality we have applied 7-(d) with $G_{i}=XD_{i}X^{\scriptscriptstyle\top}$, for $i=1,2$. The statement now follows observing that if $\mathcal{Y}\subseteq$, then $\lVert{\bf y}\rVert^{2}\leq n$ and if $\mathcal{X}\subseteq\mathcal{B}_{1}$, then $\lVert X\rVert_{\infty}^{2}\leq n$.

$\lVert AB\rVert_{2}\leq\lVert A\rVert_{\infty}\lVert B\rVert_{2}$ for any two matrices $A$ and $B$,

by 7-(b): $\lVert M_{i}^{-1}\rVert_{\infty}\leq 1/n$ for $i=1,2$,

$\displaystyle\big\|M_{1}^{-2}-M_{2}^{-2}\big\|_{\infty}=\big\|M_{1}^{-1}\bigl(M_{1}^{-1}-M_{2}^{-1}\bigr)+\bigl(M_{1}^{-1}-M_{2}^{-1}\bigr)M_{2}^{-1}\big\|_{\infty}\leq\frac{2}{n}\big\|M_{1}^{-1}-M_{2}^{-1}\big\|_{\infty}$,

if $\mathcal{X}\subseteq\mathcal{B}_{1}$ and $\mathcal{Y}\subseteq$, then $\lVert X\rVert_{2}\leq\sqrt{n}$ and $\lVert R\rVert_{\infty}=\lVert{\bf y}{\bf y}^{\scriptscriptstyle\top}\rVert_{\infty}\leq n$,

The last point is contained in [20, Prop. 1-(i)]; we report here the proof for completeness. To this end, we require some additional notation, which will be also used also in the next section of the appendix.

Coming back to the proof of the proposition, as observed in , it is possible to rewrite the algorithm defined in Eq. (16) in the equivalent form

From Eq. (40), we have that $\langle A_{D}({\bf z}),x\rangle=\big\langle A^{\rm Rid}(D^{1/2}{\bf z}),D^{1/2}x\big\rangle$, for any $x\in\mathcal{X}$ and any dataset ${\bf z}$. Consequently

Due to the definition of $A^{\rm Rid}$, assuming $\mathcal{Y}\subseteq$, the following relations hold:

The claim now follows by combining the last inequality with Eq. (42).

Appendix B UNIFORM BOUNDS for LINEAR FEATURE LEARNING

In this section, we provide the uniform bounds on ${\cal E}(D)-\hat{\cal E}(D)$ and $\hat{\cal E}(D)-\hat{\cal E}_{\bf Z}(D)$ (and the corresponding symmetric quantities) for the family of linear feature learning algorithms. Our observations are essentially taken from , we report them for clarity of exposition. We start from recalling some tools from empirical processes, then we state the uniform bounds for a more general class of learning algorithms and finally we specialize the bounds to linear feature learning. We ignore issues of measurability throughout.

For more details about these quantities, we refer to . Given a class $\mathcal{F}$ of real-valued functions on a set $\mathcal{\mathcal{V}}$, and given a point $V=(v_{1},\dots,v_{m})\in\mathcal{\mathcal{V}}^{m}$, we let

so that $\mathfrak{R}(\mathcal{F}(V))$ and $\mathcal{G}(\mathcal{F}(V))$ are the corresponding Rademacher and Gaussian averages.

The following theorem is taken from , where the author considers only the inequality for the function $\Phi_{1}$. Considering both inequalities allows us to obtain symmetric uniform bounds. The proof follows the same pattern as in .

Let $\eta$ be a probability distribution over the space $\mathcal{V}$, let $\mathcal{F}$ be a real-valued function class on $\mathcal{V}$ and let $V=(v_{1},\dots,v_{m})\in\mathcal{V}^{m}$. Define the random functions:

If $\mathcal{F}$ is $$-valued, then, for any$\delta\in(0,1]$, we have that

with probability at least $1-\delta$ in $V\sim\eta^{m}$, for $k=1,2$.

In the previous two points we can replace $\mathfrak{R}(\mathcal{F}(V))$ with $\displaystyle\sqrt{\pi/2}\mathcal{G}(\mathcal{F}(V))$.

B.2 Uniform Bounds for a More General Family of Algorithms

The results presented in this sub-section hold for the infinite dimension case. In the sequel, we let ${\cal X}$ be a generic Hilbert space and we denote by $\langle\cdot,\cdot\rangle$ and $\lVert\cdot\rVert$ its scalar product and the induced norm. We let $\mathcal{S}_{+}(\mathcal{X})$ be the set of positive semidefinite bounded linear operators on ${\cal X}$ and, for any operator $D\in\mathcal{S}_{+}(\mathcal{X})$, we denote its $p$-Schatten norm by $\lVert D\rVert_{p}$, where $p\in[1,\infty]$. We continue to use the notation introduced in the paper and in Remark 1, in particular, ${\bf Z}=\{{\bf z}_{t}\}_{t=1}^{T}$ is the meta sample and, for any $D\in\mathcal{S}_{+}(\mathcal{X})$, we denote $D^{1/2}{\bf z}=\bigl(D^{1/2}x_{i},y_{i}\bigr)_{i=1}^{n}$. Throughout this section we will consider linear models and a learning algorithm $A({\bf z})$ processing a training set ${\bf z}\in{\cal Z}^{n}$ of $n$ points:

hence, according to our notation, we have that $A({\bf z})(x)=\langle A({\bf z}),x\rangle$ for any $x\in\mathcal{X}$. For any $D\in\mathcal{S}_{+}(\mathcal{X})$, define now the more general family of modified algorithms

By this definition, as we have already observed in the proof of Prop. 1-(5) in Sec. A, we have that

for any $x\in\mathcal{X}$ and consequently

In this way, we can consider the family of learning algorithms $\big\{{\bf z}\mapsto A_{D}({\bf z}):D\in\mathcal{S}_{+}(\mathcal{X})\big\}$, parameterized by the operators $D$. Recall now, for every $D\in\mathcal{S}_{+}(\mathcal{X})$, the notion of transfer risk

In order to give the next theorem, we need to introduce the Gramian matrix defined by the entries $[G({\bf x})]_{i,j}=\langle x_{i},x_{j}\rangle$ for $i,j=1,\dots,n$.

Let $\mathcal{X}\subseteq\mathcal{B}_{1}$ and $\mathfrak{D}\subseteq\mathcal{S}_{+}({\cal X})$ be a bounded set. Consider a function $f:{\cal Z}^{n}\to$ satisfying the condition

for any ${\bf z},{\bf z}^{\prime}\in{\cal Z}^{n}$ and for some $L_{K}\geq 0$. Let $\mu_{1},\dots,\mu_{T}$ tasks independently sampled from $\rho$ and ${\bf z}_{t}$ sampled from $\mu_{t}^{n}$ for $t\in\{1,\dots,T\}$. Then, for any $\delta\in(0,1]$, we have that

B.3 Application to the Family of Linear Feature Learning Algorithm

Similarly to what observed in Prop. 1-(5) in Sec. A, also in the infinite dimension case, we can cast the family of linear feature learning algorithms in the framework described in the previous sub-section, taking the original vanilla algorithm $A({\bf z})$ as Ridge Regression with regularization parameter equal to $1$:

we refer to for more details. Thus, we can apply the results in the previous sub-section to this specific case, in order to obtain the results stated in the paper for the uniform bounds. In fact, in the paper we have analyzed the finite dimension case, but from this analysis, we deduced that they still hold in the infinite dimension setting. The following definition will be used in the sequel.

be 1-bounded if $\lVert A({\bf z})\rVert\leq 1$ and $\hat{{\cal R}}({\bf z},A({\bf z}))\leq 1$ for any ${\bf z}\in{\cal Z}^{n}$;

have kernel stability $L_{K}$ if $\displaystyle\big|\hat{{\cal R}}({\bf z},A({\bf z}))-\hat{{\cal R}}({\bf z}^{\prime},A({\bf z}^{\prime}))\big|\leq\frac{L_{K}}{n}\big\|G({\bf x})-G({\bf x}^{\prime})\big\|_{2}$, for any ${\bf z},{\bf z}^{\prime}\in{\cal Z}^{n}$ and for some $L_{K}\geq 0$.

The following two lemmas are essentially taken from and they are respectively immediate consequences of Thm. 9 and Thm. 10 applied to the family of linear feature learning algorithms with restriction to the set

Thanks to the assumption ${\cal Y}\subseteq$, by [20, Prop. 1], $A^{\rm Rid}({\bf z})$, is $1$-bounded – and in particular, $\lVert A^{\rm Rid}(D^{1/2}{\bf z})\rVert\leq 1$ for any $D\in\mathcal{L}_{+}({\cal X})$ and any dataset ${\bf z}$ – with respect to the square loss. Hence, we can apply Thm. 9 to $A^{\rm Rid}$. We restrict to the set ${{\mathfrak{D}}_{\lambda}}$, we choose $q=1$ and $p=\infty$ and we observe that the square loss is $M(K)=2(K+1)$-Lipschitz on the interval $[-K,K]$. ∎

Thanks to the assumption that ${\cal Y}\subseteq$, by [20, Prop. 1], $A^{\rm Rid}({\bf z})$ is $1$-bounded – and in particular, $\hat{{\cal R}}\bigl(D^{1/2}{\bf z},A^{\rm Rid}(D^{1/2}{\bf z})\bigr)\leq 1$ for any $D\in\mathcal{L}_{+}({\cal X})$ and any dataset ${\bf z}$ – and has kernel stability $L_{K}=2$ with respect to the square loss. We can then apply Thm. 10 to the function

Appendix C PROOF of Thm. 6

In this section, we report the proof of Thm. 6. We do not make any claim of originality in this theorem which is merely a collection of results contained in ; we report the proof for completeness.

Similarly to the online case, the proof of Thm. 6 relies on the following decomposition.

We now describe how to deal with each term. We decompose the term $A$ as

and we bound the term $A1$ by Prop. 3 and the term $A2$ by Prop. 12 with confidence parameter $\delta/2$. The term $B$, thanks to the definition of $\hat{D}_{T}$, is negative. Lastly, as regards the term $C$, we split it in

where we bound $C2$ by Prop. 3, while, in order to bound the first term $C1$, we apply Hoeffding’s inequality (see 13 below) with parameters $a_{t}=0$ and $b_{t}=1$ for any $t$ (thanks to Prop. 1-(5)) and confidence parameter $\delta/2$, i.e. for any $\delta\in(0,1]$, we have that

with probability at least $1-\delta/2$ in ${\bf Z}$. Joining all the previous parts, the statement follows. ∎

Let $m$ be a positive integer and let $X_{1},\dots,X_{m}$ be independent random variables such that $X_{i}\in[a_{i},b_{i}]$ with probability $1$, for $i=1,\dots,m$. Define $\bar{X}_{m}=\displaystyle\frac{1}{m}\sum_{i=1}^{m}X_{i}$. Then, for any $\epsilon>0$, we have that

or equivalently, for any $\delta\in(0,1]$, we have that

Appendix D NON-ASYMPTOTIC RATES for PROJECTED STOCHASTIC SUBGRADIENT ALGORITHM

In this section, we briefly describe how to derive non-asymptotic convergence rates in probability for Projected Stochastic Subgradient Algorithm (PSSA), exploiting the regret bounds for Projected Online Subgradient Algorithm (POSA). In the first part we give a regret bound for POSA and we specialize it to Algorithm 1 for the case of the square loss (4). In the second part we first show, in general, how a bound on the regret implies a rate in probability for the convergence in the statistical setting and then we specialize this result to obtain the bound on the excess empirical future risk of the output of Algorithm 1 for the case of the square loss (Prop. 5). The results contained in this section are standard, we will cite during the presentation some references where the interested reader can find more details. Throughout this section, no differentiability assumptions on the functions will be made, we only require them to be convex and Lipschitz. We also require the boundedness of the diameter of the set over which we optimize. The general analysis will be conducted in a Hilbert space with scalar product $\langle\cdot,\cdot\rangle$ and induced norm $\lVert\cdot\rVert$.

In the sequel, we will always assume the convexity of the functions $f_{t}$ and the existence of a minimizer of the batch problem $\hat{h}\in\arg\min_{h\in H}\sum_{t=1}^{T}f_{t}(h)$. In our case, we will focus on the classical Projected Online Subgradient Algorithm described in Algorithm 2 and we will give an upper bound on its regret. When needed, the following assumptions will be made.

Assume that for any $t$ the functions $f_{t}$ are $G$-Lipschitz on $H$, i.e. there exists a positive constant such that $\lVert u\rVert\leq G$ for any $u\in\partial f_{t}(h)$ and for any $h\in H$.

Assume that the diameter of the set $H$ is bounded by some constant $\mathcal{D}>0$, i.e. $\displaystyle\sup_{h,h^{\prime}\in H}\lVert h-h^{\prime}\rVert\leq\mathcal{D}$.

The following theorem is a classical result and a slightly different version can be found in [16, Thm. 3.1], we report here the proof because of clarity and completeness.

Under Asm. 1 and Asm. 2, the regret of Algorithm 2, with $\gamma_{t}=c/\sqrt{t}$ for some $c>0$, is bounded by

Moreover, the optimal value for the previous bound, attained at $c=\displaystyle\frac{\mathcal{D}}{\sqrt{2}G}$, is $\displaystyle R_{T}\leq\frac{\sqrt{2}\mathcal{D}G}{\sqrt{T}}$.

Since $u_{t}\in\partial f_{t}(h^{(t)})$, by convexity of $f_{t}$ and definition of subgradient, we have that:

Using the update rule of Algorithm 2, Pythagorean Theorem (i.e. the non-expansiveness property of the projection operator) and Asm. 1, the following relations hold:

Combining Eq. (64) with Eq. (62), we obtain:

Now, summing Eq. (65) from $t=1$ to $t=T$, using the convention $1/\gamma_{0}=0$, and setting $\gamma_{t}=c/\sqrt{t}$ we can write:

where we have exploited Asm. 2, more precisely $\lVert h^{(t)}-\hat{h}\rVert\leq\mathcal{D}$, the fact that $\sum_{t=1}^{T}\Bigl(\frac{1}{\gamma_{t}}-\frac{1}{\gamma_{t-1}}\Bigr)=\frac{1}{\gamma_{T}}$ and the inequality $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}-1\leq 2\sqrt{T}$. Dividing by $T$ and optimizing with respect to $c$, the result follows. ∎

We now specialize the regret bound obtained for the generic Algorithm 2 to our Algorithm 1 described in the paper for the square loss.

The thesis follows from applying Thm. 14 to the context of Algorithm 1 with the square loss. In this case the iteration $h^{(t)}$ coincide with $D^{(t)}$, the cost functions are identified with $f_{t}={\cal L}_{Z_{t}}$, hence they are $2$-Lipschitz thanks to Prop. 1-(3) and, consequently, we can take $G=2$ in Thm. 14. Moreover, the diameter $\mathcal{D}$ of the set over which we project ${{\mathfrak{D}}_{\lambda}}$ (in the previous notation $H$) is $2/\lambda$. Indeed, for any $D\in{{\mathfrak{D}}_{\lambda}}$ we have that $\lVert D\rVert_{2}\leq\lVert D\rVert_{1}={\rm tr}(D)\leq 1/\lambda$, hence $\mathcal{D}=\sup_{D,D^{\prime}\in{{\mathfrak{D}}_{\lambda}}}\lVert D-D^{\prime}\rVert_{2}\leq 2/\lambda$. ∎

D.2 Online-to-Batch Conversion

and we will assume the existence of a minimizer $h_{*}\in\arg\min_{h\in H}F(h)$. In order to solve the stochastic problem in Eq. (67), we will analyze the general incremental procedure described in Algorithm 3, where the next point is updated by some rule depending on the past history of the process, for instance, if we choose the update $h^{(t+1)}={\rm{proj}}_{H}(h^{(t)}-\gamma_{t}u_{t})$, for some $\gamma_{t}>0$ and $u_{t}\in\partial f_{t}(h^{(t)})$, then Algorithm 3 coincides with POSA (Algorithm 2) applied to the functions $f_{t}={\cal L}_{Z_{t}}$.

In the online setting no further assumptions about the data are made, however, in the statistical setting we typically assume that the data are i.i.d. from the distribution $\eta$; since this last setting is more restrictive, one would expect that if Algorithm 3 solves the problem in the online framework, i.e. if its regret $R_{T}$ is such that $R_{T}\to 0$ as $T\to\infty$, then it will also solve the corresponding problem (67) in the statistical setting. This statement is formally confirmed by the following theorem, which relies on results taken from .

Let $f_{t}={\cal L}_{Z_{t}}$ be convex functions with values in $$for any$Z_{t}$,$t\in\{1,\dots,T\}$and let the points$\{Z_{t}\}_{t=1}^{T}$processed by Algorithm 3 be i.i.d. from$\eta$. Then, denoting by$R_{T}$the regret bound of Algorithm 3, for any$\delta\in(0,1]$, we have that

with probability at least $1-\delta$ in the sampling of the points $\{Z_{t}\}_{t=1}^{T}$.

The previous theorem relies on the theory of Martingales and the analysis of the first term $\frac{1}{T}\sum_{t=1}^{T}f_{t}(h^{(t)})$ of the regret (), in fact this term is a data-dependent statistics evaluating the average cumulative error of the prediction $h^{(t)}$ of the algorithm on the next point $Z_{t}$, therefore it is reasonable to expect that it contains information about the generalization ability of the algorithm.

Adapting the previous discussion to the setting of Algorithm 1 for the square loss, we obtain the following rate for the excess empirical future risk of online estimator returned by the algorithm.

Appendix E PROJECTION ON THE SET 𝔇λ{{\mathfrak{D}}_{\lambda}}

In the following lemma we describe how to perform the projection over the set ${{\mathfrak{D}}_{\lambda}}$ in a finite number of steps. Without loss of generality we consider the case that $\lambda=1$, the case regarding a general value of $\lambda$ immediately follows by a rescaling argument.

Let $Q$ be a $d\times d$ symmetric matrix and let $U\Gamma U^{\scriptscriptstyle\top}$ be an eigen-decomposition of $Q$, with $\Gamma={\rm Diag}(\gamma_{1},\dots,\gamma_{d})$. Then the solution of the problem

is given by ${\hat{D}}={Q}$ if $Q$ satisfies the constraints and ${\hat{D}}=U\Theta U^{\scriptscriptstyle\top}$ otherwise, where $\Theta={\rm Diag}(\theta_{1},\dots,\theta_{d})$, $\theta_{i}=\max(0,\gamma_{i}-a)$ for $i\in\{1,\dots,d\}$, and the nonnegative parameter $a$ is uniquely defined by the equation $\sum_{i=1}^{d}\max(0,\gamma_{i}-a)=1$.

The proof of the above lemma follows a standard path of reducing the matrix problem to a vector problem by application of von Neumann trace inequality, after which an argument based on Lagrange multipliers is employed, see e.g. [24, Theorem 15]. Note that the explicit equation defining the parameter $a$ can be solved efficiently in $O(d\log d)$ time, hence the computational cost of the projection is dominated by the computational cost $O(d^{3})$ of performing the eigen-decomposition of $Q$.

References