Provable Guarantees for Gradient-Based Meta-Learning

Introduction

The goal of meta-learning can be broadly defined as using the data of existing tasks to learn algorithms or representations that enable better or faster performance on unseen tasks. As the modern iteration of learning-to-learn (LTL) (Thrun & Pratt, 1998), research on meta-learning has been largely focused on developing new tools that can exploit the power of the latest neural architectures. Examples include the control of stochastic gradient descent (SGD) itself using a recurrent neural network (Ravi & Larochelle, 2017) and learning deep embeddings that allow simple classification methods to work well (Snell et al., 2017). A particularly simple but successful approach has been parameter-transfer via gradient-based meta-learning, which learns a meta-initialization $\phi$ for a class of parametrized functions $f_{\theta}:\mathcal{X}\mapsto\mathcal{Y}$ such that one or a few stochastic gradient steps on a few samples from a new task suffice to learn good task-specific model parameters $\hat{\theta}$ . For example, when presented with examples $(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}$ for an unseen task, the popular MAML algorithm (Finn et al., 2017) outputs

While meta-initialization is a more recent approach, methods for parameter-transfer have long been studied in the multi-task, transfer, and lifelong learning communities (Evgeniou & Pontil, 2004; Kuzborskij & Orabona, 2013; Pentina & Lampert, 2014). A common classical alternative to (1), which in modern parlance may be called meta-regularization, is to learn a good bias $\phi$ for the following regularized empirical risk minimization (ERM) problem:

Although there exist statistical guarantees and poly-time algorithms for learning a meta-regularization for simple models (Pentina & Lampert, 2014; Denevi et al., 2018b), such methods are impractical and do not scale to modern settings with deep neural architectures and many tasks. On the other hand, while the theoretically less-studied meta-initialization approach is often compared to meta-regularization (Finn et al., 2017), their connection is not rigorously understood.

In this work, we formalize this connection using the theory of online convex optimization (OCO) (Zinkevich, 2003), in which an intimate connection between initialization and regularization is well-understood due to the equivalence of online gradient descent (OGD) and follow-the-regularized-leader (FTRL) (Shalev-Shwartz, 2011; Hazan, 2015). In the lifelong setting of an agent solving a sequence of OCO tasks, we use this connection to analyze an algorithm that learns a $\phi$, which can be a meta-initialization for OGD or a meta-regularization for FTRL, such that the within-task regret of these algorithms improves with the similarity of the online tasks; here the similarity is measured by the distance between the optimal actions $\theta^{\ast}$ of each task and is not known beforehand. This algorithm, which we call Follow-the-Meta-Regularized-Leader ( FMRL or Ephemeral ), scales well in both computation and memory requirements, and in fact generalizes the gradient-based meta-learning algorithm Reptile (Nichol et al., 2018), thus providing a convex-case theoretical justification for a leading method in practice.

More specifically, we make the following contributions:

Our first result assumes a sequence of OCO tasks $t$ whose optimal actions $\theta_{t}^{\ast}$ are inside a small subset $\Theta^{\ast}$ of the action space. We show how Ephemeral can use these $\theta_{t}^{\ast}$ to make the average regret decrease in the diameter of $\Theta^{\ast}$ and do no worse on dissimilar tasks. Furthermore, we extend a lower bound of Abernethy et al. (2008) to the multi-task setting to show that one can do no more than a small constant-factor better sans stronger assumptions.

Under a realistic assumption on the loss functions, we show that Ephemeral also has low-regret guarantees in the practical setting where the optimal actions $\theta_{t}^{\ast}$ are difficult or impossible to compute and the algorithm only has access to a statistical or numerical approximation. In particular, we show high probability regret bounds in the case when the approximation uses the gradients observed during within-task training, as is done in practice by Reptile (Nichol et al., 2018).

We prove an online-to-batch conversion showing that the task parameters learned by a meta-algorithm with low task-averaged regret have low risk, connecting our guarantees to statistical LTL (Baxter, 2000; Maurer, 2005).

We verify several assumptions and implications of our theory using a new meta-learning dataset we introduce consisting of text-classification tasks solvable using convex methods. We further study the empirical suggestions of our theory in the deep learning setting.

Gradient-Based Meta-Learning: The model-agnostic meta-learning (MAML) algorithm of Finn et al. (2017) pioneered this recent approach to LTL. A great deal of empirical work has studied and extended this approach (Li et al., 2017; Grant et al., 2018; Nichol et al., 2018; Jerfel et al., 2018); in particular, Nichol et al. (2018) develop Reptile, a simple yet equally effective first-order simplification of MAML for which our analysis shows provable guarantees as a subcase. Theoretically, Franceschi et al. (2018) provide computational convergence guarantees for gradient-based meta-learning for strongly-convex functions, while Finn & Levine (2018) show that with infinite data MAML can approximate any function of task samples assuming a specific neural architecture as the model. In contrast to both results, we show finite-sample learning-theoretic guarantees for convex functions under a natural task-similarity assumption.

Online LTL: Learning-to-learn and multi-task learning (MTL) have both been extensively studied in the online setting, although our setting differs significantly from the one usually studied in online MTL (Abernethy et al., 2007; Dekel et al., 2007; Cavallanti et al., 2010). There, in each round an agent is told which of a fixed set of tasks the current loss belongs to, whereas our analysis is in the lifelong setting, in which tasks arrive one at a time. Here there are many theoretical results for learning useful data representations (Ruvolo & Eaton, 2013; Pentina & Lampert, 2014; Balcan et al., 2015; Alquier et al., 2017); the PAC-Bayesian result of Pentina & Lampert (2014) can also be used for regularization-based parameter transfer, which we also consider. Such methods are provable variants of practical shared-representation approaches, e.g. ProtoNets (Snell et al., 2017), but unlike our algorithms they do not scale to deep neural networks. Our work is especially related to Alquier et al. (2017), who also consider a many-task regret. We achieve similar bounds with a significantly more practical algorithm, although within-task their results hold for any low-regret method whereas ours only hold for OCO. Lastly, we note two concurrent works, by Denevi et al. (2019) and Finn et al. (2019), that address LTL via online learning, either directly or through online-to-batch conversion.

Meta-Initialization & Meta-Regularization

We study simple methods of the form of Algorithm 1, where we run a within-task online algorithm on each task and then update the initialization or regularization of this algorithm using a meta-update online algorithm. Alquier et al. (2017) study such a method where the meta-update is conducted using exponentially-weighted averaging. Our use of OCO for the meta-update makes this class of algorithms much more practical; for example, in the case of OGD for both the inner and outer loop we recover the Reptile algorithm of Nichol et al. (2018). To analyze Algorithm 1, we first discuss the OCO methods that make up both its inner and outer loop and the inherent connection they provide between initialization and regularization. We then make this connection explicit by formalizing the notion of learning a meta-initialization or meta-regularization as learning a parameterized Bregman regularizer. We conclude this section by proving convex-case upper and lower bounds on the task-averaged regret.

When $\operatorname{\bf R}_{T}=o(T)$ then as $T\to\infty$ the average loss of the agent will approach that of an optimal fixed action.

and achieves sublinear regret $\mathcal{O}(D\sqrt{T})$ when $\eta\propto\frac{D}{\sqrt{T}}$, where $D$ is the diameter of the action space $\Theta$.

In the case of linear losses this is the online mirror descent (OMD) generalization of OGD. For $G$-Lipschitz losses, OMD and FTRL have the following well-known regret guarantee $\forall~{}\theta^{\ast}\in\Theta$ (Shalev-Shwartz, 2011, Theorem 2.11):

2 Task-Averaged Regret and Task Similarity

The task-averaged regret (TAR) of an online algorithm after $T$ tasks with $\{m_{t}\}_{t=1}^{T}$ steps is

Note that, unlike in standard regret one cannot achieve TAR decreasing in $T$, the number of tasks, because the comparator is dynamic and so can force a constant loss at each task $t$. Furthermore, the average is taken over $T$ and not the number of rounds per task $m_{t}$, so in our results we expect TAR to grow sub-linearly in $m_{t}$. This corresponds to achieving sub-linear single-task regret on-average.

An alternative comparator that is seemingly natural in the study of gradient-based meta-learning is the best fixed initialization in hindsight; however, this quantity overlooks the fact that meta-initialization is simply a tool to achieve what we actually care about, which is within-task performance. If the difference between the task loss when starting from the best meta-initialization and that of the optimal within-task parameter is high, comparing to the best meta-initialization may not be very meaningful. On the other hand, a low TAR ensures that the task loss of an algorithm compared to that of the optimal within-task parameter is low on average.

We now formalize our similarity assumption on the tasks $t\in[T]$: their optimal actions $\theta_{t}^{\ast}$ lie within a small subset $\Theta^{\ast}$ of the action space. This is natural for studying gradient-based meta-learning, as the notion that there exists a meta-parameter $\phi$ from which a good parameter for any individual task is reachable with only a few steps implies that they are all close together. We develop algorithms whose TAR scales with the diameter $D^{\ast}$ of $\Theta^{\ast}$; notably, this means they will not do much worse if $\Theta^{\ast}=\Theta$, i.e. if the tasks are not related in this way, but will do well if $D^{\ast}\ll D$. Importantly, our methods will not require knowledge of $\Theta^{\ast}$.

Note $\theta_{t}^{\ast}$ is unique as the minimum of $\|\cdot\|^{2}$, a strongly convex function, over minima of a convex function. The algorithms in Section 2.4 assume an efficient oracle computing $\theta_{t}^{\ast}$.

3 Parameterizing Bregman Regularizers

Within each task, the regularizer is parameterized by the second argument and acts on the first. More specifically, for $R=\frac{1}{2}\|\cdot\|_{2}^{2}$ we have $\mathcal{B}_{R}(\theta||\phi)=\frac{1}{2}\|\theta-\phi\|_{2}^{2}$, and so in the case of FTRL and OGD, $\phi$ is a parameterization of the regularization and the initialization, respectively. In the case of the entropic regularizer, the associated Bregman regularizer is the KL-divergence from $\phi$ to $\theta$ and thus meta-learning $\phi$ can very explicitly be seen as learning a prior.

Finally, we use Bregman regularizers to formally define our parameterized learning algorithms:

for Bregman regularizer $\mathcal{B}_{R}$. Similarly, $\operatorname{OMD}_{\eta,\phi}$ plays

Here FTRL and OMD correspond to the meta-regularization (2) and meta-initialization (1) approaches, respectively. As $\mathcal{B}_{R}(\cdot||\phi)$ is strongly-convex, both algorithms have the same regret bound (5), allowing us to analyze them jointly.

4 Follow-the-Meta-Regularized-Leader

We now specify the first variant of our main algorithm, Follow-the-Meta-Regularized-Leader (Ephemeral). First assume the diameter $D^{\ast}$ of $\Theta^{\ast}$, as measured by the square root of the maximum Bregman divergence between any two points, is known. Starting with $\phi_{1}\in\Theta$, run $\operatorname{FTRL}_{\eta,\phi_{t}}$ or $\operatorname{OMD}_{\eta,\phi_{t}}$ with $\eta\propto\frac{D^{\ast}}{\sqrt{m}}$ on the losses in each task $t$. After each task, compute $\phi_{t+1}$ using an OCO meta-update algorithm operating on the Bregman divergences $\mathcal{B}_{R}(\theta_{t}^{\ast}||\cdot)$. For $D^{\ast}$ unknown, make an underestimate $\varepsilon>0$ and multiply it by a factor $\gamma>1$ each time $\mathcal{B}_{R}(\theta_{t}^{\ast}||\phi_{t})>\varepsilon^{2}$.

The following is a regret bound for this algorithm when the meta-update is either Follow-the-Leader (FTL), which plays the minimizer of all past losses, or OGD with adaptive step size. We call this Ephemeral variant Follow-the-Average-Leader (FAL) because in the case of FTL the algorithm uses the mean of the previous optimal parameters in hindsight as the initialization. Pseudo-code for this and other variants is given in Algorithm 2. For brevity, we state results for constant $G_{t}=G,m_{t}=m~{}\forall~{}t$; detailed statements are in the supplement together with the full proof.

In Setting 2.1, the FAL variant of Algorithm 2 with task similarity guess $\varepsilon=D\frac{1+\log T}{T}$, tuning parameter $\gamma=\frac{1+\log T}{\log T}$, and $\mathcal{B}_{R}$ that is Lipschitz on $\Theta^{\ast}$ achieves TAR

for diameter $D^{\ast}=\max_{\theta,\phi\in\Theta^{\ast}}\sqrt{\mathcal{B}_{R}(\theta||\phi)}$ of $\Theta^{\ast}$.

We give a proof for $R(\cdot)=\frac{1}{2}\|\cdot\|_{2}^{2}$ and known task similarity, i.e. $\varepsilon=D^{\ast},\gamma=1$. Denote the divergence to $\theta_{t}^{\ast}$ by $\Delta_{t}(\phi)=\mathcal{B}_{R}(\theta_{t}^{\ast}||\phi)=\frac{1}{2}\|\theta_{t}^{\ast}-\phi\|_{2}^{2}$ and let $\phi^{\ast}=\frac{1}{T}\sum_{t=1}^{T}\theta_{t}^{\ast}$. Note $\Delta_{t}$ is 1-strongly-convex and $\phi^{\ast}$ is the minimizer of their sum, with the variance $\bar{D}^{2}=\frac{1}{T}\sum_{t=1}^{T}\Delta_{t}(\phi^{\ast})\leq{D^{\ast}}^{2}$. Now by Definition 2.1:

The first two lines apply the regret bound (5) of FTRL and OMD. The key step is the last one, with the regret is split into the loss of the meta-update algorithm on the left and the loss if we had always initialized at the mean $\phi^{\ast}$ of the optimal actions $\theta_{t}^{\ast}$ on the right. Since $\Delta_{1},\dots,\Delta_{T}$ are 1-strongly-convex with minimizer $\phi^{\ast}$, and since each $\phi_{t}$ is determined by playing FTL or OGD on these same functions, the left term is the regret of these algorithms on strongly-convex functions, which is known to be $\mathcal{O}(\log T)$ (Bartlett et al., 2008; Kakade & Shalev-Shwartz, 2008). Substituting the definition of $\phi^{\ast}$ and $\eta=\frac{D^{\ast}}{G\sqrt{m}}$ sets the right term to

The full proof uses the doubling trick to tune task similarity $D^{\ast}$, requiring an analysis of the location of meta-parameter $\phi_{t}$ to ensure that we only increase the guess when needed. The extension to non-Euclidean geometries uses a novel logarithmic regret bound for FTL over Bregman regularizers.

Note that if we know the variance $\bar{D}^{2}$ of the task parameters from their mean $\phi^{\ast}$, setting $\eta_{t}=\frac{\bar{D}}{G_{t}\sqrt{m_{t}}}$ in Algorithm 2 and following the analysis above replaces $D^{\ast}$ in Theorem 2.1 with $\bar{D}$, which is better since $\bar{D}\leq D^{\ast}$ and is furthermore less sensitive to possible outlier tasks.

However, it is easy to see that an even simpler “strawman” algorithm achieves regret only a constant factor worse: at time $t+1$, simply initialize FTRL or OMD using the optimal parameter $\theta_{t}^{\ast}$ of task $t$. Of course, in the few-shot setting of small $m$, a reduction in the average regret is still practically significant; we observe this empirically in Figure 3. Indeed, in the proof of Theorem 2.1 the regret converges to that obtained by always playing the mean optimal action, which will not occur when playing the strawman algorithm. Furthermore, the following lower-bound on the task-averaged regret, a multi-task extension of Abernethy et al. (2008, Theorem 4.2), shows that such constant factor reductions are the best we can achieve under our task similarity assumption:

More broadly, this lower bound shows that the learning-theoretic benefits of gradient-based meta-learning are inherently limited without stronger assumptions on the tasks. Nevertheless, Ephemeral-style algorithms are very attractive from a practical perspective, as their memory and computation requirements per iteration scale linearly in the dimension and not at all in the number of tasks.

Provable Guarantees for Practical Gradient-Based Meta-Learning

In the previous section we gave an algorithm with access to the best actions in hindsight $\theta_{t}^{\ast}$ of each task that can learn a good meta-initialization or meta-regularization. While $\theta_{t}^{\ast}$ is efficiently computable in some cases, often it is more practical to use an approximation. This holds in the deep learning setting, e.g. Nichol et al. (2018) use the average within-task gradient. Furthermore, in the batch setting a more natural similarity notion depends on the true risk minimizers and not the optimal actions for a few samples. In this section we first show how two simple variants of Ephemeral handle these settings, one for the adversarial setting which uses the final action on task $t$ as the meta-update and one for the stochastic setting using the average iterate. We call these methods FLI-Online and FLI-Batch, respectively, where FLI stands for Follow-the-Last-Iterate. We then provide an online-to-batch conversion result for TAR that implies good generalization guarantees when any of the variants of Ephemeral are run in the distributional LTL setting.

To prove FLI guarantees, we require in Setting 3.1 that some notion of average loss on each task grows quadratically away from the optimum, which is shown to hold in both a real and a synthetic setting in Figure 2.

In Setting 2.1, for each task $t\in[T]$ define average loss $L_{t}$ according to one of the following two cases:

Assume the corresponding $L_{t}$ in each case is $\alpha$-QG w.r.t. $\|\cdot\|$ and define $\Theta^{\ast}\subset\Theta$ s.t. $\Theta^{\ast}\supset\operatorname*{arg\,min}_{\theta\in\Theta}L(\theta)~{}\forall~{}t\in[T]$.

Here case (b) is the batch-within-online setting, also studied by Alquier et al. (2017). In this case the distance defining the similarity is between the true-risk minimizers and not the optimal parameters in hindsight. Under such data-dependent assumptions we have the following bound on using approximate meta-updates:

In Setting 3.1(a), the FLI-Online variant of Algorithm 2 with $\varepsilon=\Omega\left(\frac{1}{\sqrt{m}}\right)$, tuning parameter $\gamma\geq 1$, and within-task algorithm FTRL with Bregman regularizer $\mathcal{B}_{R}$ for $R$ strongly-smooth w.r.t. $\|\cdot\|$ achieves TAR

for $D^{\ast}$ as in Theorem 2.1 and $o_{m}(1)=\mathcal{O}(m^{-\frac{1}{6}})$. In Setting 3.1(b) the same bound holds w.p. $1-\delta$ and $o_{m}(1)=\mathcal{O}\left(m^{-\frac{1}{6}}\sqrt{\log\frac{Tm}{\delta}}\right)$ for both the FAL and FLI-Batch variants and using either FTRL or OMD within-task.

This bound is very similar to Theorem 2.1 apart from a per-task error term due to the use of an estimate of $\theta_{t}^{\ast}$.

2 Distributional Learning-to-Learn

Theorem 3.2 gives an online-to-batch conversion for which low TAR implies low expected risk of a new task sampled from $\mathcal{Q}$. For Ephemeral, the procedure draws $t\sim\mathcal{U}[T]$, runs $\operatorname{FTRL}_{\eta_{t},\phi_{t}}$ or $\operatorname{OMD}_{\eta,\phi_{t}}$ on samples from $\mathcal{P}\sim\mathcal{Q}$, and outputs the average iterate $\bar{\theta}$. Such guarantees on random or mean iterates are standard, although in practice the last iterate is used. The proof uses Jensen’s inequality to combine two standard conversions (Cesa-Bianchi et al., 2004).

Empirical Results

An important aspect of Ephemeral is its practicality. n particular, FLI-Batch is scalable without modification to high-dimensional, non-convex models. This is demonstrated by the success of Reptile (Nichol et al., 2018), a sub-case of our method that competes with MAML on standard meta-learning benchmarks. Given this evidence, empirically our goal is to validate our theory in the convex setting, although we also examine implications for deep meta-learning.

We introduce a new dataset of 812 classification tasks, each consisting of sentences from one of four Wikipedia pages which we use as labels. It is derived from the raw super-set of the Wiki3029 corpus collected by Arora et al. (2019). We call the new dataset Mini-Wiki and make it available in the supplement. Our use of text classification to examine the convex setting is motivated by the well-known effectiveness of linear models over simple representations (Wang & Manning, 2012; Arora et al., 2018). We use logistic regression over 50-dimensional continuous-bag-of-words (CBOW) using GloVe embeddings (Pennington et al., 2014). The similarity of these tasks is verified by seeing if their optimal parameters are close together. As shown before in Figure 1, we find when $\Theta$ is the unit ball that even in the 1-shot setting the tasks have non-vacuous similarity; for 32-shots the parameters are contained in a set of radius 0.32.

We next compare Ephemeral to the “strawman” algorithm from Section 2, which uses the previous optimal action as the initialization. For both algorithms we use similarity guess $\varepsilon=0.1$ and tune with $\gamma=1.1$. As expected, in Figure 3 we see that Ephemeral is superior to the strawman algorithm, especially for few-shot learning, demonstrating that our TAR improvement is significant in the low-sample regime. We also see that FLI-Batch, which uses approximate meta-updates, approaches FAL as the number of samples increases and thus its estimate improves.

Finally, we evaluate Ephemeral and (first-order) MAML in the statistical setting. On each task we standardize data using the mean and deviation of the training features. For Ephemeral we use the FAL variant with OGD as the within-task algorithm, with learning rate set using the average deviation of the task parameters from the mean parameter, as suggested in Remark 2.1. For MAML, we use grid search to determine the within-task and meta-update learning rates. As shown in Figure 4, despite using no tuning, Ephemeral performs comparably to MAML – slightly better for $m\geq 8$ and slightly worse for $m<4$.

2 Deep Learning

While our method generalizes Reptile, an effective meta-learning method (Nichol et al., 2018), we can still examine if our theory can help neural network LTL. We study modifications of Reptile on 5-way and 20-way Omniglot (Lake et al., 2017) and 5-way Mini-ImageNet classification (Ravi & Larochelle, 2017) using the same networks as Nichol et al. (2018). As in these works, we evaluate in the transductive setting, where test points are evaluated in batch.

Our theory points to the importance of accurately computing the within-task parameter for the meta-update; Theorem 2.1 assumes access to this parameter, whereas Theorems 3.1 allow computational and stochastic approximations that result in an additional error term decaying with number of task-examples. This becomes relevant in the non-convex setting with many tasks, where it is infeasible to find even a local optimum. Thus we see how a better estimate of the within-task parameter for the meta-update may lead to higher accuracy. We can attain a better estimate by using more samples to reduce stochastic noise or by running more gradient steps on each task to reduce approximation error. It is not obvious that these changes will improve performance – it may be better to learn using the same settings at meta-train and meta-test time. However, for 5-shot evaluation the Reptile authors do indeed use more than 5 task samples – 10 for Omniglot and 15 for Mini-ImageNet. Similarly, they use far fewer within-task gradient steps – 5 for Omniglot and 8 for Mini-ImageNet – at meta-train time than the 50 iterations used for evaluation.

We study how the two settings – the number of task samples and within-task iterations – affect meta-test performance. In Figure 5, we see that more task-samples provide a significant improvement, with fewer meta-iterations needed for good test performance. Reducing this number is equivalent to reducing task-sample complexity, although for a better approximation each task needs more samples. We also see in Figure 6 that taking more gradient steps, which does not use more samples, can also help performance, especially on 20-way Omniglot. However, on Mini-ImageNet using than 8 iterations reduces performance; this may be due to over-fitting on specific tasks, with task similarity likely holding for the true rather than empirical risk minimizers, as in Setting 3.1(b). The broad patterns shown above also hold for several other settings, which we discuss in the supplement.

Conclusion

In this paper we study a broad class of gradient-based meta-learning methods using the theory of OCO, proving their usefulness compared to single-task learning under a closeness assumption on task parameters. The guarantees of our algorithm, Ephemeral, can be extended to approximate meta-updates, the batch-within-online setting, and statistical LTL. Apart from these results, the algorithm’s simplicity makes it extensible to settings of practical interest such as federated learning and differential privacy. Future work can consider more sophisticated notions of task-similarity, such as multi-modal or evolving settings, and theory for practical and scalable shared-representation-learning.

Acknowledgments

This work was supported in part by DARPA FA875017C0141, National Science Foundation grants CCF-1535967, IIS-1618714, IIS-1705121, and IIS-1838017, a Microsoft Research Faculty Fellowship, an Okawa Grant, a Google Faculty Award, an Amazon Research Award, an Amazon Web Services Award, and a Carnegie Bosch Institute Research Award. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA, the National Science Foundation, or any other funding agency.

References

Appendix A Background and Results for Online Convex Optimization

We first state the related definitions of strong convexity and strong smoothness:

We now turn to the Bregman divergence and a discussion of several useful properties (Bregman, 1967; Banerjee et al., 2005):

The definition directly implies that $\mathcal{B}_{f}(\cdot||y)$ preserves the (strong or strict) convexity of $f$ for any fixed $y\in S$. Strict convexity further implies $\mathcal{B}_{f}(x||y)\geq 0~{}\forall~{}x,y\in S$, with equality iff $x=y$. Finally, if $f$ is $\alpha$-strongly-convex, or $\beta$-strongly-smooth, w.r.t. $\|\cdot\|$ then Definition A.1 implies $\mathcal{B}_{f}(x||y)\geq\frac{\alpha}{2}\|x-y\|^{2}$, or $\mathcal{B}_{f}(x||y)\leq\frac{\beta}{2}\|x-y\|^{2}$, respectively.

By Definition A.3 the last expression has a unique minimum at $y=\bar{x}$. ∎

A.2 Standard Online Algorithms

Here we provide a review of the online algorithms we use. Recall that in this setting our goal is minimizing regret:

Within-task our focus is on two closely related meta-algorithms, Follow-the-Regularized-Leader (FTRL) and (linearized lazy) Online Mirror Descent (OMD).

for all $\theta^{\ast}\in\Theta$ and $G^{2}\geq\frac{1}{T}\sum_{t=1}^{T}G_{t}^{2}$.

We next review the online algorithms we use for the meta-update. The main requirement here is logarithmic regret guarantees for the case of strongly convex loss functions, which is satisfied by two well-known algorithms:

Kakade & Shalev-Shwartz (2008, Theorem 2) and Bartlett et al. (2008, Theorem 2.1) provide for FTL and AOGD, respectively, the following regret bound:

One further useful fact about FTL and AOGD is that when run on a sequence of Bregman regularizers $\mathcal{B}_{R}(\theta_{1}||\cdot),\dots,\mathcal{B}_{R}(\theta_{T}||\cdot)$ they will play points in the convex hull $\operatorname{Conv}(\{\theta_{t}\}_{t\in[T]})$:

The proof for FTL follows directly from Claim A.1 and the fact that the weighted average of a set of points is in their convex hull. For AOGD we proceed by induction on $t$. The base case $t=1$ holds by the assumption $\phi_{t}\in\Theta^{\ast}$. In the inductive case, note that $\mathcal{B}_{R}(\theta_{t}||\phi_{t})=\frac{1}{2}\|\theta_{t}-\phi_{t}\|_{2}^{2}$ so the gradient update is $\phi_{t+1}=\phi_{t}+\frac{\alpha_{t}}{\alpha_{1:t}}(\theta_{t}-\phi_{t})$, which is on the line segment between $\phi_{t}$ and $\theta_{t}$, so the proof is complete by the convexity of $\Theta^{\ast}\ni\phi_{t},\theta_{t}$. ∎

A.3 Online-to-Batch Conversion

Finally, as we are also interested in distributional meta-learning, we discuss some techniques for converting regret guarantees into generalization bounds, which are usually named online-to-batch conversions. We state some standard results below:

Note that Cesa-Bianchi et al. (2004) only prove the first inequality; the second follows via the same argument but applying the symmetric version of the Azuma-Hoeffding inequality (Azuma, 1967).

Appendix B Proofs of Theoretical Results

In this section we prove the main guarantees on task-averaged regret for our algorithms, as, lower bounds showing that the results are tight up to constant factors, and online-to-batch conversion guarantees for statistical LTL. We first define some necessary definitions, notations, and general assumptions.

Using the data given to Algorithm 2 define the following quantities:

convenience coefficients $\sigma_{t}=G_{t}\sqrt{m_{t}}$

the sequence of update parameters $\{\hat{\theta}_{t}\in\Theta\}_{t\in[T]}$ with average update parameter $\hat{\phi}=\frac{1}{\sigma_{1:T}}\sum_{t=1}^{T}\sigma_{t}\hat{\theta}_{t}$

a sequence of reference parameters $\{\theta_{t}^{\prime}\in\Theta\}_{t\in[T]}$ with average reference parameter $\phi^{\prime}=\frac{1}{\sigma_{1:T}}\sum_{t=1}^{T}\sigma_{t}\theta_{t}^{\prime}$

a sequence $\{\theta_{t}^{\ast}\in\Theta\}_{t\in[T]}$ of optimal parameters in hindsight

we will say we are in the “Exact” case if $\hat{\theta}_{t}=\theta_{t}^{\prime}=\theta_{t}^{\ast}~{}\forall~{}t$ and the “Approx” case otherwise

$\kappa\geq 1,\Delta_{t}^{\ast}\geq 0$ s.t. $\sum_{t=1}^{T}\alpha_{t}\mathcal{B}_{R}(\theta_{t}^{\ast}||\phi_{t})\leq\sum_{t=1}^{T}\alpha_{t}\Delta_{t}^{\ast}+\kappa\sum_{t=1}^{T}\alpha_{t}\mathcal{B}_{R}(\hat{\theta}_{t}||\phi_{t})$ for some nonnegative $\alpha_{t}$

$\nu\geq 1,\Delta^{\prime}\geq 0$ s.t. $\sum_{t=1}^{T}\sigma_{t}\mathcal{B}_{R}(\hat{\theta}_{t}||\hat{\phi})\leq\Delta^{\prime}+\nu\sum_{t=1}^{T}\sigma_{t}\mathcal{B}_{R}(\theta_{t}^{\prime}||\phi^{\prime})$

$\Delta_{\max}\geq 0$ s.t. $\frac{1}{2}\|\theta_{t}^{\prime}-\hat{\theta}_{t}\|^{2}\leq\Delta_{\max}~{}\forall~{}t\in[T]$

average deviation $\bar{D}^{2}=\frac{1}{\sigma_{1:T}}\sum_{t=1}^{T}\sigma_{t}\mathcal{B}_{R}(\theta_{t}^{\prime}||\phi^{\prime})$ of the reference parameters; assumed positive

task diameter $D^{\ast}=\max_{\theta,\phi\in\operatorname{Conv}(\{\theta_{t}^{\prime}\}_{t\in[T]})}\sqrt{\mathcal{B}_{R}(\theta||\phi)}$; assumed positive

action diameter $D^{2}=\max\{{D^{\ast}}^{2},\max_{\theta\in\Theta}\mathcal{B}_{R}(\theta||\phi_{1})\}$ in the Exact case or $\max_{\theta,\phi\in\Theta}\mathcal{B}_{R}(\theta||\phi)$ in the Approx case

upper bound $G^{\prime}$ on the Lipschitz constants of the functions $\{\mathcal{B}_{R}(\hat{\theta}_{t}||\cdot)\}_{t\in[T]}$ over $\operatorname{Conv}(\{\hat{\theta}_{t}\}_{t=1}^{T})$

we will say we are in the “Nice” case if $\mathcal{B}_{R}(\theta||\cdot)$ is 1-strongly-convex and $\beta$-strongly-smooth w.r.t. $\|\cdot\|~{}\forall~{}\theta\in\Theta$

in the general case $\operatorname{META}$ is FTL; in the Nice case $\operatorname{META}$ may instead be AOGD re-initialized at $\theta_{1}^{\ast}$

convenience indicator $\iota=1_{\operatorname{META}=\operatorname{FTL}}$

effective meta-action space $\hat{\Theta}=\operatorname{Conv}(\{\hat{\theta}_{t}\}_{t\in[T]})$ if $\operatorname{META}$ is FTL or $\Theta$ if $\operatorname{META}$ is AOGD

$\operatorname{TASK}_{\eta,\phi}=\operatorname{FTRL}_{\eta,\phi}^{(R)}$ or $\operatorname{OMD}_{\eta,\phi}^{(R)}$

at time $t=1$ the update algorithm $\operatorname{META}$ plays $\phi_{1}\in\Theta$ satisfying $\max_{\theta\in\Theta}\mathcal{B}_{R}(\theta||\phi_{1})<\infty$

in the Approx case $R$ is $\beta$-strongly-smooth for some $\beta\geq 1$

We first prove a technical result on the performance of FTL on a sequence of Bregman regularizers. We start by lower bounding the regret of FTL when the loss functions are quadratic.

We proceed by induction on $T$. The base case $T=1$ follows directly since $\phi_{1}=\theta_{1}$ and so the second term is zero. In the inductive case we have

in which case $\phi_{T}=\phi_{T-1}$ and both added terms are zero, preserving the inequality. The gradient and Hessian are

so the problem is strongly convex and thus has a unique global minimum. Setting the gradient to zero yields

We use this to show logarithmic regret of FTL when the loss functions are Bregman regularizers with changing first arguments. Note that such functions are in general only strictly convex, so the bounds from Theorem A.2 cannot be applied directly.

where $G_{R}$ is the Lipschitz constant of the Bregman regularizer $\mathcal{B}_{R}(\theta_{t}||\cdot)$ for any $t\in[T]$ on $S$ w.r.t. the Euclidean norm.

Defining $\bar{\phi}=\frac{1}{\alpha_{1:T}}\sum_{t=1}^{T}\alpha_{t}\theta_{t}$, we apply Claim A.1 and Lemma B.1 to get

Since Bregman regularizers are convex in the second argument, the above is the regret of playing FTL on a sequence of $a_{t}$-strongly-convex losses. Applying Kakade & Shalev-Shwartz (2008, Theorem 2) yields the result. ∎

The following result is our main theorem; Theorems 2.1 and 3.1 will follow as corollaries.

In Setting B.1, Algorithm 2 has TAR bounded as

for $C=\frac{{G^{\prime}}^{2}}{2}$ in the Nice case or otherwise $C=\frac{C^{\prime}D^{\prime}(G^{\prime}+1)}{2}$, $\rho=1$ in the Exact case or $\rho=2\sqrt{\beta}$ in the Approx case, and $\mathcal{E}=2\sqrt{2\beta\Delta_{\max}}$.

We first use the $\beta$-strong-smoothness of $R$ to provide a bound in the Approx setting of the distance from the initialization to the update parameter at each time $t\in[T]$:

The following result corresponds to the general case of Theorem 2.1.

In the Exact case of Setting B.1, if $G_{t}=G,m_{t}=m~{}\forall~{}t\in[T]$, the FAL variant of Algorithm 2 has TAR

If we assume known $D$, picking $\varepsilon=D\frac{1+\log T}{T}$ and $\gamma=\frac{1+\log T}{\log T}$ yields

For $K=\lfloor\log_{\gamma}\frac{D^{\ast}}{\varepsilon}\rfloor$ we have

The result follows by noting that in the exact case we have $\kappa=\nu=\rho=1,\Delta_{1:T}^{\ast}=\Delta^{\prime}=\Delta_{\max}=0$, and substituting $\sum_{t=1}^{T}\frac{1}{t}\leq(1+\log T)$. ∎

B.2 Lower Bound

The following lower bound, which extends Theorem 4.2 of Abernethy et al. (2008) to the multi-task setting, shows that the previous TAR guarantees are optimal up to a constant multiplicative factor. Note that while the result is stated in terms of the task divergence $D^{\ast}$, since $D^{\ast}\geq\bar{D}$ the same lower bound holds for the average task deviation as well.

Note that the condition $\langle\nabla_{t,i},\theta_{t,i}-\phi^{\ast}\rangle=0$ and the nonnegativity of $c(\theta)$ implies that the loss of the agent is at least 0, and so the agent’s regret on task $t$ satisfies $\operatorname{\bf R}_{m_{t}}\geq\frac{D^{\ast}}{2}\|\nabla_{t,1:m_{t}}\|_{2}$. By the condition $\langle\nabla_{t,i},\nabla_{t,1:i-1}\rangle=0$ we have that

and so by induction on $i$ with base case $\|\nabla_{t,1}\|_{2}=\frac{G_{t}}{2}$ we have $\|\nabla_{t,1:m_{t}}\|_{2}=\frac{G_{t}}{2}\sqrt{m_{t}}\implies\operatorname{\bf R}_{m_{t}}\geq\frac{G_{t}D^{\ast}}{4}\sqrt{m_{t}}$. Substituting the regret on each task into $\operatorname{\bf\bar{R}}=\frac{1}{T}\sum_{t=1}^{T}\operatorname{\bf R}_{m_{t}}$ completes the proof. ∎

B.3 Task-Averaged Regret for Approximate Meta-Updates

For the Approx variants of FMRL we need a bound on the distance between the last or average iterate of FTRL/OMD and the best parameter in hindsight. This necessitates further assumptions on the loss functions besides convexity, as a task may otherwise have functions with very small losses, even far away from the optimal parameter, in which case the last iterate of FTRL/OMD will be far away if the initial point is far away from the optimum. Here we make use of the $\alpha$-QG assumption on the average loss functions to obtain stability of the estimates w.r.t. the true loss.

We have by definition of $\theta^{\prime}$ and $\hat{\theta}$ that

On the other hand since $L$ is $\alpha$-QG we have that

Multiplying the second inequality by $\eta m$ and adding it to the first yields the result. ∎

Applying the triangle inequality, Jensen’s inequality, and Lemma B.3 yields the first two values:

Here in the last step we used the fact that $\varepsilon\geq\frac{4\beta G_{t}}{\alpha\sqrt{m_{t}}}\implies\eta_{t}\geq\frac{4\beta}{\alpha m_{t}}~{}\forall~{}t\in[T]$. For the next two values, noting that for FLI-Online, $\theta_{t}^{\ast}=\theta_{t}^{\prime}~{}\forall~{}t\in[T]$ we have by the triangle inequality and Titu’s lemma that

Therefore since $\eta\geq\frac{\varepsilon}{\sigma_{t}}$ and $\mathcal{B}_{R}(\theta_{t}^{\ast}||\phi_{t})\leq D^{2}$ we have that

The last value follows directly by Lemma B.3, $\eta_{t}\geq\frac{\varepsilon}{\sigma_{t}}$, and the bound $D^{2}$ on the maximum Bregman divergence. ∎

The following upper bound yields Theorem 3.1:

In the Approx. case of Setting B.1, if $G_{t}=G,m_{t}=m~{}\forall~{}t\in[T],\gamma=\frac{1+\log T}{\log T}$, and $\varepsilon=\frac{4\beta G}{\alpha\sqrt{m}}+D\frac{1+\log T}{T}$ then the FLI-Online variant of Algorithm 2 has TAR

Substitute Proposition B.1 into Theorem B.1 and simplify. ∎

By definition of $\theta^{\ast}$ and $\theta^{\prime}$ we have w.p. $1-\delta$ that

Suppose $\forall~{}t\in[T]$ the r.v. $Q_{t}$ satisfies $0\leq Q_{t}\leq B$ a.s. and $Q_{t}\leq\sqrt{\frac{8}{m_{t}}\log\frac{2}{\delta}}$ w.p. $1-\delta$ for any $\delta\in(0,1)$. Then for nonnegative $\alpha_{1},\dots,\alpha_{T}$ we have w.p. $1-\gamma$ for any $\gamma\in(0,1)$ that

Note further that using $\delta=\frac{2}{\sqrt{Bm_{t}}}$ and Jensen’s inequality we have

Noting that $Q_{t}\leq B$ a.s. $\implies X_{t}\leq B$ a.s., we have by Freedman’s inequality (Freedman, 1975, Theorem 1.6) that

for $\tau\geq 0,\sigma^{2}=\sum_{t=1}^{T}\frac{2+8\log(Bm_{t})}{m_{t}}\beta_{t}^{2}$. Substituting $\tau=\frac{2\beta_{\max}}{3}\log\frac{1}{\gamma}+\sqrt{2\sigma^{2}\log\frac{1}{\gamma}}$ yields

$\kappa=1$ and $\Delta_{t}^{\ast}=0~{}\forall~{}t\in[T]$ because $\hat{\theta}_{t}=\theta_{t}^{\ast}~{}\forall~{}t\in[T]$. Applying Titu’s lemma as in the proof of Proposition B.1 yields the values of $\nu$ and $\Delta^{\prime}$ w.p. $1-2\delta$:

Here in the last step we applied Lemma B.5 on $Q_{t}=\frac{\alpha}{2}\|\theta_{t}^{\ast}-\theta_{t}^{\prime}\|^{2}$, which is 1-bounded by Lemma B.4. The value of $\Delta_{\max}$ follows directly by Lemma B.4 w.p. $1-2\delta$. ∎

The following upper bound yields the FAL result in Theorem 3.1:

In the Approx. case of Setting B.1, if $G_{t}=G,m_{t}=m~{}\forall~{}t\in[T],\gamma=\frac{1+\log T}{\log T}$, and $\varepsilon=D\frac{1+\log T}{T}$ then the FAL variant of Algorithm 2 has TAR

Substitute Proposition B.2 into Theorem B.1 and simplify. ∎

where $G^{2}=\frac{1}{m}\sum_{i=1}^{m}G_{i}^{2}$.

By definition of $\hat{\theta}$ and $\theta^{\prime}$ we have w.p. $1-\delta$ that

Applying the triangle inequality, Jensen’s inequality, Lemma B.4, and Lemma B.6 yields w.p. $1-\delta$

where we have used the uniqueness of the reference parameter $\theta_{t}^{\prime}$. The above implies

Here in the last step we used the fact that $\varepsilon\geq\frac{24\beta G_{t}}{\alpha\sqrt{m_{\min}}}\implies\eta_{t}\geq\frac{24\beta}{\alpha m_{t}}~{}\forall~{}t\in[T]$. Thus by Lemma B.5 w.p. $1-3\delta$

This yields the values of $\kappa$ and $\Delta_{t}^{\ast}~{}\forall~{}t\in[T]$. We next have by applying Titu’s lemma as in the proof of Proposition B.1

This yields the values of $\nu$ and $\Delta^{\prime}$. The value of $\Delta_{\max}$ follows directly by Lemma B.4 w.p. $1-3\delta$. ∎

The following final upper bound yields the FLI-Batch result in Theorem 3.1:

In the Approx. case of Setting B.1, if $G_{t}=G,m_{t}=m~{}\forall~{}t\in[T],\gamma=\frac{1+\log T}{\log T}$, and $\varepsilon=\frac{24\beta G}{\alpha\sqrt{m}}+D\frac{1+\log T}{T}$ then the FLI-Batch variant of Algorithm 2 has TAR

Substitute Proposition B.3 into Theorem B.1 and simplify. ∎

B.4 Online-to-Batch Conversion for Task-Averaged Regret

The following yields a bound on the expected transfer risk when randomizing over the output of any TAR-minimizing algorithm when in the setting of statistical LTL.

where $\bar{\theta}=\frac{1}{m}\theta_{1:m}$ is generated by randomly sampling $t\in\mathcal{U}[T]$, running the online algorithm with state $s_{t}$, and averaging the actions $\{\theta_{i}\}_{i\in[m]}$.

Applying Proposition A.1, linearity of expectations, the fact that the regret over 1-bounded loss functions is $m$-bounded, and Proposition A.2 yields

Appendix C Computing the Quadratic Growth Factor

For our analysis of the FLI variants of Algorithm 2 we consider a class of functions related to strongly convex functions that satisfy the quadratic growth (QG) condition:

For our results we require a stronger condition, namely that if $L$ is a sum of $m$ convex losses then $L$ satisfies $\alpha m$-QG. While this additive property holds directly if the losses are strongly-convex, in the general case it does not. Furthermore, the spectral lower bound on $\alpha$ studied by Karimi et al. (2016) and Garber (2019) is an underestimate; for example, in the strongly-convex case, where $A^{T}A$ is the identity, the lower bound will be 1 even though their sum is $m$-QG.

Here we derive an alternative approach for verifying $\alpha$-QG for a convex Lipschitz function $f$ constrained to a ball of radius $B$. Note that since the functions are Lipschitz, we can focus on computing the minimal difference between $f(\theta)$ and $f(\theta^{\ast})$ over all $\theta$ located some fixed distance $\delta$ away from any minimizer $\theta^{\ast}$ of $f$ over the ball:

Then if $f$ is $\alpha$-QG, Equation 6 implies that $\alpha_{\delta}=\frac{2\varepsilon_{\delta}}{\delta^{2}}$ should be a constant, or equivalently that $\varepsilon_{\delta}=\Omega(\delta^{2})$. While the above problem is non-convex due to the first constraint, note that

which is a linear constraint since $\theta^{\ast}$ is constant. Therefore we have

which is a convex program amenable to standard solvers; we employ the Frank-Wolfe method (Frank & Wolfe, 1956).

Appendix D Experimental Details

We briefly describe the construction of Mini-Wiki. Starting with the raw corpus of the Wiki3029 dataset of Arora et al. (2019), we select those Wikipedia pages whose titles correspond to lemmas in the WordNet corpus (Fellbaum, 1998). We then use the hypernymy structure in this corpus to separate the pages into four semantically meaningful meta-classes; this is necessary when using linear classification as the task similarity only depends on the classifier and not the representation. Finally, we take the longest sentences from each page to construct $m$-shot tasks of $4m$ samples each, for $m=1,2,4,\dots,32$. We have made MiniWiki available here: https://github.com/mkhodak/FMRL/blob/master/data/miniwikipedia.tar.gz.

D.2 Complete Deep Learning Results

Below are plots for all evaluations on Omniglot and Mini-ImageNet. As our algorithm generalizes the Reptile method of Nichol et al. (2018), we use code they make available at https://github.com/openai/supervised-reptile and vary the parameters train-shots and inner-iters.