Provable Guarantees for Gradient-Based Meta-Learning
Mikhail Khodak Maria-Florina Balcan Ameet Talwalkar


[
Provable Guarantees for Gradient-Based Meta-Learning

















Mikhail Khodakcmu
          Maria-Florina Balcancmu
          Ameet Talwalkarcmu,dai


cmuCarnegie Mellon University
daiDetermined AI

Mikhail Khodakkhodak@cmu.edu





Machine Learning, ICML

0.3in
]









  





	We study the problem of meta-learning through the lens of online convex optimization, developing a meta-algorithm bridging the gap between popular gradient-based meta-learning and classical regularization-based multi-task transfer methods.
	Our method is the first to simultaneously satisfy good sample efficiency guarantees in the convex setting, with generalization bounds that improve with task-similarity, while also being computationally scalable to modern deep learning architectures and the many-task setting.
	Despite its simplicity, the algorithm matches, up to a constant factor, a lower bound on the performance of any such parameter-transfer method under natural task similarity assumptions
	.
	We use experiments in both convex and deep learning settings to verify and demonstrate the applicability of our theory.






§ 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) <cit.>, 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 <cit.> and learning deep embeddings that allow simple classification methods to work well <cit.>.
A particularly simple but successful approach has been parameter-transfer via gradient-based meta-learning, which learns a meta-initialization ϕ for a class of parametrized functions f_θ:𝒳↦𝒴 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 θ̂ .
For example, when presented with examples (x_i,y_i)∈𝒳×𝒴 for an unseen task, the popular MAML algorithm <cit.> outputs

    θ̂=ϕ-η∑_i∇ L(f_ϕ(x_i),y_i)

for loss function L:𝒴×𝒴↦ℝ_+ and learning rate η> 0;
θ̂ is then used for inference on the task.
Despite its simplicity, gradient-based meta-learning is a leading approach for LTL in numerous domains including vision <cit.>, robotics <cit.>, and federated learning <cit.>.



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 <cit.>.
A common classical alternative to (<ref>), which in modern parlance may be called meta-regularization, is to learn a good bias ϕ for the following regularized empirical risk minimization (ERM) problem:

    θ̂=_θθ-ϕ_2^2/2η+∑_iL(f_θ(x_i),y_i)

Although there exist statistical guarantees and poly-time algorithms for learning a  meta-regularization for simple models <cit.>, 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 <cit.>, their connection is not rigorously understood.















In this work, we formalize this connection using the theory of online convex optimization (OCO) <cit.>, 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) <cit.>.
In the lifelong setting of an agent solving a sequence of OCO tasks, we use this connection to analyze an algorithm that learns a ϕ, 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 θ^∗ of each task and is not known beforehand.
This algorithm, which we call Follow-the-Meta-Regularized-Leader (
FMRL or 

), scales well in both computation and memory requirements, and in fact generalizes the gradient-based meta-learning algorithm Reptile <cit.>,
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 θ_t^∗ are inside a small subset Θ^∗ of the action space.
	We show how can use these θ_t^∗ to make the average regret decrease in the diameter of Θ^∗ and do no worse on dissimilar tasks.
	Furthermore, we extend a lower bound of <cit.> 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 also has low-regret guarantees in the practical setting where the optimal actions θ_t^∗ 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 <cit.>.

	
  * 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 <cit.>.

	
  * 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.
	



















 §.§ Related Work

Gradient-Based Meta-Learning: The model-agnostic meta-learning (MAML) algorithm of <cit.> pioneered this recent approach to LTL. A great deal of empirical work has studied and extended this approach <cit.>;
in particular, <cit.> develop Reptile, a simple yet equally effective first-order simplification of MAML for which our analysis shows provable guarantees as a subcase.
Theoretically, <cit.> provide computational convergence guarantees for gradient-based meta-learning for strongly-convex functions, while <cit.> 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 <cit.>.
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 <cit.>;
the PAC-Bayesian result of <cit.> 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 <cit.>, but unlike our algorithms they do not scale to deep neural networks.
Our work is especially related to <cit.>, 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 <cit.> and <cit.>, that address LTL via online learning, either directly or through online-to-batch conversion.










Statistical LTL: While we focus on the online setting, our online-to-batch results also imply risk bounds for distributional meta-learning.

This setting was formalized by <cit.>;
<cit.> further extended the hypothesis-space-learning framework to algorithm-learning.
Recently, <cit.> showed PAC-Bayesian generalization bounds for this setting, although without implying an efficient algorithm.

Also closely related are the regularization-based approaches of <cit.>, which provide statistical learning guarantees for Ridge regression with a meta-learned kernel or bias.
<cit.> in particular focuses on usefulness relative to single-task learning, showing that their method is better than the ℓ_2-regularized ERM, but neither addresses the connection between loss-regularization and gradient-descent-initialization.














§ META-INITIALIZATION & META-REGULARIZATION




We study simple methods of the form of Algorithm <ref>, 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.
<cit.> 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 <cit.>.
To analyze Algorithm <ref>, 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.




 §.§ Online Convex Optimization


In the online learning setting, at each time t=1,…,T an agent chooses action θ_t∈Θ⊂ℝ^d and suffers loss ℓ_t(θ_t) for some adversarially chosen function ℓ_t:Θ↦ℝ that subsumes the loss, model, and data in L(f_θ(x),y) into one function of θ.
The goal is to minimize regret – the difference between the total loss and that of the optimal fixed action:



    _T=∑_t=1^Tℓ_t(θ_t)-min_θ∈Θ∑_t=1^Tℓ_t(θ)

When _T=o(T) then as T→∞ the average loss of the agent will approach that of an optimal fixed action.

For OCO, ℓ_t is assumed convex and Lipschitz for all t.
This setting provides many practically useful algorithms such as online gradient descent (OGD).
Parameterized by a starting point ϕ∈Θ and learning rate η>0, OGD plays

    θ_t=_Θ(ϕ-η∑_s<t∇ℓ_s(θ_s))


and achieves sublinear regret 𝒪(D√(T)) when η∝D/√(T), where D is the diameter of the action space Θ.

Note the similarity between OGD and the meta-initialization update in Equation <ref>.
In fact another fundamental OCO algorithm, follow-the-regularized-leader (FTRL), is a direct analog for the meta-regularization algorithm in Equation <ref>, with its action at each time being the output of ℓ_2-regularized ERM over the previous data:

    θ_t=_θ∈Θ1/2ηθ-ϕ_2^2+∑_s<tℓ_s(θ)

Note that most definitions set ϕ=0.
A crucial connection here is that on linear functions ℓ_t(·)=⟨∇_t,·⟩, OGD initialized at ϕ=0 plays the same actions θ_t∈Θ ∀ t∈[T] as FTRL.
Since linear losses are the hardest losses, in that low regret for them implies low regret for convex functions <cit.>, in the online setting this equivalence suggests that meta-initialization is a reasonable surrogate for meta-regularization because it is solving the hardest version of the problem.
The OGD-FTRL equivalence can be extended to other geometries by replacing the squared-norm in (<ref>) by a strongly-convex function R:Θ↦ℝ_+:



    θ_t=_θ∈Θ1/ηR(θ)+∑_s<tℓ_s(θ)

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 ∀ θ^∗∈Θ <cit.>:



    _T≤1/ηR(θ^∗)+η G^2T




 §.§ Task-Averaged Regret and Task Similarity


We consider the lifelong extension of online learning, where t=1,…,T now index a sequence of online learning problems, in each of which the agent must sequentially choose m_t actions θ_t,i∈ Θ and suffer loss ℓ_t,i:Θ↦ℝ.
Since in meta-learning we are interested in doing well on individual tasks, we will aim to minimize a dynamic notion of regret in which the comparator changes with each task, so that the comparator corresponds to the best within-task parameter:

	The task-averaged regret (TAR) of an online algorithm after T tasks with {m_t}_t=1^T steps is

	
    =1/T∑_t=1^T(∑_i=1^m_tℓ_t,i(θ_t,i)-min_θ_t∈Θ∑_i=1^m_tℓ_t,i(θ_t))




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∈[T]: their optimal actions θ_t^∗ lie within a small subset Θ^∗ of the action space.
This is natural for studying gradient-based meta-learning, as the notion that there exists a meta-parameter ϕ 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^∗ of Θ^∗;
notably, this means they will not do much worse if Θ^∗=Θ, i.e. if the tasks are not related in this way, but will do well if D^∗≪ D.
Importantly, our methods will not require knowledge of Θ^∗.

	Each task t∈[T] has m_t convex loss functions ℓ_t,i:Θ↦ℝ that are G_t-Lipschitz on-average.
	Let θ_t^∗∈_θ∈Θ∑_i=1^m_tℓ_t,i(θ) be the minimum-norm optimal fixed action for task t.
	Define Θ^∗⊂Θ to be the minimal subset containing θ_t^∗ ∀ t∈[T].
	Assume that Θ^∗ has non-empty interior (and thus T>1).


Note θ_t^∗ is unique as the minimum of ·^2, a strongly convex function, over minima of a convex function.
The algorithms in Section <ref> assume an efficient oracle computing θ_t^∗.





































































 §.§ Parameterizing Bregman Regularizers


Following the main idea of gradient-based meta-learning, our goal is to learn a ϕ∈Θ such that an online algorithm such as OGD starting from ϕ will have low regret.
We thus treat regret as our objective and observe that in the regret of FTRL (<ref>), the regularizer R effectively encodes a distance from the initialization to θ^∗.
This is clear in the Euclidean geometry for R(θ)=1/2θ-ϕ_2^2, but can be extended




via the Bregman divergence <cit.>, defined for f:S↦ℝ everywhere-sub-differentiable and convex as

    _f(x||y)=f(x)-f(y)-⟨∇ f(y),x-y⟩

The Bregman divergence has many useful properties <cit.> that allow us to use it almost directly as a parameterized regularization function.
However, in order to use OCO for the meta-update we also require it to be strictly convex in the second argument, a property that holds for the Bregman divergence of both the ℓ_2 regularizer and the entropic regularizer R(θ)=⟨θ,logθ⟩ used for online learning over the probability simplex, e.g. with expert advice.



	Let R:S↦ℝ be 1-strongly-convex w.r.t. norm · on convex S⊂ℝ^d.
	Then we call the Bregman divergence _R(x||y):S× S↦ℝ_+ a Bregman regularizer if _R(x||·) is strictly convex for any fixed x∈ S.


Within each task, the regularizer is parameterized by the second argument and acts on the first.
More specifically, for R=1/2·_2^2 we have _R(θ||ϕ)=1/2θ-ϕ_2^2, and so in the case of FTRL and OGD, ϕ 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 ϕ to θ and thus meta-learning ϕ can very explicitly be seen as learning a prior.

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

	_η,ϕ, for η∈ℝ_+,ϕ∈Θ, where Θ is some bounded convex subset Θ⊂ℝ^d, plays
	

	
    θ_t=_θ∈Θ_R(θ||ϕ)+η∑_s<tℓ_s(θ)

	for Bregman regularizer _R.
	Similarly, _η,ϕ plays
	

	
    θ_t=_θ∈Θ_R(θ||ϕ)+η∑_s<t⟨∇_s,θ⟩


Here FTRL and OMD correspond to the meta-regularization (<ref>) and meta-initialization (<ref>) approaches, respectively.
As _R(·||ϕ) is strongly-convex, both algorithms have the same regret bound (<ref>), allowing us to analyze them jointly.














 §.§ Follow-the-Meta-Regularized-Leader


We now specify the first variant of our main algorithm, Follow-the-Meta-Regularized-Leader ().
First assume the diameter D^∗ of Θ^∗, as measured by the square root of the maximum Bregman divergence between any two points, is known.
Starting with ϕ_1∈Θ, run _η,ϕ_t or _η,ϕ_t with η∝D^∗/√(m) on the losses in each task t.
After each task, compute ϕ_t+1 using an OCO meta-update algorithm operating on the Bregman divergences _R(θ_t^∗||·).
For D^∗ unknown, make an underestimate ε>0 and multiply it by a factor γ>1 each time _R(θ_t^∗||ϕ_t)>ε^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 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 <ref>.
For brevity, we state results for constant G_t=G,m_t=m ∀ t;
detailed statements are in the supplement together with the full proof.


	In Setting <ref>, the FAL variant of Algorithm <ref> with task similarity guess ε=D1+log T/T, tuning parameter γ=1+log T/log T, and _R that is Lipschitz on Θ^∗ achieves TAR
	
    ≤𝒪(D^∗+Dlog T/D^∗ T)√(m)

	for diameter D^∗=max_θ,ϕ∈Θ^∗√(_R(θ||ϕ)) of Θ^∗.


	We give a proof for R(·)=1/2·_2^2 and known task similarity, i.e. ε=D^∗,γ=1.
	Denote the divergence to θ_t^∗ by Δ_t(ϕ)=_R(θ_t^∗||ϕ)=1/2θ_t^∗-ϕ_2^2 and let ϕ^∗=1/T∑_t=1^Tθ_t^∗.
	Note Δ_t is 1-strongly-convex and ϕ^∗ is the minimizer of their sum, with the variance D̅^2=1/T∑_t=1^TΔ_t(ϕ^∗)≤D^∗^2.
	Now by Definition <ref>:
	
    =1/T∑_t=1^T(∑_i=1^mℓ_t,i(θ_t,i)-min_θ_t∈Θ∑_i=1^mℓ_t,i(θ_t))
       ≤1/T∑_t=1^TΔ_t(ϕ_t)/η+η G^2m
       =1/T∑_t=1^TΔ_t(ϕ_t)-Δ_t(ϕ^∗)/η+1/T∑_t=1^TΔ_t(ϕ^∗)/η+η G^2m

	The first two lines apply the regret bound (<ref>) 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 ϕ^∗ of the optimal actions θ_t^∗ on the right.
	Since Δ_1,…,Δ_T are 1-strongly-convex with minimizer ϕ^∗, and since each ϕ_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 𝒪(log T) <cit.>.
	Substituting the definition of ϕ^∗ and η=D^∗/G√(m) sets the right term to
	

	
    1/T∑_t=1^TΔ_t(ϕ^∗)/η+η G^2m=GD̅√(m)+GD^∗√(m)

	


The full proof uses the doubling trick to tune task similarity D^∗, requiring an analysis of the location of meta-parameter ϕ_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 D̅^2 of the task parameters from their mean ϕ^∗, setting η_t=D̅/G_t√(m_t) in Algorithm <ref> and following the analysis above replaces D^∗ in Theorem <ref> with D̅,
	which is better since D̅≤ D^∗ and is furthermore less sensitive to possible outlier tasks.




Theorem <ref> shows that the TAR of scales with task similarity D^∗, and that if tasks are not similar then we only do a constant factor worse than FTRL or OMD.
This shows that gradient-based meta-learning is useful in convex settings:
under a simple notion of similarity, having more tasks yields better performance than the 𝒪(D√(m)) regret of single-task learning.
The algorithm also scales well and in the ℓ_2 setting is similar to Reptile <cit.>.


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 θ_t^∗ 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 <ref>.
Indeed, in the proof of Theorem <ref> 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 <cit.>, shows that such constant factor reductions are the best we can achieve under our task similarity assumption:


	Assume d≥3 and that for each t∈[T] an adversary must play a sequence of m convex G-Lipschitz functions ℓ_t,i:Θ↦ℝ whose optimal actions in hindsight _θ∈Θ∑_i=1^mℓ_t,i(θ) are contained in some fixed ℓ_2-ball Θ^∗⊂Θ with center ϕ^∗ and diameter D^∗.
	Then the adversary can force the agent to have TAR at least GD^∗/4√(m).


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, -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 θ_t^∗ of each task that can learn a good meta-initialization or meta-regularization.
While θ_t^∗ is efficiently computable in some cases, often it is more practical to use an approximation.
This holds in the deep learning setting, e.g. <cit.> 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 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 are run in the distributional LTL setting.



 §.§ Simple-to-Compute Meta-Updates


To achieve guarantees using approximate meta-updates we need to make some assumptions on the within-task loss functions.
This is unavoidable because we need estimates of the optimal actions of different tasks to be nearby;
in general, for some θ∈Θ a convex function f:Θ↦ℝ can have small f(θ)-f(θ^∗) but large θ-θ^∗ if f does not increase quickly away from the minimum.
This makes it impossible to use guarantees on the loss of an estimate of θ_t^∗ to bound its distance from θ_t^∗.
We therefore make assumptions that some aggregate loss, e.g. the expectation or sum of the within-task losses, satisfies the following growth condition:

	A function f:Θ↦ℝ has α-quadratic-growth (α-QG) w.r.t. · for α>0 if for any θ∈Θ and θ^∗ its closest minimum of f we have
	

	
    α/2θ-θ^∗^2≤ f(θ)-f(θ^∗)


QG has recently been used to provide fast rates for GD that hold for practical problems such as LASSO and logistic regression under data-dependent assumptions <cit.>.
It can be shown when f(θ)=g(Aθ) for g strongly-convex and some A∈ℝ^m× d;
in this case α≥σ_min(A) <cit.>.
Note that α-QG is also a weaker condition than α-strong-convexity.



To prove FLI guarantees, we require in Setting <ref> 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 <ref>.

In Setting <ref>, for each task t∈[T] define average loss L_t according to one of the following two cases:




  (a) L_t(θ)=1/m_t∑_i=1^m_tℓ_t,i(θ)



  (b) assume losses ℓ_t,i:Θ↦[0,1] are i.i.d. from distribution 𝒫_t s.t. 
L_t(θ)=_𝒫_tℓ(θ) has a unique minimum 





Assume the corresponding L_t in each case is α-QG w.r.t. · and define Θ^∗⊂Θ s.t. Θ^∗⊃_θ∈ΘL(θ) ∀ t∈[T].

Here case (b) is the batch-within-online setting, also studied by <cit.>.
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 <ref>(a), the FLI-Online variant of Algorithm <ref> with ε=Ω(1/√(m)), tuning parameter γ≥1, and within-task algorithm FTRL with Bregman regularizer _R for R strongly-smooth w.r.t. · achieves TAR
	

	
    ≤𝒪(D^∗+D/D^∗(log T/T+o_m(1)))√(m)

	for D^∗ as in Theorem <ref> and o_m(1)=𝒪(m^-1/6).
	In Setting <ref>(b) the same bound holds w.p. 1-δ and o_m(1)=𝒪(m^-1/6√(logTm/δ)) for both the FAL and FLI-Batch variants and using either FTRL or OMD within-task. 

This bound is very similar to Theorem <ref> apart from a per-task error term due to the use of an estimate of θ_t^∗.





























 §.§ Distributional Learning-to-Learn


While gradient-based LTL methods are largely online, their goals are often statistical.
The usual setting due to <cit.> assumes a distribution 𝒬 over task-distributions 𝒫 over functions ℓ, which can correspond to a single-sample loss.
Given i.i.d. samples from each of T i.i.d. task-samples 𝒫_t∼𝒬, we seek to do learn how to do well given m samples from a new distribution 𝒫∼𝒬.
Here we hope that samples from 𝒬 can reduce the amount needed from 𝒫.





Theorem <ref> gives an online-to-batch conversion for which low TAR implies low expected risk of a new task sampled from 𝒬.
For , the procedure draws t∼𝒰[T], runs _η_t,ϕ_t or _η,ϕ_t on samples from 𝒫∼𝒬, and outputs the average iterate θ̅.
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 <cit.>.




	Suppose convex losses ℓ_t,i:Θ↦[0,1] are drawn i.i.d. from 𝒫_t∼𝒬,{ℓ_t,i}_i∼𝒫_t^m for some distribution 𝒬 over task distributions 𝒫_t.
	Let 𝒜_t be the state (e.g. the initialization ϕ_t and similarity guess D_t) before task t∈[T] of an algorithm 𝒜 with TAR .
	Then w.p. 1-δ if m loss functions {ℓ_i}_i∼𝒫^m are sampled from task distribution 𝒫∼𝒬, running 𝒜_t on these losses will generate θ_1,…,θ_m∈Θ s.t. their mean θ̅ satisfies
	

	
    _t∼𝒰[T]_[ ℓ∼𝒫; 𝒫∼𝒬 ]_𝒫^mℓ(θ̅)
    	=_[ ℓ∼𝒫; 𝒫∼𝒬 ]ℓ(θ^∗)+/m+√(8/Tlog1/δ)





























































































§ EMPIRICAL RESULTS


An important aspect of 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 <cit.>, 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.



 §.§ Convex Setting


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 <cit.>.
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 <cit.>.
We use logistic regression over 50-dimensional continuous-bag-of-words (CBOW) using GloVe embeddings <cit.>.
The similarity of these tasks is verified by seeing if their optimal parameters are close together.
As shown before in Figure <ref>, we find when Θ 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 to the “strawman" algorithm from Section <ref>, which uses the previous optimal action as the initialization.
For both algorithms we use similarity guess ε=0.1 and tune with γ=1.1.
As expected, in Figure <ref> we see that 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 and (first-order) MAML in the statistical setting.
On each task we standardize data using the mean and deviation of the training features.
For 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 <ref>.
For MAML, we use grid search to determine the within-task and meta-update learning rates.
As shown in Figure <ref>, despite using no tuning, performs comparably to MAML  – slightly better for m≥ 8 and slightly worse for m<4.



 §.§ Deep Learning


While our method generalizes Reptile, an effective meta-learning method <cit.>, we can still examine if our theory can help neural network LTL.
We study modifications of Reptile on 5-way and 20-way Omniglot <cit.> and 5-way Mini-ImageNet classification <cit.> using the same networks as <cit.>.
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 <ref> assumes access to this parameter, whereas Theorems <ref> 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 <ref>, 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 <ref> 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 <ref>(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, , 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.


icml2019







§ BACKGROUND AND RESULTS FOR ONLINE CONVEX OPTIMIZATION


Throughout the appendix we assume all subsets are convex and in ℝ^d unless explicitly stated.
Let ·_∗ be the dual norm of ·, which we assume to be any norm on ℝ^d, and note that the dual norm of ·_2 is itself.
For sequences of scalars σ_1,…,σ_T∈ℝ we will use the notation σ_1:t to refer to the sum of the first t of them.
In the online learning setting, we will use the shorthand ∇_t to denote the subgradient of ℓ_t:Θ↦ℝ evaluated at action θ_t∈Θ.
We will use (S) to refer to the convex hull of a set of points S and _S(·) to be the projection to any convex subset S⊂ℝ^d.



 §.§ Convex Functions


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

	An everywhere sub-differentiable function f:S↦ℝ is α-strongly-convex w.r.t. norm · if
	
    f(y)≥ f(x)+⟨∇ f(x),y-x⟩+α/2y-x^2 ∀ x,y∈ S



	An everywhere sub-differentiable function f:S↦ℝ is β-strongly-smooth w.r.t. norm · if
	
    f(y)≤ f(x)+⟨∇ f(x),y-x⟩+β/2y-x^2 ∀ x,y∈ S
















We now turn to the Bregman divergence and a discussion of several useful properties <cit.>:

	Let f:S↦ℝ be an everywhere sub-differentiable strictly convex function.
	Its Bregman divergence is defined as
	
    _f(x||y)=f(x)-f(y)-⟨∇ f(y),x-y⟩

	The definition directly implies that _f(·||y) preserves the (strong or strict) convexity of f for any fixed  y∈ S.
	Strict convexity further implies _f(x||y)≥0 ∀ x,y∈ S, with equality iff x=y.
	Finally, if f is α-strongly-convex, or β-strongly-smooth, w.r.t. · then Definition <ref> implies _f(x||y)≥α/2x-y^2, or _f(x||y)≤β/2x-y^2, respectively.


	Let f:S↦ℝ be a strictly convex function on S, α_1,…,α_n∈ℝ be a sequence satisfying α_1:n>0, and x_1,…,x_n∈ S.
	Then 
	
    x̅=1/α_1:n∑_i=1^nα_ix_i=_y∈ S∑_i=1^nα_i_f(x_i||y)



	∀ y∈ S we have
	
    ∑_i=1^nα_i(_f(x_i||y)-_f(x_i||x̅))
    		   =∑_i=1^nα_i(f(x_i)-f(y)-⟨∇ f(y),x_i-y⟩-f(x_i)+f(x̅)+⟨∇ f(x̅),x_i-x̅⟩)
       =(f(x̅)-f(y)+⟨∇ f(y),y⟩)α_1:n+∑_i=1^nα_i(-⟨∇ f(x̅),x̅⟩+⟨∇ f(x̅)-∇ f(y),x_i⟩)
       =(f(x̅)-f(y)-⟨∇ f(y),x̅-y⟩)α_1:n
       =α_1:n_f(x̅||y)

	By Definition <ref> the last expression has a unique minimum at y=x̅.




 §.§ Standard Online Algorithms


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

	The regret of an agent playing actions {θ_t∈Θ}_t∈[T] on a sequence of loss functions {ℓ_t:Θ↦ℝ}_t∈[T] is
	
    _T=∑_t=1^Tℓ_t(θ_t)-min_θ∈Θ∑_t=1^Tℓ_t(θ)


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

	Given a strictly convex function R:Θ↦ℝ, starting point ϕ∈Θ, fixed learning rate η>0, and a sequence of functions {ℓ_t:Θ↦ℝ}_t≥1, Follow-the-Regularized Leader (_ϕ,η^(R)) plays
	
    θ_t=_θ∈Θ_R(θ||ϕ)+η∑_s<tℓ_s(θ)



	Given a strictly convex function R:Θ↦ℝ, starting point ϕ∈Θ, fixed learning rate η>0, and a sequence of functions {ℓ_t:Θ↦ℝ}_t≥1, lazy linearized Online Mirror Descent (_ϕ,η^(R)) plays
	
    θ_t=_θ∈Θ_R(θ||ϕ)+η∑_s<t⟨∇_s,θ⟩



These formulations make the connection between the two algorithms – their equivalence in the linear case ℓ_s(·)=⟨∇_s,·⟩ – very explicit.
There exists a more standard formulation of OMD that is used to highlight its generalization of OGD – the case of R(·)=1/2·_2^2 – and the fact that the update is carried out in the dual space induced by R <cit.>.
However, we will only need the following regret bound satisfied by both <cit.>

	Let {ℓ_t:Θ↦ℝ}_t∈[T] be a sequence of convex functions that are G_t-Lipschitz w.r.t. · and let R:S↦ℝ be 1-strongly-convex.
	Then the regret of both _η,ϕ^(R) and _η,ϕ^(R) is bounded by
	
    _T≤_R(θ^∗||ϕ)/η+η G^2T

	for all θ^∗∈Θ and G^2≥1/T∑_t=1^TG_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:

	Given a sequence of strictly convex functions {ℓ_t:Θ↦ℝ}_t≥1, Follow-the-Leader (FTL) plays arbitrary θ_1∈Θ and for t>1 plays
	
    θ_t=_θ∈Θ∑_s<tℓ_s(θ)



	Given a sequence of functions {ℓ_t:Θ↦ℝ}_t≥1 that are α_t-strongly-convex w.r.t. ·_2, Adaptive OGD (AOGD) plays arbitrary θ_1∈Θ and for t>1 plays
	
    θ_t+1=_Θ(θ_t-1/α_1:t∇ f(θ_t))



<cit.> and <cit.> provide for FTL and AOGD, respectively, the following regret bound:

	Let {ℓ_t:Θ↦ℝ}_t∈[T] be a sequence of convex functions that are G_t-Lipschitz and α_t-strongly-convex w.r.t. ·.
	Then the regret of both FTL and AOGD is bounded by
	
    _T≤1/2∑_t=1^TG_t^2/α_1:t



One further useful fact about FTL and AOGD is that when run on a sequence of Bregman regularizers _R(θ_1||·),…,_R(θ_T||·) they will play points in the convex hull ({θ_t}_t∈[T]):


	Let R:Θ↦ℝ be 1-strongly-convex w.r.t. · and consider any θ_1,…,θ_T∈Θ^∗ for some convex subset Θ^∗⊂Θ.
	Then for loss sequence α_1_R(θ_1||·),…,α_T_R(θ_T||·) for any positive scalars α_1,…,α_T∈ℝ_+, if we assume ϕ_1∈Θ^∗ then FTL will play ϕ_t∈Θ^∗ ∀ t and AOGD will as well if we further assume R(·)=1/2·^2.


	The proof for FTL follows directly from Claim <ref> 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 ϕ_t∈Θ^∗.
	In the inductive case, note that _R(θ_t||ϕ_t)=1/2θ_t-ϕ_t_2^2 so the gradient update is ϕ_t+1=ϕ_t+α_t/α_1:t(θ_t-ϕ_t), which is on the line segment between ϕ_t and θ_t, so the proof is complete by the convexity of Θ^∗∋ϕ_t,θ_t.















































 §.§ 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:

	If a sequence of bounded convex loss functions {ℓ_t:Θ↦ℝ}_t∈[T] drawn i.i.d. from some distribution 𝒟 is given to an online algorithm with regret bound _T that generates a sequence of actions {θ_t∈Θ}_t∈[T] then for θ̅=1/Tθ_1:T and any θ^∗∈Θ we have
	
    _𝒟^T_ℓ∼𝒟ℓ(θ̅)≤_ℓ∼𝒟ℓ(θ^∗)+_T/T



	Applying Jensen's inequality and using the fact that θ_t only depends on ℓ_1,…,ℓ_t-1 we have
	
    _𝒟^T_ℓ∼𝒟ℓ(θ̅)
    	≤1/T_𝒟^T∑_t=1^T_ℓ_t'∼𝒟ℓ_t'(θ_t)
    	   =1/T_{ℓ_t}∼𝒟^T(∑_t=1^T_ℓ_t'∼𝒟ℓ_t'(θ_t)-ℓ_t(θ_t))+1/T_{ℓ_t}∼𝒟^T(∑_t=1^Tℓ_t(θ_t))
       ≤1/T∑_t=1^T_{ℓ_s}_s<t∼𝒟^t-1(_ℓ_t'∼𝒟ℓ_t'(θ_t)-_ℓ_t∼𝒟ℓ_t(θ_t))+_T/T+1/T∑_t=1^T_ℓ∼𝒟ℓ(θ^∗)
       =_T/T+_ℓ∼𝒟ℓ(θ^∗)





	If a sequence of loss functions {ℓ_t:Θ↦[0,1]}_t∈[T] drawn i.i.d. from some distribution 𝒟 is given to an online algorithm that generates a sequence of actions {θ_t∈Θ}_t∈[T] then the following inequalities each hold w.p. 1-δ:
	
    1/T∑_t=1^T_ℓ∼𝒟ℓ(θ_t)≤1/T∑_t=1^Tℓ_t(θ_t)+√(2/Tlog1/δ)    and    1/T∑_t=1^T_ℓ∼𝒟ℓ(θ_t)≥1/T∑_t=1^Tℓ_t(θ_t)-√(2/Tlog1/δ)


Note that <cit.> only prove the first inequality;
the second follows via the same argument but applying the symmetric version of the Azuma-Hoeffding inequality <cit.>.


	If a sequence of loss functions {ℓ_t:Θ↦[0,1]}_t∈[T] drawn i.i.d. from some distribution 𝒟 is given to an online algorithm with regret bound _T that generates a sequence of actions {θ_t∈Θ}_t∈[T] then
	
    _t∼𝒰[T]_ℓ∼𝒟ℓ(θ_t)≤_ℓ∼𝒟ℓ(θ^∗)+_T/T+√(8/Tlog1/δ)    w.p. 1-δ

	for any θ^∗∈Θ.





	By Proposition <ref> we have
	
    1/T∑_t=1^T_ℓ∼𝒟ℓ(θ_t)
    	≤1/T∑_t=1^Tℓ_t(θ^∗)+_T/T+√(2/Tlog1/δ)≤_ℓ∼𝒟ℓ(θ^∗)+_T/T+√(8/Tlog1/δ)


















































§ 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 <ref> define the following quantities:
	
		
  * convenience coefficients σ_t=G_t√(m_t)
		
  * the sequence of update parameters {θ̂_t∈Θ}_t∈[T] with average update parameter ϕ̂=1/σ_1:T∑_t=1^Tσ_tθ̂_t
		
  * a sequence of reference parameters {θ_t'∈Θ}_t∈[T] with average reference parameter ϕ'=1/σ_1:T∑_t=1^Tσ_tθ_t'
		
  * a sequence {θ_t^∗∈Θ}_t∈[T] of optimal parameters in hindsight
		
  * we will say we are in the “Exact" case if θ̂_t=θ_t'=θ_t^∗ ∀ t and the “Approx" case otherwise
		
  * κ≥1,Δ_t^∗≥0 s.t. ∑_t=1^Tα_t_R(θ_t^∗||ϕ_t)≤∑_t=1^Tα_tΔ_t^∗+κ∑_t=1^Tα_t_R(θ̂_t||ϕ_t) for some nonnegative α_t
		
  * ν≥1,Δ'≥0 s.t. ∑_t=1^Tσ_t_R(θ̂_t||ϕ̂)≤Δ'+ν∑_t=1^Tσ_t_R(θ_t'||ϕ')
		
  * Δ_max≥0 s.t. 1/2θ_t'-θ̂_t^2≤Δ_max ∀ t∈[T]
		
  * average deviation D̅^2=1/σ_1:T∑_t=1^Tσ_t_R(θ_t'||ϕ') of the reference parameters; assumed positive
		
  * task diameter D^∗=max_θ,ϕ∈({θ_t'}_t∈[T])√(_R(θ||ϕ)); assumed positive
		
  * action diameter D^2=max{D^∗^2,max_θ∈Θ_R(θ||ϕ_1)} in the Exact case or max_θ,ϕ∈Θ_R(θ||ϕ) in the Approx case
		
  * universal constant C' s.t. θ≤ C'θ_2 ∀ θ∈Θ and ℓ_2-diameter D'=max_θ,ϕθ-ϕ_2 of Θ
		
  * upper bound G' on the Lipschitz constants of the functions {_R(θ̂_t||·)}_t∈[T] over ({θ̂_t}_t=1^T)
		
  * we will say we are in the “Nice" case if _R(θ||·) is 1-strongly-convex and β-strongly-smooth w.r.t. · ∀ θ∈Θ
		
  * in the general case  is FTL; in the Nice case  may instead be AOGD re-initialized at θ_1^∗
		
  * convenience indicator ι=1_=
		
  * effective meta-action space Θ̂=({θ̂_t}_t∈[T]) if  is FTL or Θ if  is AOGD
		
  * _η,ϕ=_η,ϕ^(R) or _η,ϕ^(R)
	
	We make the following assumptions:
	
		
  * the loss functions ℓ_t,i are convex ∀ t,i
		
  * at time t=1 the update algorithm  plays ϕ_1∈Θ satisfying max_θ∈Θ_R(θ||ϕ_1)<∞
		
  * in the Approx case R is β-strongly-smooth for some β≥1
	





































 §.§ Upper Bound


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.

	For any θ_1,…,θ_T∈ S and positive scalars α_1,…,α_T∈ℝ_+ define ϕ_t=1/α_1:t∑_s=1^tα_tθ_t and let ϕ_0 be any point in S.
	Then
	
    ∑_t=1^Tα_tθ_t-ϕ_t-1_2^2-∑_t=1^Tα_tθ_t-ϕ_T_2^2≥0



	We proceed by induction on T.
	The base case T=1 follows directly since ϕ_1=θ_1 and so the second term is zero.
	In the inductive case we have
	
    ∑_t=1^T-1α_tθ_t-ϕ_t-1_2^2-∑_t=1^T-1α_tθ_t-ϕ_T-1_2^2≥0

	so it suffices to show
	
    ϕ_T-1=_θ_T∑_t=1^Tα_tθ_t-ϕ_t-1_2^2-∑_t=1^Tα_tθ_t-ϕ_T_2^2

	in which case ϕ_T=ϕ_T-1 and both added terms are zero, preserving the inequality.
	The gradient and Hessian are
	
    2α_T(θ_T-ϕ_T-1)+2α_T/α_1:T∑_t=1^T-1α_t(θ_t-ϕ_T)-2α_T(θ_T-ϕ_T)(1-α_T/α_1:T)

	
    2α_T(1-α_Tα_1:T-1/α_1:T^2-1+2α_T/α_1:T-α_T^2/α_1:T^2)I=2α_T^2/α_1:TI≽0

	so the problem is strongly convex and thus has a unique global minimum.
	Setting the gradient to zero yields
	
    0=θ_T-ϕ_T-1+1/α_1:T∑_t=1^T-1α_tθ_t-1/α_1:T∑_t=1^T-1α_tϕ_T-θ_T+α_T/α_1:Tθ_T+ϕ_T-α_T/α_1:Tϕ_T=ϕ_T-ϕ_T-1θ_T=ϕ_T-1


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 <ref> cannot be applied directly.

	Let _R be a Bregman regularizer on S w.r.t. · and consider any θ_1,…,θ_T∈ S.
	Then for loss sequence α_1_R(θ_1||·),…,α_T_R(θ_T||·) for any positive scalars α_1,…,α_T∈ℝ_+ we have regret bound
	
    _T≤G_R^2+1/2∑_t=1^Tα_t/α_1:t

	where G_R is the Lipschitz constant of the Bregman regularizer _R(θ_t||·) for any t∈[T] on S w.r.t. the Euclidean norm.


	Defining ϕ̅=1/α_1:T∑_t=1^Tα_tθ_t, we apply Claim <ref> and Lemma <ref> to get
	
    _T
    	   =∑_t=1^Tα_t_R(θ_t||ϕ_t)-min_ϕ∈ S∑_t=1^Tα_t_R(θ_t||ϕ)
       ≤∑_t=1^Tα_t_R(θ_t||ϕ_t)-∑_t=1^Tα_t_R(θ_t||ϕ̅)+1/2∑_t=1^Tα_tθ_t-ϕ_t_2^2-1/2∑_t=1^Tα_tθ_t-ϕ̅_2^2
       =∑_t=1^Tα_t_R(θ_t||ϕ_t)+α_t/2θ_t-ϕ_t_2^2-min_ϕ∈ S∑_t=1^Tα_t_R(θ_t||ϕ)+α_t/2θ_t-ϕ_2^2

	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 <cit.> yields the result.


The following result is our main theorem; 
Theorems <ref> and <ref> will follow as corollaries.


	In Setting <ref>, Algorithm <ref> has TAR bounded as
	
    ≤1/T((2κ D+ε)σ_1+κ C/ρ D^∗∑_t=1^Tσ_t^2/σ_1:t+κ(νD̅^2/ρ D^∗+γ(ρ D^∗+ℰ)+ε)σ_1:T)
           +1/T(Δ_1:T^∗/ε+κΔ'/ρ D^∗+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k)

	for C=G'^2/2 in the Nice case or otherwise C=C'D'(G'+1)/2, ρ=1 in the Exact case or ρ=2√(β) in the Approx case, and ℰ=2√(2βΔ_max).


	We first use the β-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∈[T]:
	
    _R(θ̂_t||ϕ_t)
    		≤β/2θ̂_t-ϕ_t^2
    		   ≤β(θ̂_t-θ_t'^2+θ_t'-ϕ_t^2)
       ≤β(θ̂_t-θ_t'^2+max_s<t2θ_t'-θ_s'^2+2θ_s'-θ̂_s^2)
       ≤4βD^∗^2+4βmax_tθ_t'-θ̂_t^2
       ≤4βD^∗^2+8βΔ_max

	Combining this bound with the Exact setting assumption yields _R(θ̂_t||ϕ_t)≤ρ^2D^∗^2+8βΔ_max≤ρ^2D^∗^2+ℰ^2 ∀ t∈[T].	
	We now turn to analyzing the regret by defining two “cheating" sequences: ϕ̃_t=ϕ_t on all t except t=1, when we set ϕ̃_1=θ_1^∗;
	similarly, D̃_t=D_t on all t except t=1 and any t s.t. _R(θ̂_t||ϕ_t)>D_t^2, when we set D̃_t=ρ D^∗+ℰ.
	In order to do this we add outside of the summation the corresponding regret of the true sequences whenever one of them is not the same as its “cheating" sequence.
	Note that by this definition all upper bounds of _R(θ̂_t||ϕ_t) also upper bound _R(θ̂_t||ϕ̃_t).
	Furthermore the times t s.t. _R(θ_t^∗||ϕ_t)>D_t^2 corresponds exactly to the times that the violation count k is incremented in Algorithm <ref> and thus this occurs at most log_γρ D^∗+ℰ/ε times, as we multiply the diameter guess by γ each time it happens, which together with Lemma <ref> ensures that ϕ_t remains within max{γ(ρ D^∗+ℰ),ε} of all the reference parameters θ_t'.
	We index these times by k=0,…, so that at each k the agent uses η_t_k set using γ^kε.
	
    T
    		   =∑_t=1^T_R(θ_t^∗||ϕ_t)/η_t+η_tG_t^2m_t
       ≤Δ_1:T^∗/ε+∑_t=1^T(κ_R(θ̂_t||ϕ_t)/D_t+D_t)σ_t    (substitute η_t=D_t/G_t√(m_t) and D_t≥ε)
       ≤(κ_R(θ̂_1||ϕ_1)/D_1+D_1)σ_1+Δ_1:T^∗/ε    (substitute cheating sequence)
           +∑_t=1^T(κ_R(θ̂_t||ϕ̃_t)/D̃_t+D̃_t)σ_t+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ_R(θ̂_t_k||ϕ_t_k)/γ^kε+γ^kε)σ_t_k
       ≤((κ+1)D+ε)σ_1+Δ_1:T^∗/ε+κ∑_t=1^T(_R(θ̂_t||ϕ̃_t)/D̃_t+D̃_t)σ_t+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k

	
	We now bound the third term.
	For any t∈[T] define B_t^2=_R(θ̂_t||ϕ̃_t) and f_t(x)=B_t^2/x+x.
	Its derivative ∂_xf_t=1-B_t^2/x^2 is nonnegative on x≥ B_t.
	Thus when D̃_t≤ρ D^∗+ℰ we have f(D̃_t)≤ f(ρ D^∗+ℰ), as by definition both are greater than B_t and so f_t is increasing on the interval between them.
	On the other hand, for D̃_t≥ρ D^∗+ℰ, either D̃_t≤γ(ρ D^∗+ℰ) by the tuning rule or, if we initialized ε>ρ D^∗+ℰ, then D̃_t=ε ∀ t∈[T], so either way we have f_t(D̃_t)≤B_t^2/ρ D^∗+max{γ(ρ D^∗+ℰ),ε} ∀ t∈[T].
	Since γ>1 this bounds f(D̃_t) in the previous case D̃_t≤ρ D^∗+ℰ as well, so we have
	
    T
    		   ≤((1+κ) D+ε)σ_1+Δ_1:T^∗/ε+κ∑_t=1^T(_R(θ̂_t||ϕ̃_t)/D̃_t+D̃_t)σ_t+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k
       ≤(2κ D+ε)σ_1+Δ_1:T^∗/ε+κ∑_t=1^T(_R(θ̂_t||ϕ̃_t)/ρ D^∗+γ(ρ D^∗+ℰ)+ε)σ_t+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k
       ≤(2κ D+ε)σ_1+Δ_1:T^∗/ε+κ/ρ D^∗∑_t=1^T(_R(θ̂_t||ϕ̃_t)-_R(θ̂_t||ϕ̂))
           +κ∑_t=1^T(_R(θ̂_t||ϕ̂)/ρ D^∗+γ(ρ D^∗+ℰ)+ε)σ_t+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k
       ≤(2κ D+ε)σ_1+Δ_1:T^∗/ε+κ C/ρ D^∗∑_t=1^Tσ_t^2/σ_1:t+κΔ'/ρ D^∗    (Thm. <ref> and Lem. <ref>)
           +κ∑_t=1^T(ν_R(θ_t'||ϕ')/ρ D^∗+γ(ρ D^∗+ℰ)+ε)σ_t+∑_k=0^⌊log_γκ(ρ D^∗+ℰ)/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k
       =(2κ D+ε)σ_1+Δ_1:T^∗/ε+κ C/ρ D^∗∑_t=1^Tσ_t^2/σ_1:t+κΔ'/ρ D^∗
           +κ(νD̅^2/ρ D^∗+γ(ρ D^∗+ℰ)+ε)σ_1:T+∑_k=0^⌊log_γρ D^∗+ℰ/ε⌋(κ(ρ D^∗+ℰ)/γ^kε+γ^kε)σ_t_k



The following result corresponds to the general case of Theorem <ref>.

	In the Exact case of Setting <ref>, if G_t=G,m_t=m ∀ t∈[T], the FAL variant of Algorithm <ref> has TAR
	
    ≤(2D+2ε+C/D^∗(1+log T)+γ/γ-1(D^∗^2/ε+D^∗)/T+D̅^2/D^∗+γ D^∗+ε)G√(m)

	If we assume known D, picking ε=D1+log T/T and γ=1+log T/log T yields
	
    ≤((6D+C/D^∗)1+log T/T+9/2D^∗)G√(m)



	For K=⌊log_γD^∗/ε⌋ we have
	
    ∑_k=0^K(D^∗^2/γ^kε+γ^kε)
    	=(γ^K+1-1)(D^∗^2+γ^Kε^2)/γ^K(γ-1)ε≤γ/γ-1(D^∗^2/ε+D^∗)

	The result follows by noting that in the exact case we have κ=ν=ρ=1,Δ_1:T^∗=Δ'=Δ_max=0, and substituting ∑_t=1^T1/t≤(1+log T).

















































































 §.§ Lower Bound


The following lower bound, which extends Theorem 4.2 of <cit.> 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^∗, since D^∗≥D̅ the same lower bound holds for the average task deviation as well.


	Suppose the action space is Θ⊂ℝ^d for d≥3 and for each task t∈[T] an adversary must play a a sequence of m_t convex G_t-Lipschitz functions ℓ_t,i:Θ↦ℝ whose optimal actions in hindsight _θ∈Θ∑_i=1^m_tℓ_t,i(θ) are contained in some fixed ℓ_2-ball Θ^∗⊂Θ with center ϕ^∗ and diameter D^∗.
	Then the adversary can force the agent to have task-averaged regret at least D^∗/4T∑_t=1^TG_t√(m_t).


	Let {θ_t,i}_i=1^m be the sequence of actions of the agent on task t.
	Define c(θ)=G_t/2max{0,θ-ϕ^∗_2-D^∗}, which is 0 on Θ^∗ and an upward-facing cone with vertex (ϕ^∗,-G_tD^∗/2) and slope G_t/2 on the complement.
	The strategy of the adversary at round i of task t will be to play ℓ_t,i(θ)=⟨∇_t,i,θ-ϕ^∗⟩+c(θ), where ∇_t,i satisfies ∇_t,i_2=G_t/2, ⟨∇_t,i,θ_t,i-ϕ^∗⟩=0, and ⟨∇_t,i,∇_t,1:i-1⟩=0.
	Such a ∇_t,i always exists for d≥3.
	Note that these conditions imply that along any direction from ϕ^∗ the total loss ∑_i=1^m_tℓ_t,i(θ) is increasing outside Θ^∗ and so is minimized inside Θ^∗, so we have
	
    min_θ∈Θ∑_i=1^m_tℓ_t,i(θ)
    	=min_θ∈Θ^∗∑_i=1^m_t⟨∇_t,i,θ-ϕ^∗⟩
    	=min_θ-ϕ^∗_2≤D^∗/2⟨θ-ϕ^∗,∇_t,1:m_t⟩
    	=-D^∗/2∇_t,1:m_t_2

	Note that the condition ⟨∇_t,i,θ_t,i-ϕ^∗⟩=0 and the nonnegativity of c(θ) implies that the loss of the agent is at least 0, and so the agent's regret on task t satisfies _m_t≥D^∗/2∇_t,1:m_t_2.
	By the condition ⟨∇_t,i,∇_t,1:i-1⟩=0 we have that
	
    ∇_t,1:i_2^2
    	=∇_t,i+∇_t,1:i-1_2^2
    	=∇_t,i_2^2+∇_t,1:i-1_2^2
    	=G_t^2/4+∇_t,i-1_2^2

	and so by induction on i with base case ∇_t,1_2=G_t/2 we have ∇_t,1:m_t_2=G_t/2√(m_t)_m_t≥G_tD^∗/4√(m_t).
	Substituting the regret on each task into =1/T∑_t=1^T_m_t completes the proof.




 §.§ 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 α-QG assumption on the average loss functions to obtain stability of the estimates w.r.t. the true loss.








	Let ℓ_1,…,ℓ_m be a sequence of convex losses on Θ with L(θ)=1/m∑_i=1^mℓ(θ) being α-QG w.r.t. · and define θ̂=_θ∈Θ_R(θ||ϕ)+η mL(θ) to be the last iterate of running _η,ϕ^(R) for η>0,ϕ∈Θ, and R:Θ↦ℝ 1-strongly-convex w.r.t. ·.
	Then the closest minimum θ^∗∈Θ of L to θ̂ satisfies
	
    1/2θ^∗-θ̂^2≤_R(θ^∗||ϕ)-_R(θ̂||ϕ)/αη m



	We have by definition of θ' and θ̂ that
	
    _R(θ^∗||ϕ)+η mL(θ^∗)
    	≥_R(θ̂||ϕ)+η mL(θ̂)

	On the other hand since L is α-QG we have that
	
    L(θ̂)≥ L(θ^∗)+α/2θ^∗-θ̂^2

	Multiplying the second inequality by η m and adding it to the first yields the result.



	In Setting <ref> , if for each task t∈[T] the losses ℓ_t,1,…,ℓ_t,m_t satisfy the α-QG condition as in Lemma <ref> and ε≥max_t4β G_t/α√(m_t), then for θ̂_t set according to the FLI-Online algorithm and θ_t^∗=θ_t' ∀ t∈[T] we have
	
    κ=4β,
    	    Δ_t^∗=0 ∀ t∈[T],
    	    ν=3β,
    	    Δ'=6β D^2/αε∑_t=1^TG_tσ_t/√(m_t),
    	    Δ_max=max_tD^2G_t/αε√(m_t)



	Applying the triangle inequality, Jensen's inequality, and Lemma <ref> yields the first two values:
	
    θ_t^∗-ϕ_t^2
    	≤2θ_t^∗-θ̂_t^2+2θ̂_t-ϕ_t^2
    	≤4_R(θ_t^∗||ϕ_t)/αη_tm_t+4_R(θ̂_t||ϕ_t)
    	≤2β/αη_tm_tθ_t^∗-ϕ_t^2+4_R(θ̂_t||ϕ_t)

	
    _R(θ_t^∗||ϕ_t)
    	≤β/2θ_t^∗-ϕ_t^2
    	≤2β_R(θ̂_t||ϕ_t)/1-2β/αη_tm_t≤4β_R(θ̂_t||ϕ_t)

	Here in the last step we used the fact that ε≥4β G_t/α√(m_t)η_t≥4β/α m_t ∀ t∈[T].
	For the next two values, noting that for FLI-Online, θ_t^∗=θ_t' ∀ t∈[T] we have by the triangle inequality and Titu's lemma that
	
    ϕ'-ϕ̂^2
    	=1/(σ_1:T)^2∑_t=1^Tσ_tθ_t'-∑_t=1^Tσ_tθ̂_t^2
    	≤1/(σ_1:T)^2(∑_t=1^Tσ_tθ_t'-θ̂_t)^2
    	≤1/σ_1:T∑_t=1^Tσ_tθ_t'-θ̂_t^2

	Therefore since η≥ε/σ_t and _R(θ_t^∗||ϕ_t)≤ D^2 we have that
	
    ∑_t=1^Tσ_t_R(θ̂_t||ϕ̂)
    	≤3β/2∑_t=1^Tσ_t(θ̂_t-θ_t'^2+θ_t'-ϕ'^2+ϕ'-ϕ̂^2)
    	≤3β∑_t=1^Tσ_t(2_R(θ_t^∗||ϕ_t)/αη_tm_t+_R(θ_t'||ϕ'))

	The last value follows directly by Lemma <ref>, η_t≥ε/σ_t, and the bound D^2 on the maximum Bregman divergence.


The following upper bound yields Theorem <ref>:

	In the Approx. case of Setting <ref>, if G_t=G,m_t=m ∀ t∈[T],γ=1+log T/log T, and ε=4β G/α√(m)+D1+log T/T then the FLI-Online variant of Algorithm <ref> has TAR
	
    =𝒪(D/D^∗(log T/T+1/√(m))+D^∗)G√(m)



	Substitute Proposition <ref> into Theorem <ref> and simplify.



	Let ℓ_1,…,ℓ_m:Θ↦[0,1] be a sequence of convex losses on Θ drawn i.i.d. from some distribution 𝒟 with risk _ℓ∼𝒟ℓ being α-QG w.r.t. · and let θ^∗∈_θ∈Θ∑_i=1^mℓ_i(θ) be any of the optimal actions in hindsight.
	Then w.p. 1-δ the closest minimum θ'∈Θ of _ℓ∼𝒟ℓ to θ^∗ satisfies
	
    1/2θ^∗-θ'^2≤√(8/α^2mlog2/δ)



	By definition of θ^∗ and θ' we have w.p. 1-δ that
	
    α/2θ^∗-θ'^2
    	   ≤1/m_{ℓ_i}∼𝒟^m∑_i=1^mℓ_i(θ^∗)-1/m_{ℓ_i}∼𝒟^m∑_i=1^mℓ_i(θ')    (apply α-QG)
       ≤1/m∑_i=1^mℓ_i(θ^∗)-1/m∑_i=1^mℓ_i(θ')+√(8/mlog2/δ)    (apply Prp. <ref> twice)
       ≤√(8/mlog2/δ)    (definition of θ^∗)




	Suppose ∀ t∈[T] the r.v. Q_t satisfies 0≤ Q_t≤ B a.s. and Q_t≤√(8/m_tlog2/δ) w.p. 1-δ for any δ∈(0,1).
	Then for nonnegative α_1,…,α_T we have w.p. 1-γ for any γ∈(0,1) that
	
    ∑_t=1^Tα_tQ_t≤2Bα_max/3log1/γ+2∑_t=1^Tα_t√(1+4log(Bm_t)/m_t(1+log1/γ))



	Define convenience coefficients β_t=α_t/α_1:T, the auxiliary sequence Z_t=β_tQ_t ∀ t∈[T], the martingale sequence Y_0=0,Y_t=Z_1:t- Z_1:t ∀ t∈[T] and the  associated martingale difference sequence X_t=Y_t-Y_t-1 ∀ t∈[T].
	By substituting δ=2/Bm_t we then have
	
    𝔼_t-1X_t^2
    	=𝔼_t-1(Y_t-Y_t-1)^2
    	=β_t^2(Q_t- Q_t)^2
    	≤β_t^2 Q_t^2
    	≤β_t^2(8/m_tlog2/δ+δ B)
    	≤2+8log(Bm_t)/m_tβ_t^2

	Note further that using δ=2/√(Bm_t) and Jensen's inequality we have
	
    Q_t
    	≤√(8/m_tlog2/δ)+δ B
    	≤√(4+8log(Bm_t)/m_t)

	Noting that Q_t≤ B a.s. X_t≤ B a.s., we have by Freedman's inequality <cit.> that
	
    ℙ(∑_t=1^Tβ_tQ_t≥τ+2∑_t=1^Tβ_t√(1+2log(Bm_t)/m_t))
    	≤ℙ(∑_t=1^Tβ_tQ_t≥τ+∑_t=1^Tβ_t Q_t)
    	≤exp(-τ^2/2σ^2+2Bβ_max/3τ)

	for τ≥0,σ^2=∑_t=1^T2+8log(Bm_t)/m_tβ_t^2.
	Substituting
	τ=2β_max/3log1/γ+√(2σ^2log1/γ) yields
	
    ℙ(∑_t=1^Tβ_tQ_t≥2Bβ_max/3log1/γ+2∑_t=1^Tβ_t√(1+2log(Bm_t)/m_t)+√(2log1/γ∑_t=1^T2+8log(Bm_t)/m_tβ_t^2))≤γ




	In Setting <ref>, if for each task t∈[T] the losses ℓ_t,1,…,ℓ_t,m_t and reference parameter θ_t' satisfy the α-QG condition as in Lemma <ref>, then for θ̂_t=θ_t^∗ set according to the FAL algorithm we have w.p. 1-δ that κ=1,ν=3β,
	
    Δ_t^∗=0 ∀ t∈[T],
    	  Δ'=4β/α(σ_maxlog2/δ+3∑_t=1^Tσ_t√(1+4log m_t/m_t(1+log2/δ))),
    	  Δ_max=4/α√(1/m_minlog2T/δ)



	κ=1 and Δ_t^∗=0 ∀ t∈[T] because θ̂_t=θ_t^∗ ∀ t∈[T].
	Applying Titu's lemma as in the proof of Proposition <ref> yields the values of ν and Δ' w.p. 1-2δ:
	
    ∑_t=1^Tσ_t_R(θ̂_t||ϕ̂)
    	   ≤3β/2∑_t=1^Tσ_t(θ_t^∗-θ_t'^2+θ_t'-ϕ'^2+ϕ'-ϕ̂^2)
       ≤3β∑_t=1^Tσ_t(θ_t^∗-θ_t'^2+_R(θ_t'||ϕ'))
       ≤4βσ_max/αlog1/δ+12β/α∑_t=1^Tσ_t√(1+4log m_t/m_t(1+log2/δ))+3β∑_t=1^Tσ_t_R(θ_t'||ϕ')

	Here in the last step we applied Lemma <ref> on Q_t=α/2θ_t^∗-θ_t'^2, which is 1-bounded by Lemma <ref>.
	The value of Δ_max follows directly by Lemma <ref> w.p. 1-2δ.


The following upper bound yields the FAL result in Theorem <ref>:

	In the Approx. case of Setting <ref>, if G_t=G,m_t=m ∀ t∈[T],γ=1+log T/log T, and ε=D1+log T/T then the FAL variant of Algorithm <ref> has TAR
	
    =𝒪(D/D^∗(log T/T+√(1/√(m)logTm/δ))+D^∗)G√(m)



	Substitute Proposition <ref> into Theorem <ref> and simplify.



	Let ℓ_1,…,ℓ_m:Θ↦[0,1] be a sequence of G_i-Lipschitz convex losses on Θ drawn i.i.d. from some distribution 𝒟 with risk _ℓ∼𝒟ℓ being α-QG w.r.t. · and define θ̂=1/mθ_1:m to be the the average iterate of running _η,ϕ^(R) or _η,ϕ^(R) on ℓ_1,…,ℓ_m for η>0,ϕ∈Θ, and R:Θ↦ℝ 1-strongly convex w.r.t. ·.
	Then w.p. 1-δ the closest minimum θ'∈Θ of _ℓ∼𝒟ℓ to θ̂ satisfies
	
    1/2θ'-θ̂^2≤_R(θ'||ϕ)+η^2 G^2m+η√(8mlog2/δ)/αη m

	where G^2=1/m∑_i=1^mG_i^2.


	By definition of θ̂ and θ' we have w.p. 1-δ that
	
    α/2θ̂-θ'^2
    	   ≤1/m_{ℓ_i}∼𝒟^m∑_i=1^mℓ_i(θ_i)-1/m_{ℓ_i}∼𝒟^m∑_i=1^mℓ_i(θ')    (apply α-QG and Jensen's inequality)
       ≤1/m∑_i=1^mℓ_i(θ_i)-1/m∑_i=1^mℓ_i(θ')+√(8/mlog2/δ)    (apply Prp. <ref> twice)
       ≤1/η_R(θ'||ϕ)+η G^2m/m+√(8/mlog2/δ)    (substitute the regret of FTRL/OMD)




	In Setting <ref>, if for each task t∈[T] the losses ℓ_t,1,…,ℓ_t,m_t and reference parameter θ_t' satisfy the α-QG condition as in Lemma <ref> and ε≥max_t24β G_t/α√(m_t), then for θ̂_t set according to the FLI-Batch algorithm we have w.p. 1-δ that κ=12β,ν=3β,
	
    Δ_t^∗=3β/α(1+4β G_t/αε)(2α_max/3α_tTlog3/δ+2√(1+4log m_t/m_t(1+log3/δ)))+12β G_t^2(D+ε)/α m_t ∀ t∈[T]

	
    Δ'=4βσ_max/αlog3/δ+12β/α∑_t=1^T(√(1+4log m_t/m_t(1+log3/δ))+(D^2+ε)G_t/2ε√(m_t))σ_t,
    	  Δ_max=1/α√(8/m_minlog6T/δ)



	Applying the triangle inequality, Jensen's inequality, Lemma <ref>, and Lemma <ref> yields w.p. 1-δ
	
    θ_t^∗-ϕ_t^2
    	   ≤3θ_t^∗-θ_t'^2+3θ_t'-θ̂_t^2+3θ̂_t-ϕ_t^2
       ≤3/α√(8/m_tlog2/δ)+6/αη_tm_t(_R(θ_t'||ϕ_t)+η_t^2G_t^2m_t+η_t√(8m_tlog2/δ))+6_R(θ̂_t||ϕ_t)
       ≤9/α√(8/m_tlog2/δ)+12β/αη_tm_t(θ_t'-θ_t^∗^2+θ_t^∗-ϕ_t^2)+6G_t^2(D+ε)/α m_t+6_R(θ̂_t||ϕ_t)
       ≤3/α(1+4β G_t/αε)√(8/m_tlog2/δ)+12β/αη_tm_tθ_t^∗-ϕ_t^2+6G_t^2(D+ε)/α m_t+6_R(θ̂_t||ϕ_t)

	where we have used the uniqueness of the reference parameter θ_t'.
	The above implies
	
    _R(θ_t^∗||ϕ_t)
    	≤β/2θ_t^∗-ϕ_t^2
    	≤3β/α(1+4β G_t/αε)√(8/m_tlog2/δ)+12β G^2(D+ε)/α m_t+12β_R(θ̂_t||ϕ_t)

	Here in the last step we used the fact that ε≥24β G_t/α√(m_min)η_t≥24β/α m_t ∀ t∈[T].
	Thus by Lemma <ref> w.p. 1-3δ
	
    ∑_t=1^Tα_t_R(θ_t^∗||ϕ_t)
    	   ≤3β/α(1+4β G_t/αε)(2α_max/3log3/δ+2∑_t=1^Tα_t√(1+4log m_t/m_t(1+log3/δ)))
           +12β G_t^2(D+ε)/α∑_t=1^Tα_t/m_t+12β∑_t=1^Tα_t_R(θ̂_t||ϕ_t)

	This yields the values of κ and Δ_t^∗ ∀ t∈[T].
	We next have by applying Titu's lemma as in the proof of Proposition <ref>
	
    ∑_t=1^Tσ_t_R(θ̂_t||ϕ̂)
    	   ≤3β∑_t=1^Tσ_t(θ̂_t-θ_t'^2+_R(θ_t'||ϕ'))
       ≤6β/α∑_t=1^Tσ_t_R(θ_t'||ϕ_t)/η_tm_t+σ_tη_tG^2+σ_t√(8/m_tlog2/δ)+3β∑_t=1^Tσ_t_R(θ_t'||ϕ'))
       ≤4βσ_max/αlog3/δ+12β/α∑_t=1^T(√(1+4log m_t/m_t(1+log3/δ))+(D^2+ε)G_t/2ε√(m_t))σ_t+3β∑_t=1^Tσ_t_R(θ_t'||ϕ')

	This yields the values of ν and Δ'.
	The value of Δ_max follows directly by Lemma <ref> w.p. 1-3δ.


The following final upper bound yields the FLI-Batch result in Theorem <ref>:

	In the Approx. case of Setting <ref>, if G_t=G,m_t=m ∀ t∈[T],γ=1+log T/log T, and ε=24β G/α√(m)+D1+log T/T then the FLI-Batch variant of Algorithm <ref> has TAR
	
    =𝒪(D/D^∗(log T/T+√(1/√(m)logTm/δ))+D^∗)G√(m)



	Substitute Proposition <ref> into Theorem <ref> and simplify.











































 §.§ 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.


	Let 𝒬 be a distribution over distributions 𝒫 over convex loss functions ℓ:Θ↦[0,1].
	A sequence of sequences of loss functions {ℓ_t,i}_t∈[T],i∈[m] is generated by drawing m loss functions i.i.d. from each in a sequence of distributions {𝒫_t}_t∈[T] themselves drawn i.i.d. from 𝒬.
	If such a sequence is given to an meta-learning algorithm with task-averaged regret bound  that has states {s_t}_t∈[T] at the beginning of each task t then we have w.p. 1-δ for any θ^∗∈Θ that
	
    _t∼𝒰[T]_𝒫∼𝒬_𝒫^m_ℓ∼𝒫ℓ(θ̅)≤_𝒫∼𝒬_ℓ∼𝒫ℓ(θ^∗)+/m+√(8/Tlog1/δ)

	where θ̅=1/mθ_1:m is generated by randomly sampling t∈𝒰[T], running the online algorithm with state s_t, and averaging the actions {θ_i}_i∈[m].
	
	
	


	
	Applying Proposition <ref>, linearity of expectations, the fact that the regret over 1-bounded loss functions is m-bounded, and Proposition <ref> yields
	
    _t∼𝒰[T]_𝒫∼𝒬_𝒫^m_ℓ∼𝒫ℓ(θ̅)
    	≤_𝒫∼𝒬(_ℓ∼𝒫ℓ(θ^∗)+_m(s_t)/m)
    	   ≤_𝒫∼𝒬_ℓ∼𝒫ℓ(θ^∗)+1/T∑_t=1^T_𝒫∼𝒬(_m(s_t)/m)
       =_𝒫∼𝒬_ℓ∼𝒫ℓ(θ^∗)+2/T∑_t=1^T_𝒫∼𝒬(_m(s_t)/2m+1/2)-1
       ≤_𝒫∼𝒬_ℓ∼𝒫ℓ(θ^∗)+/m+√(8/Tlog1/δ)







§ COMPUTING THE QUADRATIC GROWTH FACTOR


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

    α/2θ-θ^∗^2≤ f(θ)-f(θ^∗)

By Theorem 2 of <cit.>, in the convex case QG is equivalent, up to multiplicative constants, with the Polyak-Łojaciewicz (PL) inequality <cit.>.
Using the latter condition, <cit.> further show that functions of form f(Aθ) for f strongly-convex satisfy the PL inequality, and thus also QG, with constant α=Ω(σ_min(A)).
This provides data-dependent guarantees for a variety of practical problems, including least-squares and logistic regression.
<cit.> shows a similar result for expectations of such functions with the QG constant depending now on λ_min( A^TA);
in order to do so they assume the constraint set is a polytope, e.g. an ℓ_1 or ℓ_∞ ball.

For our results we require a stronger condition, namely that if L is a sum of m convex losses then L satisfies α 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 α studied by <cit.> and <cit.> is an underestimate;
for example, in the strongly-convex case, where A^TA is the identity, the lower bound will be 1 even though their sum is m-QG.

Here we derive an alternative approach for verifying α-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(θ) and f(θ^∗) over all θ located some fixed distance δ away from any minimizer θ^∗ of f over the ball:

    ε_δ=min     f(θ)-f(θ^∗)
    s.t.     θ-θ^∗_2^2≥δ^2
       θ_2≤ B

Then if f is α-QG, Equation <ref> implies that α_δ=2ε_δ/δ^2 should be a constant, or equivalently that ε_δ=Ω(δ^2).
While the above problem is non-convex due to the first constraint, note that 

    δ^2
    ≤θ-θ^∗_2^2
    =θ_2^2-2⟨θ,θ^∗⟩+θ^∗_2^2
    ≤ B^2-2⟨θ,θ^∗⟩+θ^∗_2^2

which is a linear constraint since θ^∗ is constant.
Therefore we have

    ε_δ≥min     f(θ)-f(θ^∗)
    s.t.     2⟨θ^∗,θ⟩≤ B^2-δ^2+θ^∗_2^2
       θ_2≤ B

which is a convex program amenable to standard solvers;
we employ the Frank-Wolfe method <cit.>.





§ EXPERIMENTAL DETAILS




 §.§ Constructing Mini-Wikipedia


We briefly describe the construction of Mini-Wiki.
Starting with the raw corpus of the Wiki3029 dataset of <cit.>, we select those Wikipedia pages whose titles correspond to lemmas in the WordNet corpus <cit.>.
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,…,32.
We have made MiniWiki available here: <https://github.com/mkhodak/FMRL/blob/master/data/miniwikipedia.tar.gz>.



 §.§ Complete Deep Learning Results


Below are plots for all evaluations on Omniglot and Mini-ImageNet.
As our algorithm generalizes the Reptile method of <cit.>, we use code they make available at <https://github.com/openai/supervised-reptile> and vary the parameters  and .








