Optimistic Meta-Gradients
Authors: Sebastian Flennerhag
Tom Zahavy
Brendan O'Donoghue
Hado van Hasselt
András György
Satinder Singh
Venue: NeurIPS 2023 poster (2023)
Keywords: meta-learning
online optimisation
convex optimisation
TL;DR: We study the connection between gradient-based (online) meta-learning and convex optimisation in the single task setting.

Abstract: We study the connection between gradient-based meta-learning and convex optimisation. We observe that gradient descent with momentum is a special case of meta-gradients, and building on recent results in optimisation, we prove convergence rates for meta learning in the single task setting. While a meta-learned update rule can yield faster convergence up to constant factor, it is not sufficient for acceleration. Instead, some form of optimism is required. We show that optimism in meta-learning can be captured through the recently proposed Bootstrapped Meta-Gradient (Flennerhag et. al., 2022) method, providing deeper insight into its underlying mechanics.

Optimistic Meta-Gradients
Sebastian Flennerhag
Tom Zahavy Google DeepMind
Brendan O' O'Donoghue Google DeepMind
Google Deep f Tlemerhag@googleecomm
Hado van Hasselt Google DeepMind
András György Google DeepMind
Satinder Singh Google DeepMind
Abstract
We study the connection between gradient-based meta-learning and convex op- timisation. We observe that gradient descent with momentum special case of meta-gradients, and building on recent results in optimisation, we prove con- vergence rates for meta-learning in the single task setting. While a meta-learned update rule can yield faster convergence up to constant factor, it is not sufficient for acceleration. Instead, some form of optimism is required. We show that opti- mism in meta-learning can be captured through the recently proposed Bootstrapped Meta-Gradien [9] method, providing deeper insight into its underlying mechanics.
Introduction
In meta-learning, learner is using param- eterised algorithm to adapt to given task. The parameters of the algorithm are then meta- learned by evaluating the learner's resulting per-
75
70
formance [25, 10, 2]. As such, meta-learning features complex interaction between the
Top-1 Test. Accuraccy (%)
learner and the meta-learner. The learner's
65
problem is to minimize the expected loss of a stochastic objective by adapting its parame- ters x R" The learner has an update rule at its disposal that generates new parameters J Tt-1 + p(z(-1, w;); we suppress data dependence to simplify notation. A simple ex- ample is when represents gradient descent with W. 77 its step size, that is (frt11,
60
SGD
Standard learning
Optimistic meta learning
-=;-(== [17, 26]; several works have ex- plored meta-learning other aspects of a gradient- based update rule [6, 21, 7, 30, 31, 9, 15, 22). yf need not be limited to gradient-basee based update, can represent some algorithm implemented within Neural Network [25, 11, 1, 29].
$8.0
0.5
1.0
1.5 Training Steps
2.0
2.5
3.0
1e6
Figure ImageNet. We compare training a 50- layer ResNet using SGD against variants that tune an element wise learning rate online using standard meta-learning or optimistic meta-learning, Shad- ing depicts 95% confidence intervals over 3 seeds.
The meta-learner's problem optimise the meta- parameters ш) to yield effective updates. In typical (gradient-based
meta- leeanle setting, it does so by treating 2; as a function of w. Let he, defined by heww)= = f + (0( w)), denote the learner's 's post-update performance as function of w. The learner and the meta-learner co-evolve according to
24 -t- p(z
We+ w. (h((w,) w. Dip(zt-1, w. V((z))
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where Dip( w) denotes the Jacobian of sp with respect to The nested structure between these two updates makes it challenging to analyse meta-learning. in particular depends heavily on the properties of the Jacobian. In practice, yp is highly complex and so Dep is almost always intractable. For this reason, the only theoretical results we are aware of specialise to the multi-task setting, where the learner must adapt to new task ft- Acceleration in this setup is driven by the tasks similarity. That is, if all tasks are sufficiently similar, meta-learned update can accelerate convergence these results do not yield acceleration in the absence of task distribution to the best of our knowledge.
[14]. However,
This paper provides an alternative view. We study the classical convex optimisation setting of approximating the minimiser min, f(x). We observe that setting the update rule equal to the gradient, i.c. f (z, w) + w f(x), recovers gradient descent. Similarly, we show in Section 4 that yo can be chosen to recover gradient descent with momentum. This offers another view of meta-learning as non-linear transformation of classical optimisation. An implication thereof is that task similarity is not necessary condition for improving the rate of convergence via weta-learning. While there ample empirical evidence that effect [30, 31, 9, 16], we are only aware of theoretical results in the special case of meta-learned step sizes [17, 26].
Given function f that is convex with Lipschitz smooth gradients, meta-learning improves the rate of convergence by multiplicative factor of À to O(/TT) via the smoothness of the update rule. To achieve accelerated convergence, O(1/T3,, some form of optimism is required. typically the form of prediction of the next gradient. We consider optimism with meta-leaming in the convex setting and prove accelerated rates of convergence, (A/TT)) Again, meta-learning affects these bounds by multiplicative factor. Our main contributions are as follows:
1. We show that meta-gradients contain gradient descent with momentum (Heavy Ball [23]; Section 4) and Nesterov Acceleration [20] as special cases (Section 5).
2. We show that gradient-based meta-learning can be understood as non-linear transformation
of an underlying optimisation method (Section 4).
3. We establish rates of convergence for meta-learning in the convex setting (Section 4).
4. We show that optimism can be expressed through the recently proposed Bootstrapped Meta- Gradient method [BMG; 9]. Our analysis provides a first proof of convergence for BMG and highlights the underlying mechanics that enable faster learning with BMG (Section 6).
2 Meta-Learning as Convex Optimisation
Problem definition. This section defines the problem studied in this paper and introduces our notation (see Appendix A, Table 1). Let f x + IR be a proper and convex function. The problem of interest is to approximate the global minimum minzex (zx). We assume a global minimiser exists and is unique, defined by
x" arg aex
araggmmn min f(x).
(I)
We assume that X C IR" is closed, convex and non-empty set. f is differentiable and has Lipschitz smooth gradients with respect to norm || I]. meaning that there exists L E (0, oo) such that [[V V
ft))l. < -| y/l for all æ, E X, where || ll. is the dual norm of -l We consider
the noiseless setting for simplicity; our results carry over to the stochastic setting by replacing the key online-to-ban batch bound used in our analysis by its stochastic counterpart [13].
Algorithm. Let [T] {1,2, 2....... T}. We are given weights {at)T_ each 0e > 0, and an initialisation (To, w1) E X x W. At each time t E IT), update rule yp : X x W + X' generates the update x4 = p( Wy), w.)), where W C R" is closed, convex, and non-empty. We discuss yp momentarily. The algorithm maintains the online average
Fia (1 10--pl 1 + Pette
31
O1
where Tt.t Ei 2 ag..s On = Σl= a. and Pt. = a1/a11. Our goal is to establish conditions under which { converges to the minimiser x². While this moving average is not always used in practical applications, it is required for accelerated rates in online-to-batel conversion [27, 3, 13).

---

Algorithm 1: Meta-learning in practice.
Algorithm 2: Meta-learning in the convex setting.
input: Weights {3x)
input: Weights (ou) (9:)211
input: Update rule yp
rule y
input: Initialiisaiinn (Io, w1)
input Initialisation (Tp, w1
for t = ..,,...,, T:
for = 1,,2...,,
1- + 11 w,w)
-( Wt)
h.()) = (x + prsp(re-1;)))
Jt = (1- / Te 1 + (ut/ana)zz
W++1 Wt- 3e Vl
91 Dip[te w V (
return ZT
w4+1 arg min E 05 (gss w)+ 23, |wo
return Br
Convergence depends on how meta-parameters w, are chosen. The meta-learner faces a sequence of
losses h4 : W R defined by the composition lx(w) = f((1 pe) p w)). As such, the meta-learner is facing an online optimization, which we model under Beiloo-Thhe-egularre Leader (FTRL; reviewed in Section 3): given wo. each wy is chosen according to
Ota (Vss(ws), w) + 1 23 /w||
W++11 arg min
wEW
Note that Eq. 3 subsumes the standard meta-gradient; if is the Euclidean norm, an interior solution yields W/+1 = W/ - a2 (y It is straightforward to extend Eq. 3 to account for meta-updates that use AdaGrad-lin like [5] acceleration by altering the norms (see [12]).
Update rule. is not possible to prove convergence outside of the convex setting, since y may reach a local minimum, where local changes to w do not yield better updates in æ, yet the x sequence not converging. Convexity means that each h, must be convex, which requires that yp is affine in w (but may vary non-linearly in r). We also assume that yo is smooth with respect to ||- in the sense that has bounded norm; for all E and w W we assume that there exists À E (0, oo) for which
[|D'(z, w) f( V
fz))1
Limitations. Our analysis makes relatively strict assumptions. Most meta-learning systems not affine in w. A notable case where our assumptions to hold is meta-learned step-sizes or precondition- ing matrices. For other update rules, our analysis holds up first-order Taylor approximation error. We carry out experiments in Section 7 to empirically verify our theoretical insights.
Preliminaries: Online Convex Optimisation
In this section, we present analytical tools from the optimisation literature that we build upon. In standard optimisation setting, there is update rule ;o; instead, the iterates 2, generated by a gradient-based algorithm, akin to Eq. 3. Our problem setting reduces to standard optimisation if yp defined by 9 (x,, w) w, in which case H, = Wt. In this paper, we use batch-to-online conversion as our analytical tool. This strategy treats the iterates I U2, as generated by an online learning algorithm, for which we can obtain a regret bound. This regret bound can then be turned into convergence rate, detailed momentarily.
Online Optimisation. In online convex optimisation [32], learner is given convex decision set UI and faces a sequence convex loss functions faufe)T= |T=1- At each time t E [T]. it must make prediction prior to observing atfi, after which it incurs loss fy and receives signal- either f, itself or a (sub-) jubd)ggradient of a (u,)) The learner's goal is to minimise regret, R(T) = -t=1 ΣT (ff(ze) - f((u)), against a comparator
4. An important property of a convex function is f(u)) f(u) < (Vf(u), - u). Hence, the regret is largest under linear losses: En (f) [u) < Ei= o (V)((,, - u). For this reason, it is sufficient to consider regret under linear loss functions. An algorithm has sublinear regret if limy- R(T)/T 0.
FTRL & AO-FTRI. The meta-update Eq. an instance of Follow- Neeow-The--ee The-ThhheReellee RheeRReularised-A Leader (FTRL) under linear losses. In Section 6, we show that BMG is instance of the Adaptive-Optimistic
3

---

FTRL (AO-FTRL) [24, 19, 13, 28]. In AO-FTRL, we have strongly convex regulariser || 11 AO- FTRL sets the first prediction in to minimise || 1| Given linear losses {g. } and learning rates [3.)2-1 each 3 > O, the algorithm proceeds according to
U4 arg min wEu
(e u) Eas (gss u) + 2
llul3)
(4)
where each Gr. is a "hint" that enables optimistic learning [24, 19]; setting 9: = 0 recovers the original FTRL algorithm. The goal of a hint is to predict the next loss vector 9r: if the predictions are accurate AO-FTRL can achieve lower regret than its non-optimistic counter-part, Since || . - is strongly convex, FTRL is well defined in the sense that the minimiser exists, unique, and finite [18]. The regret of FTRL and AO-FTRL against any comparator E U can be upper-bounded by
|ul1 2B
R(T) Σ anlge, u) S
Σ
a 11g 1
(5)
Hence, hints that predict 9r well can reduce the regret substantially. Without hints, FTRL can guarantee O(VT) regret (for non strongly convex loss functions). However, [4] show that under linear losses, hints are weakly positively correlatedddefinee as (gt, 3t) 2 el|gell² for some e > 0- then the regret guarantee improves Ollo T even for non strongly-conver loss functions. We believe optimism provides an exciting opportunity for novel forms of meta-learning, Finally, we note that these regret bounds (and hence analysis) be extended to stochastic optimisation [19, 12].
Online-to-batch conversion. The main idea behind online to batch conversion is that, for f convex, Jensen's inequality gives f(īT) - f(x*) S > (V f(x)), 22 ////arr That is, the sub- optimality gap of the average iterate ëT can be bounded by the regret in the sequence & ......, IT. Applying this bound naively yields O(1/T") rate of convergence. In recent work, [3] shows that one achieve tighter bounds by instead querying the gradient at the average iterate, f(āT) - f(x*) ) S EL a f())), It z²)/aur faurr. A tighter bound means faster rate of convergence. Recently, [13] tightened the analysis further and proved that the sub-optimality gap can be bounded by
f f(x*)= s
(6)
RC (T)
at 2T.
011-1 2T.
- V(()))))
01T
were define (T) = ELe ai (V (V+())), x²) as the regret of the sequence (..) against the comparator x². With this machinery in place, we now turn to deriving our main results.
4 Meta-Gradients without Optimism
The main difference between classical optimisation and meta-learning is the introduction of the update rule yp. To see how this acts on optimisation, consider two special cases. the update rule just return the gradient, & = f, Eq. 3 reduces to gradient descent (with averaging). This inductive bias fixed and does not change with experience, so acceleration is not possible: the rate of convergence is O(L/VT) [28]. The other extreme is an update rule that only depends on the meta-parameterss pll w) w. Here, the meta-learner has ultimate control and selects the next update without constraints. The only relevant inductive bias contained w. To see how this inductive bias is formed, suppose|
|l2 so that Eq. yields W1+1 wt ff (assuming interior solution). Combining this with the moving average in Eq. 2, we may write the learner's 's iterates as
= |||||||]]
H = It-1 + Pe (ft-1 TT-2) 3 V f(E--1)
1-Pt-1 and 3, = aepp3. Setting 3 1/(2L) and each a; t yields ý: f-2 where each Pe = Pt PC-1
[+1 and 3, = t/(4(t+1)L). which recovers Polyak's 's canonical Heavy-Ball method [23]. Hence, gradient descent with momentum is special case of meta- meta-learning under the update rule yp (x., w) + w. Because Heavy Ball carries momentum from past updates, it can encode a model the learning dynamics that leads to faster convergence, on the order O(1/T). The implication of this is that the dynamics of meta-learning are fundamentally momentum- based and thus learns an inductive bias in the same cumulative manner. This similarity carries in our theoretical analysis, which we turn to next.

---

The central challenge in applying the bound in Eq. 6 to Algorithm 2 is that the iterates are generated under the update rule yp. Hence, we cannot apply standard regret bounds directly. Instead, observe that
T
T
(T)
a 2 21 x²) --==
at av( (( ws) (90))-a -x")
(
an au (Vf(())) p(8-1,, x²).
regret under losses (())).(((( (V())
difference comparator capacity
The first term in the final inequality can be understood as the regret under convex losses (-) ae (V..) (( -)). Since yp is affine, is convex and thus this regret can be upper-bounded by linearising the losses. The linearisation reads (D, (,)) " ("*)), .), which identical the linear losses (W+)(w:),)) faced by the meta-learner in Eq. 3. In other words, the regret component can be upper-bounded by the of the meta-learner,
T
RT (T)
= Σ ar (Ve((w)), w²)
aa (V ux) (0 w0 w²))
The regret of the learner is therefore upper bounded by
+ o ((a x*). t=1
The last term captures the difference in comparator capacity and more specifically the amount of regret they can inflict. If the comparator w* has more power than that of x², can accumulate lower total loss, in which case this term will be negative, allowing comparator x² is non-adaptive. must make one choice and suffer the average loss. contrast, the comparator w" becomes adaptive under the update rule; it can only choose one w", but on each round it plays - w*). If yp is sufficiently flexible, this gives the comparator w" more power than x², and hence it can force the meta-learner to suffer greater regret. When this is the case, say that regret retained when moving from x" to w". As long as yp is not degenerate, this is typically easy to satisfy by making W sufficiently large.
to discard it. Intuitively, the
Definition 1. Given f. {a and {x an update rule & X X' preserves regret if there exists comparator w E W that satisfies
Car(p(5r11.0)) w), V((A))
Σ o ()())))
(8)
If such w exists, let w denote the comparator with smallest norm ||/]]. Lemma 1. Given f. {arTT= and {xt {TteTmmi if 4p preserves regret, then
R (T(T)=
Σ
on (V) x²) on (V)) w/) (p(Ft-1, R (T).
Appendix D. From Eq. 8, is clear that for o to retain regret, must admit a parameterisation that correlates negatively with the gradient. In other words, must be able to behave as a gradient descent algorithm. However, this must not hold on every step. only sufficiently often. For instance, (p(x,-) -) affine can be made to satisfy this condition if X and W are chosen appropriately.
Proof:
Theorem 1. Let 4p preserve regret and satisfy the assumptions in Section 2. Then
X
f(Er) - f(x²)= <
[Vf(2111
01.TT
B
2
04
V ff("')1
01
(V -v((m)1
2T.
21.
xf is a global minimiser of f, setting an 1 and == xt yields f(āT) f(x²)
Ar. drddia((W)
T
5

---

Algorithm 3: BMG in practice.
Algorithm 4: Convex optimistic meta-le.
input: Weights (3()
input:
Imput:Weisee Weights {ax) (3))21
input: Update rule yp, divergence B
: rule yp
input: Taaget oracle
input :Hints {ăx J
input:Initiall :nittiaiisation (zo, w1)
input: :nitialiisatinn (ão, wi)
for 1- 1=,,
for ( -1, T:
Jt = 1 1, wt) Query from target oracle
2t = ((r,-1, (,)
(1 0z. /1/an,1 F (at/an:)
(.) = 8 ( + (xx(11)))
9: = Dp(01-11 W/ ) (
W++11 = wy 8. (w:)
Us = 0++1 + E 0s9s
return TT
W/++1 = arg min ew (U, w) + 2 |
return öT
Proof:
Appendix D. Compared to Heavy Ball, meta-learning introduces a constant À that captures the smoothness of the update rule. Hence, while meta-learning does not achieve better scaling in T' through so, can improve upon classical optimisation by a constant factor if À <
That meta-learning can improve upon momentum is borne out experimentally. We consider the problem of minimizing ill-conditioned convex quadratic and compare standard momentum to a version with meta-learned step-size, i.e. (x; w) + w @ (x(),, where @ is the Hadamard product. We find that introducing non-linearity yp leads sizeable improvement in the rate of convergence. See Section 7.1 for further details.
Meta-Gradients with Optimism
is well known that minimizing a smooth convex function admits convergence rates of OL)/T²). Our analysis of meta-learning does not achieve these rates. Previous work indicate that we should not expect it to either; to achieve the theoretical lower-limit of O(1/T²), some form of optimism (c.f. Section 3) is required. A typical form of optimism is to predict the next gradient. This is how Nesterov Acceleration operates [20], and is the reason for its O convergence guarantee.
From our perspective, meta-learning is a non-linear transformation of the iterate x. Hence, we should expect optimism to play similarly crucial role. Formally, optimism comes in the form of hint functions {ūe )T= each 9t E TR"",, that are revealed to the meta-learner prior to selecting Wz+1- These hints give rise Optimistic Meta-Learning (OML) via meta-updates
04-19t+1 + Σ as (V)((w))) w) + 233 |
We++1 = arg min WEW
the hints are accurate, meta-learning with optimism can achieve an accelerated rate of O(²TT)) where Ā is a constant that characterises the smoothness of sp, akin to A. Again, we find that meta- learning behaves as non-linear transformation of classical optimism and its rate of convergence is governed by the geometry it induces.
For complete description, see Algorithm 4. These updates do not correspond to the typical meta- update in Algorithm 1; however, we show momentarily that they can be interpreted as the targets in the BMG method, summarised in Algorithm 3. Before turning BMG, establish that optimistic meta-learning in the convex setting does indeed yield acceleration.
Theorem 2. Let up preserve regret and assume Algorithm 4 satisfy the assumptions in Section 2. Then
||
T
- - fxx)== <
-
01.T
BT
2
04
fZ.,))
v {2
01 01=-1 11 - -
2L
2L
Proof; Appendix D. From Theorem 2, it is clear that if 9: is good predictor of Dip(0,-1, VV then the positive term in the summation can be cancelled by the nega- tive term. In classical optimisation setting, Dip In. and hence it is easy to that simply

---

choosing Jt to be the previous gradient is sufficient to achieve the cancellation [13]. Indeed, this choice gives us Nesterov's 's Accelerated rate [28]. The upshot of this is that we can specialise Algo- rithm 4 to capture Nesterov's Accelerated method by choosing to Heavy Ball-and setting the hints to ÿt -1) Hence, while the standard meta-update without optimism contains Heavy Ball as special case, the optimistic meta-update contains Nesterov Acceleration as a special case.
(ær, w) > w--as in the reduction
In the meta-lcarning setting, D is not an identity matrix, and hence the best targets for meta-learning different. Naively choosing 9t ( (,,, ( ((t=1) would lead similar cancellation, but this is not allowed. At iteration t, we have not computed We when 9r is chosen, and hence D wi) is not available. The nearest term that accessible is ( wt-1).
Corollary 1. Let each De+1 = De((Fe-1, ". (Tt)) Assume that satisfies
||Du(a'' (o)(d'.w)'v (fx))( Dipl",, v')"Vf(=')II S x(IV(((a) vf(=))l
for all x², ,/, X and w, w/ W. some Ā > 0. If each on and Be 2tA ((Tr) - f(x²) S 4ALdiam((W
then
T²-1
Proof:
Appendix D.
These predictions hold empirically in a non-convex setting. We train a 50-layer ResNet using either SGD with fixed learning rate, or update rule that adapts per-parameter learning online, o (I, - to @ (xx).. We compare the standard meta-learning approach without optimism to optimistic meta-learning. Figure shows that optimism is critical for meta-learning achieve accelcration, as predicted by theory (experiment details in Appendix C).
6 Bootstrapped Meta-Gradients as a form of Optimism
Given Theorem 2, it is of interest to study practical ways of implementing optimism meta-learning. We study a recently proposed variant of meta-gradients, Bootstrapped GeeaiGGrsssnts (BMG) [8]. Informally, instead of directly minimising the loss f, the meta-objective in BMG the distance between the meta-learner's 'ssei output I; and a desired target 2t. The target is computed by unrolling the meta-learner for a further number of steps, thus implicitly embodying form of optimism, before gradient step is taken: 2 I₁ + (0 we) ff + (p(;,, wy)). This encodes optimism via because encourages the meta-learner to build up momentum (i.e. to accumulate past updates). To see this formally,
turn to AO-FTRL. First, provide more general definition of BMG. Let μ : X + R be a convex distance generating function and define the Bregman Divergence by
B" R x R
(x) = p(x) u(2) - x=
Given initial condition (zo, w1). the BMG updates proceed according to
Tz - (0
W++1 = Wt - Be V.
Wt - -B, -eDe (Vμ(æ;) - V)((z)),
(10)
where d, R" + is defined by d((w)- = B (xx-1 + (0) we each 2, E R" referred to target. See Algorithm 3 for algorithmic summary. To show how this relates to AO-FTRL, let fa f- In this case, the BMG update reads wz+1 = W/ -3, D (V/(((())) - (x())). We obtain these updates via our convex framework (i.e. Algorithm 4) by setting Ht+1 (2)). In this case, we have that (Corollary 3, Appendix E) AO-FTRL reduces to
Be+1 W1+1 B, w, 3.Dip Wx) (a (a411 aj Vf(z)) +
where & -.aaDD((E wi " denotes an error correction term that removes the previous target. This error correction term is theoretically important for stability [13], as the accu- mulation of hints can otherwise dominate the true signal. That the original BMG does not feature this error term may explain the instabilities the authors observed when setting too aggressive targets [8]. Since Algorithm 3 does not average its iterates-whil Algorithm 4 does-we see that these updates (ignoring {.) are identical up to scalar coefficients (that can be controlled for by scaling each & and each I accordingly). Our next results present formulas for constructing targets in BMG hints in AO-FTRL so that the two commute.
7

---

Theorem 3. Targets in Algorithm 3 and hints in algorithm commute in the following sense. BMG -O--FTRL Let BMG targets {2r)==1 by given. sequence of hints {g]t= can constructed recursively by
0+4419++1 = Dep(ā=-1, w (V - Vu(zz) - aa
aigt.
(II)
so that interior updates for Algorithm 4 are given by
Bt Br (Vp(z)) - vu(ūt))
Wx+1
B--1
A0-FTRL - BMG. Conversely, assume a sequence (ūr are given, each ÿt E CR.. If strictlly convex, sequence of BMG targets {ze)i-1 can be constructed recursively by
24 Vp (Vu(z)) - (a4+10++1 avVi(x)))
t [T].
that BMG updates in Eq. 10 given by
W+++1 wt 3e (0c+10++1 + uD) 3:))
where each 9 is given by
0 0++10+11 10t T + 0nğr.
Proof: see Appendix E. As an immediate consequence of this, we can apply our optimistic meta- gradient analysis (Theorem 2) to BMG obtain rate of convergence. This is captured in the following corollary.
Let each 91+1 = Di we) T Uc+1, for some yet1 E R". each D041 is a better predictor of the next gradient than fā in the sense that
Corollary 2.
[|De(ft-2,us w.-1) - Di(( w f(z)ll E f(l) V ff
then Algorithm guarantees convergence at a rate ()/TT²) In other words, for certain choices of targets, BMG yields accelerated rates of convergence.
7 Experiments
In this section, we detail experiments borne out to test our theoretical predictions. Section 7.1 tests predictions about meta- geta-ggaddeens without optimism, by comparing meta-learned variants of standard optimisers to their non-meta-learedt counterparts. Section 7.2 test predictions about optmistic meta-gradients, by comparding an optimistic meta-gradient approach gradient descent.
7.1 Convex Quadratic Experiments
Loss function. We consider the problem of minimising a convex quadratic loss functions R² + R of the form f(x) x 'r for some Q that is sampled such that it is ill-conditioned (see Appendix B for details).
Protocol. Given that the solution is always (0, 0), this experiment revolves around understanding how different algorithms deal with eurvature. Given symmetry in the solution and ill-conditioning, we fix the initialisation to zg = (4, 4) and run each algorithm for 100 iterations. For each Q and each algorithm, we sweep over the learning rate, decay rate, and the initialization w (see Table for values) and report results for the best performing hyper parameters.
Results. We report the learning curves for the best parpmmtt choice for randomly sampled problems in the top row of Figure 2 (columms correspond to different Q). We also study the sensitivity of each algorithm to the learning rate in the bottom row Figure 2. For each learning rate, we report the cumulative loss during training. While baselines relatively insensitive hyper-parameter choice, meta-learned improve for certain choices, but are never worse than baselines.
7.2 Imagenet Experiments
Protocol. We train a 50-layer ResNet following a standard protocol (Appendix C) with SGD as the baseline optimiser. We compare SGD to variant that meta-learns an element learning rate online, i.e. (xr, w) + w @ (xr).. We sweep over the learning rate (for SGD) or meta-learning rate and report results for the best
over three independent runs.

---

Mita: Mumanaur
Adadired Hila
20mh
45
60
60
183
0
22
83
60
40
192
23
85
60
F0
182
60
100
60
150
8
(retrgne
quadratic loss functions with ill-conditioning and compare gradient descent with momentum and AdaGrad to meta-learning variants. Meta-Momentum uses yp (I,, w) + w @ (z) while Meta-AdaGrad uses yp (ar, w) ~ V (x)//w, where division element-wise. Top: loss per iteration for randomly sampled loss functions. Bottom: cumulative
Figure 2: Convex Quadratic. We generate
loss (regret) at the end of learning a function of learning rate; details in Appendix B.
Standard meta-learning. In the standard meta-learning setting, we apply the update rule once before differentiating w.r.t. the meta-parameters. That is, the meta-update takes the form W = w (Vh((wa) where he = f(, + wy O fxx))) Because the update rule is linear in we can compute meta-gradient analytically: (hy(wr) = V ww](2= (ar, w)) = Dip(x, compute the meta-updates in Algorithm manually
= Vf(x) @
V fa'",, where x' + (z, w). Hence, as w = max W/ - f (z ( O. where we introduce the max operator on an element- wise basis to avoid negative learning rates. Empirically, this was important stabilize training.
Optimistic meta-learning. For optimistic meta-learning, we proceed much in the same way, but in- clude gradient prediction Ø1+1- For our prediction, we use the previous gradient, V (f as our prediction. This yields meta-updates of the form W++1 max {w, - (f O
(Vf(xt-1)+ ff(())) f((z)) ff(2,),0.}
Results. We report Top-1 accuracy the held-out test set as function of training steps in Figure 1. Tuning the learning rate does not yield any statistically significant improvements under standard meta-learning. However, with optimistic meta-learning, we obtain significant acceleration well as improved final performance, increasing the mean final top-1 accuracy from 72% to 75%.
8 Conclusion
This paper explores connection between convex optimisation and meta-learning. We construct an algorithm for convex optimisation that aligns closely as possible with how meta-learning is done in practice. Meta-learning introduces a transformation and we study the effect this transformation has on the rate of convergence. We find that, while a meta-learned update rule cannot generate better dependence on the horizon T, it can improve upon classical optimisation up to a constant factor.
An implication of our analysis is that for meta- meta-learning to achieve acceleration, it is important to introduce some form of optimism. From classical optimisation point of view, such optimism arises naturally by providing the meta-learner with hints. If hints predictive of the learning dynamics these can lead to significant acceleration. We show that the recently proposed BMG method provides natural avenue incorporate optimism practical application of meta-learning, Because targets in BMG and hints in optimistic online learning commute, our results provide first rigorous proof of convergence for BMG, while providing a general condition under which optimism in BMG yields accelerated learning.

---

References
[1] M. Andrychowicz, M. Denil, Gómez, M. W. Hoffman, D. Pfau, T. Schaul, and N. de Freitas. Learning to Learn by Gradient Descent by Gradient Descent. In Advances in Neural Information Processing Systems, 2016.
[2] Y. Bengio, S. Bengio, and Cloutier. Learning a Synaptic Learning Rule. Université de Montréal, Département d' I'informatique de recherche opérationnelle, 1991.
[3] A. Cutkosky, Anytime Soalne-tt-Batchh Optimism and Acceleration. In International Confer- ence on Machine Learning. 2019.
[4] O. Dekel, A. Flajolet, N. Haghtalab, and P. Jaillet. Online learning with hint. In Advances in Neural Information Processing Systems, 2017.
[5] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12111)2121-2159, 201
[6] C. Finn, P. Abbeel, and S. Levine, Model-Agnostee Meta-Learning for Fast Adaptation of Deep Networks. In International Conference on Machine Learning. 2017.
[7] S. Flennerhag, P. G. Moreno, N. D. Lawrence, and A. Damianou. Transferring Knowledge across Learning Processes. In International Conference Learning Representations, 2019.
[8] Flennerhag, Y. Schroecker, T. Zahavy, van Hasselt, D. Silver, and S. Singh. Bootstrapped Meta-Leaming, arXiv preprint 1XXx:22099.0504, 2021.
[9] Flennerhag, Y. Schroecker, T. Zahavy, H. van Hasselt, D. Silver, and S. Singh. Bootstrapped Meta-Leaming, In International Conference on Learning Representations, 2022.
[10] G. E. Hinton and D. C. Plaut. Using Fast Weights Deblur Old Memories. In Cognitive Science Society, 1987.
[11] S. Hochreiter, A. S. Younger, and P. R. Conwell. Learning To Learn Using Gradient Descent. International Conference on Artificial Neural Networks, 2001.
[12] P. Joulani, A. György, and C. Szepesvári. A modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, and variational bounds. Journal of Machine Learning Research, 1:40, 2017.
[13] P. Joulani, A. Raj, A. Gyorgy, and C. Szepesvári. A Simpler Approach Accelerated Optimiza- tion: Iterative Averaging Meets Optimism. In International Conference on Machine Learning, 2020.
[14] M. Khodak, M.-F. Balcan, and S. Talwalkar. Adaptive Gradient- Based Meta-Learning Methods. In Advances in Neural Information Processing Systems, 2019.
[15] L. Kirsch, S. van Steenkiste, and Schmidhuber. Improving Generalization in Meta Reinforce- ment Learning Using Learned Objectives. arXiv preprint arXiv:1910.04090 2019.
[16] J. Luketina, S. Flennerhag, Y. Schroecker, D. Abel, T. Zahavy, and S. Singh. Meta-gradient in
non-stationary environments. In ICLR Workshop on Agent Learning Open- Bhend-nde,,ess, 2022.
[17] A. R. Mahmood, R. S. Sutton, T. Degris, and M. Pilarski. Tuning-Free Step-Size Adaptation. ICASSP, 2012.
[18] H. B. McMahan. A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 18(1)3117-3166, 2017.
[19] M. Mohri and S. Yang. Accelerating Online Convex Optimization via Adaptive Prediction, In International Conference Artificial Intelligence and Statistics, 2016.
[20] Y. E. Nesterov. A method for solving the convex programming problem with convergence rate (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
10

---

[21] A. Nichol, J. Achiam, and J. Schulman. On First-Order Meta-Learning Algorithms. arXiv preprint ArXiv: 02999, 2018.
[22] Oh, M. Hessel, W. M. Czarnecki, Z. Xu, H. van Hasselt, S. Singh, and D. Silver. Discovering Reinforcement Learning Algorithms. In Advances in Neural Information Processing Systems, volume 33, 2020.
[23] B. T. Polyak. Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
[24] S. Rakhlin and K. Sridharan. Optimization, Learning, and Games with Predictable Sequences. In Advances in Neural Information Processing Systems, 2013.
[25] J. Schmidhuber. Evolutionary Principles in Relf-Referential Learning. PhD thesis, Technische Universität München, 1987.
[26] van Erven and W. M. Koolen. MetaGrad: Multiple Learning Rates in Online Learning. In Advances in Neural Information Processing Systems, 2016.
[27] J.-K. Wang and J. Abemnethy. Acceleration through Optimistic No- No-Regret Dynamics. arXiv preprint Xrviv: 1005, 2018.
[28] J.-K. Wang. J. Abernethy, and K. Y. Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. arXiv preprint arXiv:2111. 1309, 2021.
[29] X. Wang. Z. Kurth-Nelson, D. Tirumala, H. Soyer, Z. Leibo, R. Munos, C. Blundell, D. Kumaran, and M. Botvinick. Learning to Reinforcement Learn. In Annual Meeting of the Cognitive Science Society, 2016.
[30] Z. Xu, H. van Hasselt, and D. Silver. Meta-Gradient Reinforcement Learning. In Advances in Neural Information Processing Systems, 2018.
[31] T. Zahavy, Z. Xu, V. Veeriah, M. Hessel, Oh, H. P. van Hasselt, D. Silver, and S. Singh. A Self-Tuning Actor-Critic Algorithm. In Advances in Neural Information Processing Systems, volume 33, 2020.
[32] M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In International Conference on Machine Learning, 2003.


Reviews:
[{"review_id": "p3GeT617Mb", "reviewer": "Reviewer_HQ88", "summary": "The submission studies connections between recent advances in convex optimisation and heuristic meta-learning update rules. The provided framework contains standard methods such as heavy ball and Nesterov's momentum as special cases, while also containing rules that correspond to online meta-learning. Bootstrapped meta-gradients are also formalised within this framework. Some of the theoretical results are corroborated by empirical investigations.", "questions": "N/A", "limitations": "There is no substantial discussion of the limitations of the work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The submission is well-written and interesting. I can see myself referring back to this paper in future when developing new meta-learning or bi-level optimisation methods.\n* Framework provides a useful tool for conceptualising and analysing meta-learning algorithms, as well as comparing them with existing (or novel) convex optimisation approaches.\n* The analysis shows how one can obtain optimal $O(1/T^2)$ rates of convergence by using optimism. E.g., by predicting that the current gradient will be similar to the previous gradient.\n* Experiments are provided that empirically corroborate the predictions of the theoretical analysis. In particular, the meta-learning variants of momentum and adagrad converge substantially faster than the conventional approaches.", "weaknesses": "* The analysis is limited to the convex case, which is understandable. However, it would be interesting to at least empirically investigate the non-convex case as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, we are glad you found the paper interesting and potentially helpful in your future work! We agree that studying the non-convex case empirically is an exciting area for future research. We take some initial steps in this direction with our ResNet experiment, in which the learner’s problem is non-convex (while the meta-learner’s problem is still convex). We hope that our theoretical insights can help practitioners develop new meta-learning algorithms that perform better at scale in non-convex settings."}, {"review_id": "MVMrG3EnLC", "reviewer": "Reviewer_JxCU", "summary": "This work discovers the connection between gradient-based meta-learning and convex optimization of the meta parameters. From there, the authors observe that common gradient descent and its variants with momentum are special cases. To match the conventional $O(1 / T^2)$ convergence rate, the authors propose the optimistic version.", "questions": "The figure 1 shows the result of top-1 accuracy of sgd and standard meta learning on resnet50 on imagenet. But to my knowledge SGD can achieve >75% top-1 accuracy on imagenet, can the author elaborate more on what codebase they use and the details of experimental setting for that experiment (e.g., how do you tune learning rate, what is the scheduling etc)?", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The observation that common accelerated methods can be viewed as meta-learning is interesting. The online convex optimization view presents a new perspective for showing the convergence of the accelerated methods, which could be itself interesting.\n2. The proposed optimistic gradient-based meta-learning method is simple, but shows performance gain over vanilla baseline methods.", "weaknesses": "The major weakness of the analysis comes from the restrictive form of the meta-learner. This makes the analysis not applicable to all neural network based learn-to-optimize methods, while the meta-learning methods applied on learning rate or pre-conditioning matrix are well studied already in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, we are glad you found the connections we made interesting. We fully agree that the restrictions on the meta-learner are limiting. Unfortunately, this is an inherent limitation we face when using convex analysis, since neural networks are not convex. Hence, a non-convex interaction between the meta-learner and the learner cannot be analyzed exactly in this way. With that said, we would like to point out that our theoretical predictions do apply to any meta-learner, up to first order Taylor series error. For small learning rates, our predictions are accurate, and our ResNet experiment demonstrates that our theory has practical use.\n\nThank you for raising your question on Figure 1. We use the Haiku example launch script, which is available on github. We are not allowed to provide external links in the rebuttal, but please see Appendix C in the supplementary materials for a url link. We only modified this script by changing the optimizer. The baseline we compare against is SGD with a fixed learning rate (a non-adaptive baseline). We tuned the learning via a sweep over the range $[1e-4, 3e-4, 1e-3, 3e-3, 1e-2, 3e-2, 1e-1, 3e-1]$ on the validation set. We report scores for the best performing one. We would like to stress that the point of this experiment is not to propose a new meta-learner that beats state of the art, but to empirically validate that our theoretical predictions (i.e. that an adaptive meta-learner can yield accelerated learning against a non-adaptive learner) hold in the deep learning setting."}, {"review_id": "DkhdKzp7ee", "reviewer": "Reviewer_nSnp", "summary": "This paper shed an interesting perspective on meta-learning by studying the connection between gradient-based meta-learning and convex optimisation in the single task setting. It shows that meta-gradients contain gradient descent with momentum and Nesterov Acceleration as special cases. Furthermore, gradient-based meta-learning can be understood as a non-linear transformation of an underlying optimisation method. The authors establish the rates of convergence for meta-gradients in convex settings. For meta-learning to achieve acceleration of convergence, some form of optimization is needed. Specifically, it provides the first rigorous proof of BMG with acceleration rate of convergence, and highlights the underlying mechanics that enable faster learning with BMG.  \n", "questions": "Curious to know what is the computational cost of Optimistic meta-learning compared to SGD in the ImageNet experiment. \n", "limitations": "1. There is no code provided to reproduce the results.\n2. The authors do not describe limitations of their work. \n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provides us a novel view on meta-learning by studying the connection between gradient-based meta-learning and convex optimisation. It reveals that gradient descent with momentum and Nesterov Acceleration are special cases of gradient-based meta-learning with different update rules. This paper is of high technical quality. Based on the new understanding for meta-learning as a non-linear transformation of an underlying optimisation method, it establishes theoretical analysis and proof of the convergence rates of meta-gradients in convex settings. The theoretical analysis has insightful implications that we are able to further accelerate the rate of convergence with some form of optimization. As a result, the recently proposed BMG method is proven to achieve an accelerating convergence rate. These results are important and significant, providing us with new deep understanding about gradient-based meta-learning, and theoretical guidance to design fast meta-learning algorithms with update rules. Last, the paper is well organized and clearly written.\n", "weaknesses": "This is a theory paper, it could be more impactful if the authors may add more experiment results for large scale problems either in convex optimization or deep learning settings besides ImageNet.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review; we are delighted that you liked the paper and found our results important and significant. In this paper, we focused on the theoretical aspect, but we agree that further empirical investigations is an exciting area for future research. We hope that the theoretical insights we have developed can help practitioners develop novel methods that perform better in the large scale regime.\n\nOn computational cost, the FLOPs for an SGD update is 2N, N being the number of parameters in the network. The Optimistic Meta-Learning optimizer in the ImageNet experiment (Section 7.2) requires 7N FLOPs. As a reference, an optimizer like Adam requires 18N FLOPs per update."}, {"review_id": "QOumtD5n3s", "reviewer": "Reviewer_fhwU", "summary": "This paper studies a connection between optimization and meta-learning. For the case of a single task, it shows an equivalence between GD with momentum and GBML, and another equivalence between GD with Nesterov acceleration and the recent Bootstrapped Meta-Gradient algorithm. Theoretical analyses are done for these algorithm, showing that GBML speeds up convergence by a constant factor but is not able to improve on the $O(1/T)$ rate, while BMG is able to improve the rate to $O(1/T^2)$. Experiments are done on quadratic minimization and ImageNet image classification that confirm the theory.", "questions": "Is it fair to search over the range of hyperparameters in the experiments in Section 7.1? Usually when this is done the final results are provided for a held-out test set (a new quadratic function in this case), but this does not seem to be the case here.", "limitations": "The authors do not have a broader impact section, and I agree since this work discusses optimization methods. However, they do not discuss the limitations/weaknesses of their work, which I think should be added to the final draft.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The mathematical argument in the paper is very clearly presented, e.g. the authors roughly outline proof techniques.\n2. Overall the paper appears to be sound, although I did not check the math. Experiments were done on both \"toy\" examples and a more realistic ImageNet problem.\n3. As far as I know, the connection between BMG and GD with Nesterov acceleration is novel.", "weaknesses": "In my opinion, the major weakness of the paper is the fact that it only considers the single task setting. However, one of the major motivations behind meta-learning is that information may be shared between tasks in order to improve convergence speeds for all tasks, and the multi-task setting is arguably more popular in the literature. It would greatly strengthen the work to consider the theory for a multi-task setting, although I understand that it might be more appropriate for future work.\n\nMinor:\n1. The objective function is convex is a fairly strong assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, we are glad you found the paper well presented with novel insights. We appreciate that multi-task meta-learning is a common problem setting and one that we do not consider in this paper. While multi-task meta-learning has been fairly extensively analyzed, we are not aware of any theoretical work in the single-task setting (except some papers in the online optimization community on meta-learned learning rates). The goal of this paper is to address this gap, hence the focus on single task online meta-learning. \n\nNotably, as the reviewer points out, rates of acceleration in the multi-task setting rely on transfer across tasks. Reading these papers, one may be tempted to conclude that meta-learning can only achieve acceleration by transferring knowledge across tasks. We believe this to be a commonly held belief in the community.  Significantly, our paper proves the *opposite* to be true: meta-learning can achieve acceleration *without* the need for multiple tasks! We believe this to be a fundamental insight that contravenes current mainstream thinking within the meta-learning community.\n\nFundamentally, we show that meta-learning is the same as standard optimization, just non-linearly transformed. For us, this was an eye-opening discovery that has changed how we think about meta-learning. We hope that this paper can help others in the field to similarly deepen their understanding of meta-learning. \n\nOn the empirical results in Section 7.1: this is a fair question. Proofs of accelerated convergence always depend on an optimal choice of learning rates. Hence, as our purpose is to verify theoretical predictions, the relevant empirical study is to compare algorithms under optimal learning rates. This can be seen as a comparison of ‘best case performance’; as long as all algorithms are tuned similarly, this is still a fair comparison.\n\nOn limitations; the main limitation of our work is the assumption of convexity. We discuss this briefly in Section 2, but will expand this discussion in an updated version of the manuscript. If the reviewer would like to see other limitations discussed, please do let us know."}]

Author rebuttal:

Meta-review: This work discovers the connection between gradient-based meta-learning and convex optimization of the meta parameters. From there, the authors observe that common gradient descent and its variants with momentum are special cases. To match the canonical optimal convergence rate, the authors propose an optimistic version to achieve it.

All reviewers believe this paper makes valid contributions. The AC agrees and recommends acceptance.
Decision: Accept (poster)