Meta-Strategy for Learning Tuning Parameters with Guarantees

Abstract

Online learning methods, similar to the online gradient algorithm (OGA) and exponentially weighted aggregation (EWA), often depend on tuning parameters that are difficult to set in practice. We consider an online meta-learning scenario, and we propose a meta-strategy to learn these parameters from past tasks. Our strategy is based on the minimization of a regret bound. It allows us to learn the initialization and the step size in OGA with guarantees. It also allows us to learn the prior or the learning rate in EWA. We provide a regret analysis of the strategy. It allows to identify settings where meta-learning indeed improves on learning each task in isolation.

1. Introduction

In many applications of modern supervised learning, such as medical imaging or robotics, a large number of tasks is available but many of them are associated with a small amount of data. With few datapoints per task, learning them in isolation would give poor results. In this paper, we consider the problem of learning from a (large) sequence of regression or classification tasks with small sample size. By exploiting their similarities we seek to design algorithms that can utilize previous experience to rapidly learn new skills or adapt to new environments.

Inspired by human ingenuity in solving new problems by leveraging prior experience, meta-learning is a subfield of machine learning whose goal is to automatically adapt a learning mechanism from past experiences to rapidly learn new tasks with little available data. Since it “learns the learning mechanism” it is also referred to as learning-to-learn [1]. It is seen as a critical problem for the future of machine learning [2]. Numerous formulations exist for meta-learning and we focus on the problem of online meta-learning where the tasks arrive one at a time and the goal is to efficiently transfer information from the previous tasks to the new ones such that we learn the new tasks as efficiently as possible (this has also been refered to as lifelong learning). Each task is in turn processed online. To sum up, we have a stream of tasks and for each task a stream of observations.

In order to solve online tasks, diverse well-established strategies exist: perceptron, online gradient algorithm (OGA), online mirror descent, follow-the-regularized-leader, exponentially weighted aggregation (EWA, also refered to as generalized Bayes etc.) We refer the reader to [3,4,5,6] for introductions to these algorithms and to so-called regret bounds, that control their generalization errors. We refer to these algorithms as the within-task strategies. The big challenge is to design a meta-strategy that uses past experiences to adapt a within-task strategy to perform better on the next tasks.

In this paper, we propose a new meta-learning strategy. The main idea to learn the tuning parameters is to minimize its regret bound. We provide a meta-regret analysis for our strategy. We illustrate our results in the case where the within-task strategy is the online gradient algorithm, and exponentially weighted aggregation. In the case of OGA, the tuning parameters considered are the initialization and the gradient steps. For EWA, we consider either the learning rate, or the prior. In each case, we compare the regret incurred when learning the tasks in isolation to our meta-regret bound. This allows us to identify settings where meta-learning indeed improves on learning in isolation.

1.1. Related Works

Meta-learning is similar to multitask learning [7,8,9] in the sense that the learner faces many tasks to solve. However, in multitask learning, the learner is given a fixed number of tasks, and can learn the connections between these tasks. In meta-learning, the learner must prepare to face future tasks that are not given yet.

Meta-learning is often referred to as learning-to-learn or lifelong learning. The authors of [10] proposed the following distinction: “learning-to-learn” for situations where the tasks are presented simultaneously, and “lifelong learning” for situations where they are presented sequentially. Following this terminology, learning-to-learn algorithms were proposed very early in the literature, with generalization guarantees [11,12,13,14,15,16].

On the other hand, in the lifelong learning scenario, until recently, algorithms were proposed without generalization guarantees [17,18]. A theoretical study was proposed by [10], but the strategies in that paper are not feasible in practice. This problem was recently improved [19,20,21,22,23,24,25,26]. In a similar context, in [27], the authors propose an efficient strategy to learn the starting point of OGA. However, an application of this strategy to learning the step size do not show any improvement over learning in isolation [28]. The closest work to this paper is [29] in which they also suggest a regret bound minimization strategy. This paper indeed provides a meta-regret bound for learning both the initialization and the gradient step. Note, however, that this paper remains specific to OGA, while our work can be potentially applied to any online learning algorithm. Indeed, we provide another example: the generalized Bayesian algorithm EWA, for which we learn the prior, or the learning rate. To learn the prior is new in the online setting, to our knowledge. It can be related to works in the batch setting [11,13,15,16], but the improvement with respect to learning in isolation is not quantified in these works.

Finally, it is important to note that we focus on the case where the number of tasks T is large, while the sample size n and algorithmic complexity of each task is moderately small. When each task is extremely complex, for example training a deep neural network on a huge dataset, our procedure (as well as those discussed above) will become too expansive. Alternative approaches were proposed, based on optimization via multi-armed bandits [30,31].

1.2. Organization of the Paper

In Section 2, we introduce the formalism of meta-learning and the notations that will be used throughout the paper. In Section 3, we introduce our meta-learning strategy, and its theoretical analysis. In Section 4, we provide the details of our method in the case of meta-learning the initialization and the step size in the online gradient algorithm. Based on our theoretical results, there are also explicit situations where meta-learning indeed improves on learning the tasks independently. This is confirmed by experiments reported in this section. In Section 5, we provide the details of our methodology when the algorithm used within tasks is a generalized Bayesian algorithm: EWA. We show how our meta-strategy can be used to tune the learning rate; we also discuss how it can be used to learn priors. The proofs of the main results are given in Section 6.

2. Notations and Preliminaries

By convention, vectors $v\in {\mathbb{R}}^d$ are seen as $d\times 1$ matrices (columns). Let $\parallel v\parallel$ denote the Euclidean norm of v. Let $A^T$ denote the transposition of any $d\times k$ matrix A, and $I_d$ the $d\times d$ identity matrix. For two real numbers a and b, let $a\vee b=max(a,b)$ and $a\wedge b=min(a,b)$. For $z\in \mathbb{R}$, $z_{+}$ is its positive part $z_{+}=z\vee 0$. Given a finite set S, we let $\mathrm{card}\left(S\right)$ denote the cardinality of S.

The learner has to solve tasks $t=1,\dots ,T$ sequentially. Each task t consists in n rounds $i=1,\dots ,n$. At each round i of task t, the learner has to take a decision ${\theta }_{t,i}$ in a decision space $\Theta \subseteq {\mathbb{R}}^d$ for some $d>0$. Then, a convex loss function ${\ell }_{t,i}:\Theta \to \mathbb{R}$ is revealed to the learner, who incurs the loss ${\ell }_{t,i}\left({\theta }_{t,i}\right)$. Classical examples with $\Theta \subset {\mathbb{R}}^d$ include regression tasks, where ${\ell }_{t,i}\left(\theta \right)={(y_{t,i}-x_{t,i}^T\theta )}^2$ for some $x_{t,i}\in {\mathbb{R}}^d$ and $y_{t,i}\in \mathbb{R}$. For classification tasks, ${\ell }_{t,i}\left(\theta \right)={(1-y_{t,i}{x}_{t,i}^T\theta )}_{+}$ for some $x_{t,i}\in {\mathbb{R}}^d$, $y_{t,i}\in \{-1,+1\}$.

Throughout the paper, we will assume that the learner uses, for each task, an online decision strategy called within-task strategy, parametrized by a tuning parameter $\lambda \in \mathsf{\Lambda }$ where $\mathsf{\Lambda }$ is a closed, convex subset of ${\mathbb{R}}^p$ for some $p>0$. Example of such strategies include the online gradient algorithm, given by ${\theta }_{t,i}={\theta }_{t,i-1}-\gamma \nabla {\ell }_{t,i}\left({\theta }_{t,i-1}\right)$. In this case, the tuning parameters are the initialization, or starting point, ${\theta }_{t,1}=\vartheta$ and the learning rate, or step size, $\gamma$. That is, $\lambda =(\vartheta ,\gamma )$, so $p=d+1$. The parameter $\lambda$ is kept fixed during the whole task. It is of course possible to use the same parameter $\lambda$ in all the tasks. However, we will be interested here in defining meta-strategies that will allow us to improve $\lambda$ task after task, based on the information available so far. In Section 3, we will define such strategies. For now, let ${\lambda }_t$ denote the tuning parameter used by the learner all along task t. Figure 1 provides a recap of all the notations.

Let ${\theta }_{t,i}^{\lambda }$ denote the decision at round i of task t when the online strategy is used with parameter $\lambda$. We will assume that a regret bound is available for the within-task strategy. By this, we mean that there is a set ${\Theta }_0\subset \Theta$ of parameters of interest, and that the learner knows a function ${\mathcal{B}}_n:\Theta \times \mathsf{\Lambda }\to \mathbb{R}$ such that, for any task t, for any $\lambda \in \mathsf{\Lambda }$,

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{\lambda }\right)\le \underset{=:{\mathcal{L}}_t\left(\lambda \right)}{\underbrace{\underset{\theta \in {\Theta }_0}{inf}\left\{\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+{\mathcal{B}}_n(\theta ,\lambda )\right\}}}.$$

(1)

For OGA, regret bounds can be found, for example, in [4,6] (in this case, ${\Theta }_0=\Theta$). Other examples include exponentially weighted aggregation (bounds in [3], here ${\Theta }_0$ is a finite set of predictors while decisions $\Theta$ are probability distributions on ${\Theta }_0$). More examples will be discussed in the paper. For a fixed parameter $\theta$, the quantity ${\sum }_{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{\lambda }\right)-{\sum }_{i=1}^n{\ell }_{t,i}\left(\theta \right)$ measures the difference between the total loss suffered during task t, and the loss what one would have suffered using the parameter $\theta$. It is thus called “the regret with respect to parameter $\theta$”, and ${\mathcal{B}}_n(\theta ,\lambda )$ is usually referred to as a “regret bound”. We will call ${\mathcal{L}}_t\left(\lambda \right)$ the “meta-loss”. In [29], the authors study a meta-strategy that minimizes the meta-loss of OGA. Indeed, if (1) is tight, to minimize the right-hand side is a good way to ensure that the left-hand side, that is, the cumulated loss, is small. In this work, we will focus on meta-strategies minimizing the meta-loss in a more general context.

The simplest meta-strategy is learning in isolation. That is, we keep ${\lambda }_t={\lambda }_0\in \mathsf{\Lambda }$ for all tasks. The total loss after task T is then given by:

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_0}\right)\le \sum _{t=1}^T{\mathcal{L}}_t\left({\lambda }_0\right).$$

(2)

However, when the learner uses a meta-strategy to improve the tuning parameter at the end of each task, the total loss is given by ${\sum }_{t=1}^T{\sum }_{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)$. We will, in this paper, investigate strategies with meta-regret bounds; that is, bounds of the form

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le \underset{\lambda \in \mathsf{\Lambda }}{inf}\left\{\sum _{t=1}^T{\mathcal{L}}_t\left(\lambda \right)+{\mathcal{C}}_T\left(\lambda \right)\right\}.$$

(3)

Of course, such bounds will be relevant only if the right-hand side of (3) is not larger than the right-hand side of (2), and is significantly smaller in some favourable settings. We show when this is the case in Section 4.

3. Meta-Learning Algorithms

In this section, we provide two meta-strategies to update $\lambda$ at the end of each task. The first one is a direct application of OGA to meta-learning. It is computationally simpler, but feasible only in the special case where we have an explicit formula for the (sub-)gradient of each ${\mathcal{L}}_t\left(\lambda \right)$. The second one is an application of implicit online learning to our setting. In Section 4, we provide an example where this is the case. The second meta-strategy can be used without this assumption. In both cases, we provide a regret bound as (3), under the following condition.

Assumption 1.

For any $t\in \{1,\dots ,T\}$, the function $\lambda \mapsto {\mathcal{L}}_t\left(\lambda \right)$ is L-Lipschitz and convex.

3.1. Special Case: The Gradient of the Meta-Loss Is Available in Closed Form

As each ${\mathcal{L}}_t$ is convex, its subdifferential at each point of $\mathsf{\Lambda }$ is non-empty. For the sake of simplicity, we will use the notation $\lambda \mapsto \nabla {\mathcal{L}}_t\left(\lambda \right)$ in the following formulas to denote any element of its subdifferential at $\lambda$. We define the online gradient meta-strategy (OGMS) with step $\alpha >0$ and starting point ${\lambda }_1\in \mathsf{\Lambda }$: for any $t>1$,

$${\lambda }_t={\mathsf{\Pi }}_{\mathsf{\Lambda }}[{\lambda }_{t-1}-\alpha \nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)]$$

(4)

where ${\mathsf{\Pi }}_{\mathsf{\Lambda }}$ denotes the orthogonal projection on $\mathsf{\Lambda }$.

3.2. The General Case

We now cover the general case, where a formula for the gradient of ${\mathcal{L}}_t\left(\lambda \right)$ might not be available. We propose to apply a strategy that was first defined in [32] for online learning, and studied under the name “implicit online learning” (we refer the reader to [33] and the references therein). In the meta-learning context, this gives the online proximal meta-strategy (OPMS) with step $\alpha >0$ and starting point ${\lambda }_1\in \mathsf{\Lambda }$, defined by:

$${\lambda }_t=\underset{\lambda \in \mathsf{\Lambda }}{argmin}\left\{{\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2}{2\alpha }\right\}.$$

(5)

Using classical notations, e.g., [34], we can rewrite this definition with the proximal operator (hence the name of the method). Indeed ${\lambda }_t={\mathrm{prox}}_{\alpha {\mathcal{L}}_{t-1}}\left({\lambda }_{t-1}\right)$ where $\mathrm{prox}$ is the proximal operator given for any $x\in \mathsf{\Lambda }$ and any convex function $f:\mathsf{\Lambda }\to \mathbb{R}$,

$${\mathrm{prox}}_f\left(x\right)=\underset{\lambda \in \mathsf{\Lambda }}{argmin}\left\{f\left(\lambda \right)+\frac{{\parallel x-\lambda \parallel }^2}{2}\right\}.$$

(6)

This strategy is feasible in practice in the regime we are interested in; that is, when n is small or moderately large, and $T\to \infty$. The learner has to store all the losses of the current task ${\ell }_{t-1,1},\dots ,{\ell }_{t-1,n}$. At the end of the task, the learner can use any convex optimization algorithm to minimize, with respect to $(\theta ,\lambda )\in \Theta \times \mathsf{\Lambda }$, the function

$$F_t(\theta ,\lambda )=\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+{\mathcal{B}}_n(\theta ,\lambda )+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2}{2\alpha }.$$

(7)

We can use a (projected) gradient descent on $F_t$ or its accelerated variants [35].

3.3. Regret Analysis

A direct application of known results to the setting of this paper leads to the following proposition. For the sake of completeness, we still provide the proofs in Section 6.

Proposition 1.

Under Assumption 1, using either OGMS or OPMS with step $\alpha >0$ and starting point ${\lambda }_1\in \mathsf{\Lambda }$ leads to

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le \underset{\lambda \in \mathsf{\Lambda }}{inf}\left\{\sum _{t=1}^T{\mathcal{L}}_t\left(\lambda \right)+\frac{\alpha T{L}^2}{2}+\frac{\parallel \lambda -{\lambda }_1{\parallel }^2}{2\alpha }\right\}.$$

(8)

The proof can be found in Section 6.

4. Example: Learning the Tuning Parameters of Online Gradient Descent

In all this section, we work under the following condition.

Assumption 2.

For any $(t,i)\in \{1,\dots ,T\}\times \{1,\dots ,n\}$, the function ${\ell }_{t,i}$ is Γ-Lipschitz and convex.

4.1. Explicit Meta-Regret Bound

We study the situation where the learner uses (projected) OGA as a within-task strategy; that is, $\Theta =\{\theta \in {\mathbb{R}}^d:\parallel \theta \parallel \le C\}$ and, for any $i>1$,

$${\theta }_{t,i}={\mathsf{\Pi }}_{\Theta }[{\theta }_{t,i-1}-\gamma \nabla {\ell }_{t,i}\left({\theta }_{t,i-1}\right)].$$

(9)

With such a strategy, we already mentioned that $\lambda =(\vartheta ,\gamma )\in \mathsf{\Lambda }\subset \Theta \times {\mathbb{R}}_{+}$ contains an initialization and a step size. An application of the results in Chapter 11 in [3] gives ${\mathcal{B}}_n(\theta ,\lambda )={\mathcal{B}}_n(\theta ,(\vartheta ,\gamma ))=\gamma {\mathsf{\Gamma }}^{2}n/2+{\parallel \theta -\vartheta \parallel }^2/\left(2\gamma \right)$. So

$${\mathcal{L}}_t\left((\vartheta ,\gamma )\right)=\underset{\parallel \theta \parallel \le C}{inf}\left\{\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\gamma {\mathsf{\Gamma }}^{2}n}{2}+\frac{{\parallel \theta -\vartheta \parallel }^2}{2\gamma }\right\}.$$

(10)

It is quite direct to check Assumption 1. We summarize this in the following proposition.

Proposition 2.

Under Assumption 2, assume that the learner uses OGA as an inner algorithm. Assume $\mathsf{\Lambda }=\{\vartheta \in {\mathbb{R}}^d:\parallel \vartheta \parallel \le C\}\times [\underline{\gamma },\overline{\gamma }]$ for some $C>0$ and $0<\underline{\gamma }<\overline{\gamma }<\infty$. Then Assumption 1 is satisfied with

$$L:=\sqrt{\frac{n^2{\mathsf{\Gamma }}^4}{4}+\frac{4C^2}{{\underline{\gamma }}^2}+\frac{4C^4}{{\underline{\gamma }}^4}}.$$

(11)

So, when the learner uses one of the meta-strategies OGMS or OPMS, we can apply Proposition 1 respectively. This leads to the following theorem.

Theorem 1.

Under the assumptions of Proposition 2, with $\underline{\gamma }=1/n^{\beta }$ for some $\beta >0$ and $\overline{\gamma }=C^2$, when the learner uses either OGMS or OPMS with

$$\alpha =\frac{C}{L}\sqrt{\frac{4+C^2}{T}}$$

(12)

(where L is given by (11)), we have:

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\left\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+\mathcal{C}(\mathsf{\Gamma },C)\left[n^{1\vee 2\beta }\sqrt{T}+\left(n^{1-\beta }+\sigma \left({\theta }_1^T\right)\sqrt{n}\right)T\right]\right\}$$

(13)

where $\mathcal{C}(\mathsf{\Gamma },C)>0$ depends only on $(\mathsf{\Gamma },C)$ and where:

$$\sigma \left({\theta }_1^T\right)=\sqrt{\frac{1}{T}\sum _{t=1}^T{∥{\theta }_t-\frac{1}{T}\sum _{s=1}^T{\theta }_s∥}^2}.$$

(14)

Let us compare this result with learning in isolation, as defined in (2); that is, solving the sequence of tasks with a constant hyperparameter $\lambda =(\vartheta ,\gamma )$. For the usual choice $\vartheta =0$ and $\gamma =c/\sqrt{n}$ where c is a constant that does not depend on n nor T, OGA leads to a regret in $\mathcal{O}\left(\sqrt{n}\right)$. After T tasks, learning in isolation thus leads to a regret in $T\sqrt{n}$. Our strategies with $\beta =1$ lead to a regret in

$$n^2\sqrt{T}+\left(1+\sigma \left({\theta }_1^T\right)\sqrt{n}\right)T.$$

(15)

The term $n^2\sqrt{T}$ is the price to pay for meta-learning. In the regime we are interested in (small n, large T), which is smaller than $T\sqrt{n}$. Consider the leading term. In the worst case scenario, this is also $T\sqrt{n}$. However, there are good predictors ${\theta }_1,\dots ,{\theta }_T$ for tasks $1,\dots ,T$, respectively, such that $\sigma \left({\theta }_1^T\right)$ is small, and in this case we see the improvement with respect to learning in isolation. The extreme case is when there is a good predictor ${\theta }^{*}$ that predicts well for all tasks. In this case, regret with respect to ${\theta }_1=\dots ={\theta }_T={\theta }^{*}$ is in $n^2\sqrt{T}+T$, which improves significantly on learning in isolation. Note however that, using a different meta-strategy, specifically designed for OGA, Ref. [29] obtain a better dependence on T when $\sigma \left({\theta }_1^T\right)=0$.

Let us now discuss the implementation of our meta-stategy. We first remark that under the quadratic loss, it is possible to derive a formula for ${\mathcal{L}}_t$, which allows to use OGMS. We then discuss OPMS for the general case.

4.2. Special Case: Quadratic Loss

First, consider ${\ell }_{t,i}={(y_{t,i}-x_{t,i}^T\theta )}^2$ for some $y_{t,i}\in \mathbb{R}$ and $x_{t,i}\in {\mathbb{R}}^d$. Assumption 2 is satisfied if we assume, moreover that all $|y_{t,i}|\le c$ and $\parallel x_{t,i}\parallel \le b$, with $\mathsf{\Gamma }=2bc+2b^{2}C$. In this case,

$${\mathcal{L}}_t\left((\vartheta ,\gamma )\right)=\underset{\parallel \theta \parallel \le C}{inf}\left\{\sum _{i=1}^n{(y_{t,i}-x_{t,i}^T\theta )}^2+\frac{\gamma {\mathsf{\Gamma }}^{2}n}{2}+\frac{{\parallel \theta -\vartheta \parallel }^2}{2\gamma }\right\}.$$

(16)

Define $Y_t={(y_{t,1},\dots ,y_{t,n})}^T$ and $X_t=(x_{t,1}|\dots |x_{t,n}{)}^T$. The minimizer of ${\sum }_{i=1}^n{(y_{t,i}-x_{t,i}^T\theta )}^2+{\parallel \theta -\vartheta \parallel }^2/\left(2\gamma \right)$ with respect to $\theta$ is known as the ridge regression estimator:

$${\widehat{\theta }}_t={\left(X_t^T{X}_t+\frac{I_d}{2\gamma }\right)}^{-1}\left(X_t^T{Y}_t+\frac{\vartheta }{2\gamma }\right).$$

(17)

This also coincides with the minimizer in the right-hand side of (16) on the condition that $\parallel {\widehat{\theta }}_t\parallel \le C$. In this case, by plugging ${\widehat{\theta }}_t$ in (16), we have a close form formula for ${\mathcal{L}}_t\left((\vartheta ,\gamma )\right)$, and an explicit (but cumbersome) formula for its gradient. It is thus possible to use the OGMS strategy to update $\lambda =(\vartheta ,\gamma )$.

4.3. The General Case

In the general case, denote ${\lambda }_{t-1}=({\vartheta }_{t-1},{\gamma }_{t-1})$, then ${\lambda }_t=({\vartheta }_t,{\gamma }_t)$ is obtained by minimizing

$$F_t(\theta ,(\vartheta ,\gamma ))=\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\gamma {\mathsf{\Gamma }}^{2}n}{2}+\frac{{\parallel \theta -\vartheta \parallel }^2}{2\gamma }+\frac{\parallel \vartheta -{\vartheta }_{t-1}{\parallel }^2+{(\gamma -{\gamma }_{t-1})}^2}{2\alpha }$$

(18)

with respect to $\theta ,\vartheta ,\gamma$. Any efficient minimization procedure can be used. In our experiments, we used a projected gradient descent, the gradient being given by:

$$\begin{array}{ll}\frac{\partial F_t}{\partial \theta }& =\sum _{i=1}^n\nabla {\ell }_{t,i}\left(\theta \right)+\frac{\theta -\vartheta }{\gamma },\end{array}$$

(19)

$$\begin{array}{ll}\frac{\partial F_t}{\partial \vartheta }& =\frac{\vartheta -\theta }{\gamma }+\frac{\vartheta -{\vartheta }_{t-1}}{\alpha },\end{array}$$

(20)

$$\begin{array}{ll}\frac{\partial F_t}{\partial \gamma }& =\frac{{\mathsf{\Gamma }}^{2}n}{2}-\frac{{\parallel \theta -\vartheta \parallel }^2}{2{\gamma }^2}+\frac{\gamma -{\gamma }_{t-1}}{\alpha }.\end{array}$$

(21)

Note that even though we do not stricto sensu obtain the minimizer of $F_t$, we can get arbitrarily close to it by taking a large enough number of steps. The main difference between this algorithm and the strategy suggested in [29] is that it is obtained by applying the general proximal update introduced in Equation (7), while they decoupled the update for the initialization step and the learning rate.

4.4. Experimental Study

In this section we compare simulated data for the numerical performance of OPMS w.r.t learning the task in isolation with online gradient descent (I-OGA). To measure the impact of learning the gradient step $\gamma$, we also introduce mean-OPMS that uses the same strategy as OPMS but only learns the starting point $\vartheta$ (it is thus close to [27]). We present the results for regression tasks with the mean-squared-error loss, and then for classification with the hinge loss. The notebooks of the experiments can be found online: https://dimitri-meunier.github.io/ (accessed on 26 September 2021).

4.4.1. Synthetic Regression

At each round $t=1,\dots ,T$, the meta learner sequentially receives a regression task that corresponds to a dataset ${(x_{t,i},y_{t,i})}_{i=1,\dots ,n}$ generated as $y_{t,i}=x_{t,i}^T{\theta }_t+{ϵ}_{t,i}$, $x_{t,i}\in {\mathbb{R}}^d$. The noise is ${ϵ}_{t,i}\sim \mathcal{U}\left([-{\sigma }^2,{\sigma }^2]\right)$ and the ${ϵ}_{t,i}$ are all independent, the inputs are uniformly sampled on the $(d-1)$-unit sphere ${\mathcal{S}}^{d-1}$ and ${\theta }_t=ru+{\theta }_0$, $u\sim \mathcal{U}\left({\mathcal{S}}^{d-1}\right)$, ${\theta }_0\in {\mathbb{R}}^d$, $r\in {\mathbb{R}}_{+}$. We take $d=20$, $n=30$, $T=200$, ${\sigma }^2=0.5$ and ${\theta }_0$ with all components equal to 5. In this setting, ${\theta }_0$ is a common bias between the tasks, ${\sigma }^2$ is the inter-task variance and r characterizes the tasks similarity. We experiment with different values of $r\in \{0,5,10,30\}$ to observe the impact of task similarity on the meta-learning process. The smaller r, the closer are the tasks and for the extreme case of $r=0$ the tasks are identical, in the sense that the parameters ${\theta }_t$ of the tasks are all the same. We draw attention to the fact that a cross-validation procedure to select $\alpha$ (the parameter of OGMS or OPMS, see Equation (5)) or $\gamma$ is not valid in the online settings, as it would require having knowledge of several tasks in advance for the former and several datapoints in advance for each task for the latter. Moreover, the theoretical values are based on worst-case analysis and lead in practice to slow learning. In practice, to set these values to the correct order of magnitude without adjusting the constants led to better results. So, for mean-OPMS and OPMS we set $\alpha =1/\sqrt{T}$, for OPMS and I-OGA we set $\gamma =1/\sqrt{n}$. Instead of cross-validation, one can launch several online learners in parallel with different parameter values to pick the best one (or aggregate them). That is the strategy we use to select $\mathsf{\Gamma }$ for OPMS. Note that the exact value of $\mathsf{\Gamma }$ is usually unkown in practice; its automatic calibration is an important open question. To solve (18), after each task we use the exact solution for mean-OPMS and projected Newton descent with 10 steps for OPMS. We observed that not reaching the exact solution of (18) does not harm the performance of the algorithm and 10 steps are sufficient to reach convergence. The results are displayed in

Table 1. Average end-of-task MSE of the 100 last tasks (averaged over 50 independent runs).

	r = 0	r = 5	r = 10	r = 30
I-OGA	6.24	6.44	7.06	13.60
mean OPMS	0.05	0.27	0.93	7.93
OPMS	0.07	0.15	0.49	3.72

and Figure 2. On Figure 2, for each task $t=1,\dots ,T$, we report the average end-of-task loss $MS{E}_t={\sum }_{i=1}^n{\ell }_{t,i}\left({\theta }_{t,n}\right)/n$ averaged over 50 independent runs (with their confidence intervals). Table 1 reports $MS{E}_t$ averaged over the 100 most recent tasks. The results confirm our theoretical findings: learning $\gamma$ can bring a substantial benefit over just learning the starting point, which in turn brings a considerable benefit with respect to learning the tasks in isolation. Learning the gradient step makes the meta-learner more robust to task dissimilarities (i.e. when r increases) as shown in Figure 2. In the regime where r is low, learning the gradient step does not help the meta-learner as it takes more steps to reach convergence. Overall both meta learners are consistently better than learning the task in isolation since the number of observation per task is low.

4.4.2. Synthetic Classification

At each round $t=1,\dots ,T$, the meta learner sequentially receives a binary classification task with the Hinge loss that corresponds to a dataset ${(x_{t,i},y_{t,i})}_{i=1,\dots ,n}$. The binary labels $\{-1,1\}$ are generated as a logistic model $\mathbb{P}(y=1)={(1+exp(-x^t{\theta }_t))}^{-1}$. The task parameters ${\theta }_t$ and the inputs are generated as in the regression setting. To add some noise, we shuffle $10\%$ of the labels. We take $d=10$, $n=100$, $T=500$, $r=2$. For mean-OPMS and OPMS we set $\alpha =1/\sqrt{T}$, for OPMS and I-OGA we set $\gamma =1/\sqrt{n}$. For the optimisation of $F_t$ (18) with both OPMS and mean-OPMS we use a projected gradient descent with 50 steps.

On Figure 3, for each task $t=1,\dots ,T$, we report the regret on the end-of-task losses: $R\left(t\right)=\frac{1}{nt}{\sum }_{k=1}^t{\sum }_{i=1}^n{\ell }_{k,i}\left({\theta }_{k,n}\right)$, averaged over 10 independent runs (with their confidence intervals). As the for regression setting, the results confirm our theoretical findings: by learning $\gamma$ (OPMS), we reach a better overall performance than just learning the initialization (mean-OPMS) and a substantially stronger than independent task learning (I-OGA). Note that, in the classification regime, there is no known closed formed expression for the meta-gradient; therefore, OGMS cannot be used.

5. Second Example: Learning the Prior or the Learning Rate in Exponentially Weighted Aggregation

In this section, we will study a generalized Bayesian method, exponentially weighted aggregation. Consider a finite set ${\Theta }_0=\{{\theta }_1,\dots ,{\theta }_M\}\subset {\mathbb{R}}^d$. EWA depends on a prior distribution $\pi$ on ${\Theta }_0$, and on a learning rate $\eta >0$, and returns a decision in $\Theta =\mathrm{conv}({\theta }_1,\dots ,{\theta }_M)$ the convex envelope of ${\Theta }_0$. In this section, we work under the following condition.

Assumption 3.

There is a $B\in {\mathbb{R}}_{+}^{*}$, such that for any $(t,i)\in \{1,\dots ,T\}\times \{1,\dots ,n\}$, the function ${\ell }_{t,i}$ is $\Theta \to [0,B]$ and convex.

We will sometimes use a stronger assumption.

Assumption 4.

There is a $C\in {\mathbb{R}}_{+}^{*}$, such that for any $(t,i)\in \{1,\dots ,T\}\times \{1,\dots ,n\}$, the function $\theta \mapsto exp(-{\ell }_{t,i}\left(\theta \right)/C)$ is concave.

Examples of a situation in which Assumption 4 is satisfied are provided in [3]. Note that Assumption 4 implies Assumption 3.

5.1. Reminder on EWA

The update in EWA is given by:

$${\theta }_{t,i}=\sum _{\theta \in {\Theta }_0}{p}_{t,i}\left(\theta \right)\theta$$

(22)

where $p_{t,i}$ are weights defined by

$$p_{t,i}\left(\theta \right)=\frac{exp\left[-\eta {\sum }_{j=1}^{i-1}{\ell }_{t,j}\left(\theta \right)\right]\pi \left(\theta \right)}{{\sum }_{\vartheta \in {\Theta }_0}exp\left[-\eta {\sum }_{j=1}^{i-1}{\ell }_{t,j}\left(\vartheta \right)\right]\pi \left(\vartheta \right)}.$$

(23)

The strategy is studied in detail in [3]. We refer the reader to [36] and the references therein for connections to Bayesian inference. We recall the following regret bounds from [3]. First, under Assumption 3,

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\eta n{B}^2}{8}+\frac{log\frac{1}{\pi \left(\theta \right)}}{\eta }\right].$$

(24)

Moreover, under the stronger Assumption 4,

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+Clog\frac{1}{\pi \left(\theta \right)}\right].$$

(25)

In Section 5.2, we work in the general setting (Assumption 3), and we use our meta-strategy OPMS or OGMS to learn $\eta$. In Section 5.3, we use OPMS or OGMS to learn $\pi$ under Assumption 4.

5.2. Learning the Rate $\eta$

Consider the uniform prior $\pi \left(\theta \right)=1/M$ for any $\theta \in {\Theta }_0$. Then, the regret bound (24) becomes:

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\eta n{B}^2}{8}+\frac{logM}{\eta }$$

(26)

and it is then possible to optimize it explicitly with respect to $\eta$. The value minimizing the bound is $\eta =(2/B)\sqrt{2log\left(M\right)/n}$ and the regret bound becomes:

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+B\sqrt{\frac{nlogM}{2}}.$$

(27)

In practice, however, while it is often reasonable to assume that the loss function is bounded (as in Assumption 3), very often one does not know a tight upper bound. Thus, one may use a constant B that satisfies Assumption 3, but that is far too large. Even though one does not know a better upper bound than B, one would like a regret bound that depends on the tightest possible upper bound.

In the meta-learning framework, define:

$${\mathcal{L}}_t\left(\eta \right)=\underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\eta n{\left[{max}_{\vartheta \in {\Theta }_0,1\le i\le n}{\ell }_{t,i}\left(\vartheta \right)\right]}^2}{8}+\frac{logM}{\eta }$$

(28)

for $\eta \in \mathsf{\Lambda }=[1/n,1]$. It is immediately necessary to prove that this function is convex and L-Lipschitz with $L=n^{2}log\left(M\right)+n{B}^2/8$. So, Assumption 1 is satisfied, allowing for the use of the OPMS or OGMS strategy without needed a tight upper bound on the losses. Note that, in this context, the OGMS strategy is given by:

$${\eta }_t=\frac{1}{n}\vee \left[{\eta }_{t-1}-\alpha \left(\frac{n{\left[{max}_{\theta \in {\Theta }_0,1\le i\le n}{\ell }_{t,i}\left(\theta \right)\right]}^2}{8}-\frac{logM}{{\eta }_{t-1}^2}\right)\right]\wedge 1.$$

Theorem 2.

Under Assumption 3, using OGMS or OPMS on ${\mathcal{L}}_t\left(\eta \right)$, as in (28) with ${\eta }_1=1$, $L=n^{2}log\left(M\right)+n{B}^2/8$ and

$$\alpha =\frac{1}{L}\sqrt{\frac{2}{T}}$$

(29)

we have

$$\begin{array}{ll}{\displaystyle \sum _{t=1}^T}{\displaystyle \sum _{i=1}^n}{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le {\displaystyle \sum _{t=1}^T}\underset{\theta \in {\Theta }_0}{min}{\displaystyle \sum _{i=1}^n}{\ell }_{t,i}\left(\theta \right)& +bT\sqrt{\frac{nlog\left(M\right)}{2}}\\ & +Tlog\left(M\right)+\frac{b^{2}T}{8}+\left(n^{2}logM+\frac{n{B}^2}{8}\right)\sqrt{2T}\end{array}$$

(30)

where

$$b=\underset{\theta \in {\Theta }_0,1\le t\le T,1\le i\le n}{max}\left|{\ell }_{t,i}\left(\theta \right)\right|.$$

(31)

Let us compare learning in isolation with meta-learning in this context. When learning in isolation, the hyperparameter $\eta$ is fixed (as in (2)). If we fix it to the value ${\eta }_0=(2/B)\sqrt{2log\left(M\right)/n}$ as in (27), the meta-regret is in $BT\sqrt{nlog\left(M\right)/2}$. On the other hand, meta-learning leads to a meta-regret in $bT\sqrt{nlog\left(M\right)/2}+n^{2}logM\sqrt{2T}+\mathcal{O}(n{B}^2\sqrt{T}+T)$. In other words, we replace the potentially loose upper bound B by the tightest possible bound b, at the cost of an additional $n^{2}logM\sqrt{2T}+\mathcal{O}(n{B}^2\sqrt{T}+T)$ term. Here again, when T is large enough with respect to n, this term is negligible.

5.3. Learning the Prior $\pi$

Under Assumption 4, we have the regret bound in (25). Without any information on ${\Theta }_0$, it seems natural to use the uniform prior $\pi$ on ${\Theta }_0=\{{\theta }_1,\dots ,{\theta }_M\}$, which leads to

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+ClogM.$$

(32)

If some additional information was available, such as, for example: “the best $\theta$ is always either ${\theta }_1$ or ${\theta }_2$”, one would rather chose the uniform prior on $\{{\theta }_1,{\theta }_2\}$, and obtain the bound:

$$\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}\right)\le \underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+Clog2.$$

(33)

Unfortunately, such information is generally not available. However, in the context of meta-learning, we can take advantage of the previous tasks to learn such information.

Thus, let us define, for any task t,

$${\theta }_t^{*}=\underset{\theta \in {\Theta }_0}{argmin}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)$$

(34)

and

$${\mathcal{L}}_t\left(\pi \right)=\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t^{*}\right)+Clog\frac{1}{\pi \left({\theta }_t^{*}\right)}$$

(35)

for $\pi =(\pi \left({\theta }_1\right),\dots ,\pi \left({\theta }_M\right))\in \mathsf{\Lambda }$ with

$$\mathsf{\Lambda }=\left\{x\in {\left({\mathbb{R}}_{+}\right)}^M:\sum _{h=1}^M{x}_h=1\mathrm{and}{x}_h\ge \frac{1}{2M}\right\}.$$

(36)

It is important to check that ${\mathcal{L}}_t$ is convex and L-Lipschitz with $L=2CM$ on $\mathsf{\Lambda }$; this allows us to use OPMS (or OGMS).

Theorem 3.

Under Assumption 4, using OPMS on ${\mathcal{L}}_t\left(\pi \right)$ as in (35) with ${\pi }_1=(1/M,\dots ,1/M)$, $L=2CM$ and

$$\alpha =\frac{1}{2CM\sqrt{T}},$$

(37)

define $I^{*}=\{{\theta }_1^{*},\dots ,{\theta }_T^{*}\}$ where each ${\theta }_t^{*}$ is as in (34) and $m^{*}=\mathrm{card}\left(I^{*}\right)$. We have

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\pi }_t}\right)\le \sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t^{*}\right)+CTlog\left(2m^{*}\right)+2CM\sqrt{T}.$$

(38)

When learning in isolation with a uniform prior, the meta-regret is $TClog\left(M\right)$. On the other hand, if $m^{*}$ is small (that is, many of the ${\theta }_i^{*}$s are similar), meta-learning leads to a meta-regret in $CTlog\left(2m^{*}\right)+2CM\sqrt{T}$. For a T that is large enough, this is an important improvement.

5.4. Discussion on the Continuous Case

Let us now discuss the possibility of meta-learning for generalized Bayesian methods when ${\Theta }_0$ is no longer a finite set. There is a general formula for EWA, given by

$${\rho }_{t,i}\left(\mathrm{d}\theta \right)=\underset{\rho }{argmin}\left\{{\mathbb{E}}_{\theta \sim \rho }\left[\sum _{j=1}^{i-1}{\ell }_{t,j}\left(\theta \right)\right]+\frac{\mathcal{K}(\rho ,\pi )}{\eta }\right\}$$

(39)

where the minimum is taken over for all probability distributions that are absolutely continuous with $\pi$, and where $\pi$ is a prior distribution, $\eta >0$ a learning rate and $\mathcal{K}$ is the Kullback–Leibler divergence (KL). Meta-learning for such an update rule is proven in [10,37] but usually does not lead to feasible strategies. Online variational inference [38,39] consists in replacing the minimization on the set of all probability distributions by minimization in a smaller set in order to define a feasible approximation of ${\rho }_{t,i}$. For example, let ${\left(q_{\mu }\right)}_{\mu \in M}$ be a parametric family of probability distributions, Thus, we define:

$${\mu }_{t,i}=\underset{\mu \in M}{argmin}\left\{{\mathbb{E}}_{\theta \sim q_{\mu }}\left[\sum _{j=1}^{i-1}{\ell }_{t,j}\left(\theta \right)\right]+\frac{\mathcal{K}(q_{\mu },\pi )}{\eta }\right\}.$$

(40)

It is discussed in [40] that, generally, when $\mu$ is a location-scale parameter and ${\ell }_{t,j}$ is $\mathsf{\Gamma }$-Lipschitz and convex, then ${\overline{\ell }}_{t,i}\left(\mu \right):={\mathbb{E}}_{\theta \sim q_{\mu }}\left[{\ell }_{t,j}\left(\theta \right)\right]$ is $2\mathsf{\Gamma }$-Lipschitz and convex. In this case, under the assumption that $\mathcal{K}(q_{\mu },\pi )$ is $\alpha$-strongly convex in $\mu$, a regret bound for such strategies was derived in [39]:

$$\sum _{i=1}^n{\mathbb{E}}_{\theta \sim q_{{\mu }_{t,i}}}\left[{\ell }_{t,i}\left(\theta \right)\right]\le \underset{\mu \in \mathcal{M}}{inf}\left\{{\mathbb{E}}_{\theta \sim q_{\mu }}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)\right]+\frac{\eta 4{\mathsf{\Gamma }}^{2}n}{\alpha }+\frac{\mathcal{K}(q_{\mu },\pi )}{\eta }\right\}.$$

(41)

A complete study of meta-learning of the rate $\eta >0$ and of the prior $\pi$ in this context is an important objective (possibly, with a restriction that $\pi \in \{q_{\mu },\mu \in M\}$). However, this raises many problems. For example, the KL divergence $\mathcal{K}(q_{\mu },q_{{\mu }^{\prime }})$ is not always convex with respect to the parameter ${\mu }^{\prime }$. In this case, it might help to replace it by a convex relaxation that would allow for the use of OGMS or OPMS. This relates to [41,42], who advocate going beyond the KL divergence in (39); see also [36] and the references therein. This will be the object of future works.

6. Proofs

We start with a preliminary lemma that will be used in the proof of Proposition 1.

Lemma 1.

Let $a,b,c$ be three vectors in ${\mathbb{R}}^p$. Then:

$${(a-b)}^T(b-c)=\frac{{\parallel a-c\parallel }^2{-\parallel a-b\parallel }^2-{\parallel b-c\parallel }^2}{2}.$$

(42)

Proof. 

expand ${\parallel a-c\parallel }^2={\parallel a\parallel }^2+{\parallel c\parallel }^2-2a^{T}c$ in the r.h.s, as well as ${\parallel a-b\parallel }^2$ and ${\parallel b-c\parallel }^2$. Then simplify. □

We now prove Proposition 1 separately for the general OGMS strategy, and then for OGMS.

Proof of Proposition 1 for OPMS.

As mentioned earlier, this strategy is an application to the meta-learning setting of implicit online learning [32,33]. We follow here a proof from Chapter 11 in [3]. We refer the reader to [43] and the references therein for tighter bounds under stronger assumptions.

First, ${\lambda }_t$ is defined as the minimizer of a convex function in (5). So, the subdifferential of this function at ${\lambda }_t$ contains 0. In other words, there is a $z_t\in \partial {\mathcal{L}}_{t-1}\left({\lambda }_t\right)$, such that

$$z_t=\frac{{\lambda }_{t-1}-{\lambda }_t}{\alpha }.$$

(43)

By convexity, for any $\lambda$, for any $z\in \partial {\mathcal{L}}_{t-1}\left({\lambda }_t\right)$,

$${\mathcal{L}}_{t-1}\left(\lambda \right)\ge {\mathcal{L}}_{t-1}\left({\lambda }_t\right)+{(\lambda -{\lambda }_t)}^{T}z.$$

(44)

The choice $z=z_t$ gives:

$${\mathcal{L}}_{t-1}\left(\lambda \right)\ge {\mathcal{L}}_{t-1}\left({\lambda }_t\right)+\frac{{(\lambda -{\lambda }_t)}^T({\lambda }_{t-1}-{\lambda }_t)}{\alpha },$$

(45)

that is,

$$\begin{array}{ll}{\mathcal{L}}_{t-1}\left({\lambda }_t\right)& \le {\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{{(\lambda -{\lambda }_t)}^T({\lambda }_t-{\lambda }_{t-1})}{\alpha }\\ & ={\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }-\frac{\parallel {\lambda }_t-{\lambda }_{t-1}{\parallel }^2}{2\alpha }\\ & ={\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }-\alpha \frac{\parallel z_t{\parallel }^2}{2}\end{array}$$

(46)

where we used Lemma 1. Then, note that

$$\begin{array}{ll}{\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)& ={\mathcal{L}}_{t-1}\left({\lambda }_t\right)+[{\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)-{\mathcal{L}}_{t-1}\left({\lambda }_t\right)]\\ & \le {\mathcal{L}}_{t-1}\left({\lambda }_t\right)+\parallel {\lambda }_{t-1}-{\lambda }_t\parallel L\\ & \le {\mathcal{L}}_{t-1}\left({\lambda }_t\right)+\alpha \parallel z_t\parallel L.\end{array}$$

(47)

Combining this inequality with (46) gives

$${\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\le {\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }+\alpha \left(\parallel z_t\parallel L-\frac{\parallel z_t{\parallel }^2}{2}\right).$$

(48)

Now, for any $x\in \mathbb{R}$, $-x^2/2+xL-L^2/2\le 0$. In particular, $\parallel z_t\parallel L-\parallel z_t{\parallel }^2/2\le L^2/2$ and so the above can be rewritten:

$${\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\le {\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }+\frac{\alpha L^2}{2}.$$

(49)

Summing the inequality for $t=2$ to $T+1$ leads to:

$$\sum _{t=1}^T{\mathcal{L}}_t\left({\lambda }_t\right)\le \sum _{t=1}^T{\mathcal{L}}_t\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_1{\parallel }^2-{\parallel \lambda -{\lambda }_{T+1}\parallel }^2}{2\alpha }+\frac{\alpha T{L}^2}{2}.$$

(50)

This ends the proof. □

Proof of Proposition 1 for OGMS.

The beginning of the proof follows the proof of Theorem 11.1 in [3].

Note that we can rewrite (4) as

$$\left\{\begin{array}{c}{\tilde{\lambda }}_t={\lambda }_{t-1}-\alpha \nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\\ {\lambda }_t={\mathsf{\Pi }}_{\mathsf{\Lambda }}\left({\tilde{\lambda }}_t\right)\end{array}\right.$$

rearranging the first line, we obtain:

$$\nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)=\frac{{\lambda }_{t-1}-{\tilde{\lambda }}_t}{\alpha }.$$

(51)

By convexity, for any $\lambda$,

$${\mathcal{L}}_{t-1}\left(\lambda \right)\ge {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)+{(\lambda -{\lambda }_{t-1})}^T\nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)$$

(52)

$$\begin{array}{ll}& ={\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)+\frac{{(\lambda -{\lambda }_{t-1})}^T({\lambda }_{t-1}-{\tilde{\lambda }}_t)}{\alpha },\end{array}$$

(53)

that is,

$${\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\le {\mathcal{L}}_{t-1}\left(\lambda \right)-\frac{{(\lambda -{\lambda }_{t-1})}^T({\lambda }_{t-1}-{\tilde{\lambda }}_t)}{\alpha }.$$

(54)

Lemma 1 gives:

$$\begin{array}{ll}{(\lambda -{\lambda }_{t-1})}^T({\lambda }_{t-1}-{\tilde{\lambda }}_t)& =\frac{\parallel \lambda -{\tilde{\lambda }}_t{\parallel }^2-\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel {\lambda }_{t-1}-{\tilde{\lambda }}_t\parallel }^2}{2}\end{array}$$

$$\begin{array}{ll}& =\frac{\parallel \lambda -{\tilde{\lambda }}_t{\parallel }^2-\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\alpha }^2{\parallel \nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\parallel }^2}{2}\end{array}$$

(55)

$$\begin{array}{ll}& \ge \frac{\parallel \lambda -{\lambda }_t{\parallel }^2-\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\alpha }^2{\parallel \nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\parallel }^2}{2},\end{array}$$

(56)

the last step being justified by:

$$\parallel \lambda -{\tilde{\lambda }}_t{\parallel }^2\ge \parallel \lambda -{\mathsf{\Pi }}_{\mathsf{\Lambda }}\left({\tilde{\lambda }}_t\right){\parallel }^2={\parallel \lambda -{\lambda }_t\parallel }^2$$

(57)

for any $\lambda \in \mathsf{\Lambda }$. Plug (55) in (54) to get:

$${\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\le {\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }+\frac{\alpha \parallel \nabla {\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right){\parallel }^2}{2}$$

(58)

and the Lipschitz assumption gives:

$${\mathcal{L}}_{t-1}\left({\lambda }_{t-1}\right)\le {\mathcal{L}}_{t-1}\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_{t-1}{\parallel }^2-{\parallel \lambda -{\lambda }_t\parallel }^2}{2\alpha }+\frac{\alpha L^2}{2}$$

(59)

sum the inequality for $t=2$ to $T+1$ to get:

$$\sum _{t=1}^T{\mathcal{L}}_t\left({\lambda }_t\right)\le \sum _{t=1}^T{\mathcal{L}}_t\left(\lambda \right)+\frac{\parallel \lambda -{\lambda }_1{\parallel }^2-{\parallel \lambda -{\lambda }_{T+1}\parallel }^2}{2\alpha }+\frac{\alpha T{L}^2}{2}.$$

(60)

This ends the proof of the statement for OGMS. □

We now provide a lemma that will be useful for the proof of Proposition 2.

Lemma 2.

Let $G(u,v)$ be a convex function of $(u,v)\in U\times V$. Define $g\left(u\right)={inf}_{v\in V}G(u,v)$. Then g is convex.

Proof. 

indeed, let $\lambda \in [0,1]$ and $(x,y)\in U^2$,

$$\begin{array}{ll}g(\lambda x+(1-\lambda \left)y\right)& =\underset{v\in V}{inf}G(\lambda x+(1-\lambda )y,v)\end{array}$$

(61)

$$\begin{array}{ll}& \le G(\lambda x+(1-\lambda )y,\lambda x^{\prime }+(1-\lambda )y^{\prime })\end{array}$$

(62)

$$\begin{array}{ll}& \le \lambda G(x,x^{\prime })+(1-\lambda )G(y,y^{\prime })\end{array}$$

(63)

where the last two inequalities hold for any $(x^{\prime },y^{\prime })\in V^2$. Let us now take the infimum with respect to $(x^{\prime },y^{\prime })\in V^2$ in both sides, this gives:

$$g(\lambda x+(1-\lambda )y)\le \underset{x^{\prime }\in V}{inf}\lambda G(x,x^{\prime })+\underset{y^{\prime }\in V}{inf}(1-\lambda )G(y,y^{\prime })$$

(64)

$$\begin{array}{ll}& =\lambda g\left(x\right)+(1-\lambda )g\left(y\right),\end{array}$$

(65)

that is, g is convex. □

Proof of Proposition 2.

Apply Lemma 2 to $u=(\vartheta ,\gamma )$, $v=\theta$, $U=\mathsf{\Lambda }$, $V=\Theta$ and

$$G(u,v)=\sum _{i=1}^n{\ell }_{i,t}\left(\theta \right)+\frac{\gamma {\mathsf{\Gamma }}^{2}n}{2}+\frac{{\parallel \vartheta -\theta \parallel }^2}{2\gamma }.$$

(66)

This shows $g\left(u\right)={\mathcal{L}}_t\left((\vartheta ,\gamma )\right)$ is convex with respect $(\vartheta ,\gamma )$. Additionally, G is differentiable w.r.t $u=(\vartheta ,\gamma )$, so

$$\frac{\partial G}{\partial \vartheta }=\frac{\vartheta -\theta }{\gamma },\mathrm{and}\frac{\partial G}{\partial \gamma }=\frac{n{\mathsf{\Gamma }}^2}{2}-\frac{{\parallel \vartheta -\theta \parallel }^2}{2{\gamma }^2}.$$

(67)

As a consequence, for $(\theta ,\vartheta )\in {\Theta }^2$ and $\underline{\gamma }\le \gamma \le \overline{\gamma }$,

$${∥\frac{\partial G}{\partial \vartheta }∥}^2\le \frac{4C^2}{{\underline{\gamma }}^2},\mathrm{and}{\left|\frac{\partial G}{\partial \gamma }\right|}^2\le \frac{n^2{\mathsf{\Gamma }}^4}{4}+\frac{4C^4}{{\underline{\gamma }}^4}.$$

(68)

This leads to

$$\begin{array}{ll}\parallel {\nabla }_{u}G(u,v)\parallel & =\sqrt{{∥\frac{\partial G}{\partial \vartheta }∥}^2+{\left|\frac{\partial G}{\partial \gamma }\right|}^2}\end{array}$$

(69)

$$\begin{array}{ll}& \le \sqrt{\frac{n^2{\mathsf{\Gamma }}^4}{4}+\frac{4C^2}{{\underline{\gamma }}^2}+\frac{4C^4}{{\underline{\gamma }}^4}}=:L,\end{array}$$

(70)

that is, for each v, $G(u,v)$ is L-Lipschitz in u. So, $g\left(u\right)={inf}_{v\in V}G(u,v)$ is L-Lipschitz in u. □

Proof of Theorem 1.

Thanks to the Assumption 2, we can apply Proposition 2. That is, Assumption (A1) is satisfied, and we can apply Proposition 1. This gives:

$$\begin{array}{ll}\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le & \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\underset{(\vartheta ,\gamma )\in \mathsf{\Lambda }}{inf}\left\{\sum _{t=1}^T\right[\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)\\ & +\frac{\gamma {\mathsf{\Gamma }}^{2}n}{2}+\frac{\parallel {\theta }_t{-\vartheta \parallel }^2}{2\gamma }]+\frac{\alpha T{L}^2}{2}+\frac{\parallel \vartheta -{\vartheta }_1{\parallel }^2+{|\gamma -{\gamma }_1|}^2}{2\alpha }\}.\end{array}$$

(71)

We use direct bounds for the last two terms: $\parallel \vartheta -{\vartheta }_1{\parallel }^2\le 4C^2$ and $|\gamma -{\gamma }_1{|}^2\le {|\overline{\gamma }-\underline{\gamma }|}^2\le {\overline{\gamma }}^2=C^4$. Then note that

$$\begin{array}{ll}\sum _{t=1}^T{\parallel {\theta }_t-\vartheta \parallel }^2& =T{∥\vartheta -\frac{1}{T}\sum _{s=1}^T{\theta }_s∥}^2+\sum _{t=1}^T{∥{\theta }_t-\frac{1}{T}\sum _{s=1}^T{\theta }_s∥}^2\end{array}$$

(72)

$$\begin{array}{ll}& =T{∥\vartheta -\frac{1}{T}\sum _{s=1}^T{\theta }_s∥}^2+T{\sigma }^2\left({\theta }_1^T\right).\end{array}$$

(73)

Upper bounding the infimum on $\vartheta$ in (71) by $\vartheta =\frac{1}{T}{\sum }_{s=1}^T{\theta }_s$ leads to

$$\begin{array}{ll}\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le & \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\underset{\gamma \in [\underline{\gamma },\overline{\gamma }]}{inf}\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+\frac{\gamma {\mathsf{\Gamma }}^{2}nT}{2}\\ & +\frac{T{\sigma }^2\left({\theta }_1^T\right)}{2\gamma }+\frac{\alpha T{L}^2}{2}+\frac{C^2(4+C^2)}{2\alpha }\}.\end{array}$$

(74)

The right-hand side of (74) is minimized with respect to $\alpha$ if $\alpha =\frac{C}{L}\sqrt{\frac{4+C^2}{T}}$, which is the value proposed in the theorem, and we obtain:

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)\le \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\underset{\gamma \in [\underline{\gamma },\overline{\gamma }]}{inf}\left\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+\frac{\gamma {\mathsf{\Gamma }}^{2}nT}{2}+\frac{T{\sigma }^2\left({\theta }_1^T\right)}{2\gamma }+CL\sqrt{(4+C^2)T}\right\}.$$

(75)

The infimum with respect to $\gamma$ in the r.h.s is reached for

$${\gamma }^{*}=\left(\underline{\gamma }\vee \frac{\sigma \left({\theta }_1^T\right)}{\mathsf{\Gamma }\sqrt{n}}\right)\wedge \overline{\gamma }.$$

(76)

First, note that

$$\begin{array}{ll}\frac{{\gamma }^{*}{\mathsf{\Gamma }}^{2}nT}{2}& \le \left(\underline{\gamma }\vee \frac{\sigma \left({\theta }_1^T\right)}{\mathsf{\Gamma }\sqrt{n}}\right)\frac{{\mathsf{\Gamma }}^{2}nT}{2}\end{array}$$

(77)

$$\begin{array}{ll}& \le \left(\underline{\gamma }+\frac{\sigma \left({\theta }_1^T\right)}{\mathsf{\Gamma }\sqrt{n}}\right)\frac{{\mathsf{\Gamma }}^{2}nT}{2}\end{array}$$

(78)

$$\begin{array}{ll}& =\frac{{\mathsf{\Gamma }}^{2}T{n}^{1-\beta }}{2}+\frac{\sigma \left({\theta }_1^T\right)\mathsf{\Gamma }T\sqrt{n}}{2},\end{array}$$

(79)

using $\underline{\gamma }=n^{-\beta }$. Then,

$$\begin{array}{ll}\frac{T{\sigma }^2\left({\theta }_1^T\right)}{2{\gamma }^{*}}& \le \frac{T{\sigma }^2\left({\theta }_1^T\right)}{2}\left(\frac{1}{\overline{\gamma }}\vee \frac{\mathsf{\Gamma }\sqrt{n}}{\sigma \left({\theta }_1^T\right)}\right)\end{array}$$

(80)

$$\begin{array}{ll}& \le \frac{T{\sigma }^2\left({\theta }_1^T\right)}{2}\left(\frac{1}{\overline{\gamma }}+\frac{\mathsf{\Gamma }\sqrt{n}}{\sigma \left({\theta }_1^T\right)}\right)\end{array}$$

(81)

$$\begin{array}{ll}& =\frac{T{\sigma }^2\left({\theta }_1^T\right)}{2C^2}+\frac{\sigma \left({\theta }_1^T\right)\mathsf{\Gamma }T\sqrt{n}}{2}\end{array}$$

(82)

$$\begin{array}{ll}& \le \frac{T\sigma \left({\theta }_1^T\right)}{C}+\frac{\sigma \left({\theta }_1^T\right)\mathsf{\Gamma }T\sqrt{n}}{2},\end{array}$$

(83)

using $\overline{\gamma }=C^2$ and $\sigma \left({\theta }_1^T\right)\le 2C$. Plugging (77), (80) and the definition of L into (75) gives

$$\begin{array}{ll}\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\lambda }_t}\right)& \le \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+C\sqrt{\left(\frac{n^2{\mathsf{\Gamma }}^4}{4}+4C^2{n}^{2\beta }+4C^4{n}^{4\beta }\right)(4+C^2)T}\end{array}$$

(84)

$$\begin{array}{ll}& +\frac{{\mathsf{\Gamma }}^{2}T{n}^{1-\beta }}{2}+\sigma \left({\theta }_1^T\right)T\left(\mathsf{\Gamma }\sqrt{n}+\frac{1}{C}\right)\}\end{array}$$

(85)

$$\begin{array}{ll}& =\underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+C\sqrt{(4+C^2)\left(\frac{n^2{\mathsf{\Gamma }}^4}{4n^{2\vee 4\beta }}+\frac{4C^2{n}^{2\beta }}{n^{2\vee 4\beta }}+\frac{4C^4{n}^{4\beta }}{n^{2\vee 4\beta }}\right)}{n}^{1\vee 2\beta }\sqrt{T}\end{array}$$

(86)

$$\begin{array}{ll}& +\left[\frac{{\mathsf{\Gamma }}^2}{2}{n}^{1-\beta }+\left(\mathsf{\Gamma }+\frac{1}{nC}\right)\sigma \left({\theta }_1^T\right)\sqrt{n}\right]T\}\end{array}$$

(87)

$$\begin{array}{ll}& \le \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+C\sqrt{(4+C^2)\left(\frac{{\mathsf{\Gamma }}^2}{4}+4C^2+4C^4\right)}{n}^{1\vee 2\beta }\sqrt{T}\end{array}$$

(88)

$$\begin{array}{ll}& +\left[\frac{{\mathsf{\Gamma }}^2}{2}{n}^{1-\beta }+\left(\mathsf{\Gamma }+\frac{1}{C}\right)\sigma \left({\theta }_1^T\right)\sqrt{n}\right]T\}\end{array}$$

(89)

$$\begin{array}{ll}& \le \underset{{\theta }_1,\dots ,{\theta }_T\in \Theta }{inf}\{\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t\right)+\mathcal{C}(\mathsf{\Gamma },C)\left[n^{1\vee 2\beta }\sqrt{T}+\left(n^{1-\beta }+\sigma \left({\theta }_1^T\right)\sqrt{n}\right)T\right]\end{array}$$

(90)

where we took

$$\mathcal{C}(\mathsf{\Gamma },C)=max\left(C\sqrt{(4+C^2)\left(\frac{{\mathsf{\Gamma }}^2}{4}+4C^2+4C^4\right)},\frac{{\mathsf{\Gamma }}^2}{2},\mathsf{\Gamma }+\frac{1}{C}\right).$$

(91)

This ends the proof. □

Proof of Theorem 2.

A direct application of Proposition 1 gives

$$\begin{array}{ll}\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le & \underset{\eta \ge \frac{1}{n}}{inf}\left\{\sum _{t=1}^T\underset{\theta \in {\Theta }_0}{min}\right[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)\\ & +\frac{\eta n{\left[{max}_{\vartheta \in {\Theta }_0,1\le i\le n}{\ell }_{t,i}\left(\vartheta \right)\right]}^2}{8}+\frac{logM}{\eta }]+\frac{\alpha T{L}^2}{2}+\frac{{(\eta -1)}^2}{2\alpha }\}.\end{array}$$

(92)

Thus, we have

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le \underset{\eta \ge \frac{1}{n}}{inf}\left\{\sum _{t=1}^T\underset{\theta \in {\Theta }_0}{min}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{\eta n{b}^2}{8}+\frac{logM}{\eta }\right]+\frac{\alpha T{L}^2}{2}+\frac{{(\eta -1)}^2}{2\alpha }\right\}.$$

(93)

Now, plugging in the right-hand side

$$\eta =\frac{1}{n}\vee \left(\frac{2}{b}\sqrt{\frac{2logM}{n}}\right)\wedge 1,$$

(94)

we obtain:

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le \sum _{t=1}^T\underset{\theta \in {\Theta }_0}{min}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{b^2}{8}+b\sqrt{\frac{nlog\left(M\right)}{2}}+log\left(M\right)\right]+\frac{\alpha T{L}^2}{2}+\frac{1}{2\alpha }.$$

(95)

Now, we see that the value $\alpha =\sqrt{2/\left(T{L}^2\right)}$ leads to:

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le \sum _{t=1}^T\underset{\theta \in {\Theta }_0}{min}\left[\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+\frac{b^2}{8}+b\sqrt{\frac{nlog\left(M\right)}{2}}+log\left(M\right)\right]+L\sqrt{2T}.$$

(96)

Rearranging terms, and replacing L by its value,

$$\begin{array}{ll}\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\eta }_t}\right)\le & \sum _{t=1}^T\underset{\theta \in {\Theta }_0}{min}\sum _{i=1}^n{\ell }_{t,i}\left(\theta \right)+bT\sqrt{\frac{nlog\left(M\right)}{2}}+\frac{b^{2}T}{8}+Tlog\left(M\right)\\ & +\left(n^{2}logM+\frac{n{B}^2}{8}\right)\sqrt{2T},\end{array}$$

(97)

that is the statement of the theorem. □

Proof of Theorem 3.

An application of Proposition 1 leads to

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\pi }_t}\right)\le \underset{\pi \in \mathsf{\Lambda }}{min}\left\{\sum _{t=1}^T\left[\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t^{*}\right)+Clog\frac{1}{\pi \left({\theta }_t^{*}\right)}\right]+\frac{\alpha T{L}^2}{2}+\frac{\parallel \pi -{\pi }_1{\parallel }^2}{2\alpha }\right\}$$

(98)

and so

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\pi }_t}\right)\le \underset{\pi \in \mathsf{\Lambda }}{min}\left\{\sum _{t=1}^T\left[\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t^{*}\right)+Clog\frac{1}{\pi \left({\theta }_t^{*}\right)}\right]+\frac{\alpha T{L}^2}{2}+\frac{1}{2\alpha }\right\}$$

(99)

define ${\pi }_{I^{*}}$ such that ${\pi }_{I^{*}}\left({\theta }_j\right)=1/\left(2m^{*}\right)$ if $j\in I^{*}$ and ${\pi }_{I^{*}}\left({\theta }_j\right)=1/\left(2(M-m^{*})\right)$ otherwise. We have ${\pi }_I^{*}\in \mathsf{\Lambda }$ and thus

$$\sum _{t=1}^T\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_{t,i}^{{\pi }_t}\right)\le \sum _{t=1}^T\left[\sum _{i=1}^n{\ell }_{t,i}\left({\theta }_t^{*}\right)+Clog\left(2m^{*}\right)\right]+\frac{\alpha T{L}^2}{2}+\frac{1}{2\alpha }.$$

(100)

Replace L and $\alpha$ by their values to get the theorem. □

7. Conclusions

We proposed two simple meta-learning strategies together with their theoretical analysis. Our results clearly show an improvement on learning in isolation if the tasks are similar enough. These theoretical findings are confirmed by our numerical experiments. Important questions remain open. In [27], a purely online method is proposed, in the sense that it does not require storing all of the information of the current task. In the case of OGA, this method allows us to learn the starting point. However, its application to learn the step size is not direct [28]. An important question is, then: is there a purely online method that would provably improve on learning in isolation in this case? Another important question is the automatic calibration of $\mathsf{\Gamma }$. However, as mentioned in Section 5, we believe that a very general and efficient meta-learning method for learning priors in Bayesian statistics (or in generalized Bayesian inference) would be extremely valuable in practice.