# Optimistic Meta-Gradients

Sebastian Flennerhag
DeepMind
<EMAIL_ADDRESS>
&Tom Zahavy
DeepMind

&Brendan O’Donoghue
DeepMind

&Hado van Hasselt
DeepMind
&András György
DeepMind
&Satinder Singh
DeepMind

###### 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 Bootstrapped
Meta-Gradients (Flennerhag et al., 2022), providing deeper insight into its
underlying mechanics.

##  1 Introduction

Figure 1: 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. Shading depicts 95% confidence intervals
over 3 seeds.

In meta-learning, a learner is using a parameterised algorithm to adapt to a
given task. The parameters of the algorithm are then meta-learned by
evaluating the learner’s resulting performance (Schmidhuber, 1987; Hinton and
Plaut, 1987; Bengio et al., 1991). This paradigm has garnered wide empirical
success (Hospedales et al., 2020). For instance, it has been used to meta-
learn how to explore in reinforcement learning (RL) (Xu et al., 2018a; Alet et
al., 2020), online hyper-parameter tuning of non-convex loss functions
(Bengio, 2000; Maclaurin et al., 2015; Xu et al., 2018b; Zahavy et al., 2020),
discovering black-box loss functions (Chen et al., 2016; Kirsch et al., 2019;
Xu et al., 2020; Oh et al., 2020), black-box learning algorithms (Hochreiter
et al., 2001; Wang et al., 2016), or entire training protocols (Real et al.,
2020). Yet, very little is known in terms of the theoretical properties of
meta-learning.

The reason for this is the complex interaction between the learner and the
meta-learner. learner’s problem is to minimize the expected loss $f$ of a
stochastic objective by adapting its parameters
$x\in\operatorname{{\mathbb{R}}}^{n}$. The learner has an update rule
$\varphi$ at its disposal that generates new parameters
$x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$; we suppress data dependence to
simplify notation. A simple example is when $\varphi$ represents gradient
descent with $w_{t}=\eta$ its step size, that is
$\varphi(x_{t-1},\eta)=-\eta\nabla f(x_{t-1})$ (Mahmood et al., 2012; van
Erven and Koolen, 2016); several works have explored meta-learning other
aspects of a gradient-based update rule (Finn et al., 2017; Nichol et al.,
2018; Flennerhag et al., 2019; Xu et al., 2018b; Zahavy et al., 2020;
Flennerhag et al., 2022; Kirsch et al., 2019; Oh et al., 2020). More
generally, $\varphi$ need not be limited to the gradient of any function, for
instance, it can represent some algorithm implemented within a Recurrent
Neural Network (Schmidhuber, 1987; Hochreiter et al., 2001; Andrychowicz et
al., 2016; Wang et al., 2016).

The meta-learner’s problem is to optimise the meta-parameters $w_{t}$ to yield
effective _updates_. In a typical (gradient-based) meta-learning setting, it
does so by treating $x_{t}$ as a function of $w$. Let $h_{t}$, defined by
$h_{t}(w)=f(x_{t-1}+\varphi(x_{t-1},w))$, denote the learner’s post-update
performance as a function of $w$. The learner and the meta-learner co-evolve
according to

$\displaystyle x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t}),\qquad\text{and}\qquad
w_{t+1}$ $\displaystyle=w_{t}-\nabla h_{t}(w_{t})$
$\displaystyle=w_{t}-D\varphi(x_{t-1},w_{t})^{T}\nabla f(x_{t}),$

where $D\varphi(x,w)$ denotes the Jacobian of $\varphi$ with respect to $w$.
The nested structure between these two updates makes it challenging to analyse
meta-learning, in particular it depends heavily on the properties of the
Jacobian. In practice, $\varphi$ is highly complex and so $D\varphi$ is almost
always intractable. For instance, in Xu et al. (2018a), the meta-parameters
define the data-distribution under which a stochastic gradient is computed. In
Zahavy et al. (2020), the meta-parameters define auxiliary objectives that are
meant to help with representation learning; in Vinyals et al. (2016) they
learn an embedding space for nearest-neighbour predictions.

For this reason, the only theoretical results we are aware of specialise to
the multi-task setting and assume $\varphi$ represents adaptation by gradient
descent. In this setting, at each iteration $t$, the learner must adapt to a
new task $f_{t}$. The learner adapts by taking a (or several) gradient step(s)
on $f_{t}$ using either a meta-learned initialisation (Flennerhag et al.,
2019; Finn et al., 2019; Fallah et al., 2020; Wang et al., 2022) or using a
meta-learned regulariser (Khodak et al., 2019; Denevi et al., 2019). Because
the update rule has this form, it is possible to treat the meta-optimisation
problem as an online learning problem and derive convergence guarantees.
Acceleration in this setup is driven by the tasks similarity. That is, if all
tasks are sufficiently similar, a meta-learned update can accelerate
convergence (Khodak et al., 2019). However, these results do not yield
acceleration in the absence of a task distribution to the best of our
knowledge.

This paper provides an alternative view. We study the classical convex
optimisation setting of approximating the minimiser $\min_{x}f(x)$. We observe
that setting the update rule equal to the gradient, i.e. $\varphi:(x,w)\mapsto
w\nabla f(x)$, recovers gradient descent. Similarly, we show in Section 3 that
$\varphi$ can be chosen to recover gradient descent with momentum. This offers
another view of meta-learning as a non-linear transformation of classical
optimisation. A direct implication of this is that a task similarity is not
necessary condition for improving the rate of convergence via meta-learning.
While there is ample empirical evidence to that effect (Xu et al., 2018b;
Zahavy et al., 2020; Flennerhag et al., 2022; Luketina et al., 2022), we are
only aware of theoretical results in the special case of meta-learned step
sizes (Mahmood et al., 2012; van Erven and Koolen, 2016).

In particular, we analyse meta-learning using recent techniques developed for
convex optimisation (Cutkosky, 2019; Joulani et al., 2020; Wang et al., 2021).
Given a function $f$ that is convex with Lipschitz smooth gradients, meta-
learning improves the rate of convergence by a multiplicative factor $\lambda$
to $O(\lambda/T)$, via the smoothness of the update rule. Importantly, these
works show that to achieve accelerated convergence, $O(1/T^{2})$, some form of
optimism is required. This optimism essentially provides a prediction of the
next gradient, and hence represents a model of the geometry. We consider
optimism with meta-learning in the convex setting and prove accelerated rates
of convergence, $O(\lambda/T^{2})$. Again, meta-learning affects these bounds
by a multiplicative factor. We further show that optimism in meta-learning can
be expressed through the recently proposed Bootstrapped Meta-Gradient method
(BMG; Flennerhag et al., 2022). Our analysis provides a first proof of
convergence for BMG and highlights the underlying mechanics that enable faster
learning with BMG. Our main contributions are as follows:

  1. 1.

We show that meta-learning contains gradient descent with momentum (Heavy Ball
(Polyak, 1964); Section 3) and Nesterov Acceleration (Nesterov, 1983) as
special cases (Section 6).

  2. 2.

We show that gradient-based meta-learning can be understood as a non-linear
transformation of an underlying optimisation method (Section 3).

  3. 3.

We establish rates of convergence for meta-learning in the convex setting
(Sections 5 and 6).

  4. 4.

We show that optimism can be expressed through (Flennerhag et al., 2022). Our
analysis (Section 6) provides a first proof of convergence for BMG.

input : Weights $\\{\beta_{t}\\}^{T}_{t=1}$

input : Update rule $\varphi$

input : Initialisation $(x_{0},w_{1})$

for   _$t=1,2,\ldots,T$ :_

$x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$

$h_{t}(\cdot)=f(x_{t-1}+\rho_{t}\varphi(x_{t-1},\cdot))$

$w_{t+1}=w_{t}-\beta_{t}\nabla h_{t}(w_{t})$

return _$x_{T}$_

Algorithm 1 Meta-learning in practice.

input : Weights $\\{\alpha_{t}\\}^{T}_{t=1},\\{\beta_{t}\\}^{T}_{t=1}$

input : Update rule $\varphi$

input : Initialisation $(\bar{x}_{0},w_{1})$

for   _$t=1,2,\ldots,T$ :_

$x_{t}=\varphi(\bar{x}_{t-1},w_{t})$

$\bar{x}_{t}=(1-\alpha_{t}/\alpha_{1:t})\bar{x}_{t-1}+(\alpha_{t}/\alpha_{1:t})x_{t}$

$g_{t}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t})$

$w_{t+1}\\!\\!=\\!\arg\min_{w\in\operatorname{\mathcal{W}}}\\!\sum_{s=1}^{t}\\!\alpha_{s}\langle
g_{s},w\rangle\\!+\\!\frac{1}{2\beta_{t}}\|w\|^{2}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$

return _$\bar{x}_{T}$_

Algorithm 2 Meta-learning in the convex setting.

##  2 Meta-learning meets convex optimisation

#### Problem definition.

This section defines the problem studied in this paper and introduces our
notation. Let $f:\operatorname{\mathcal{X}}\to\operatorname{{\mathbb{R}}}$ be
a proper and convex function. The problem of interest is to approximate the
global minimum $\min_{x\in\operatorname{\mathcal{X}}}f(x)$. We assume a global
minimiser exists and is unique, defined by

$x^{*}=\operatorname*{arg\,min\ }_{x\in\operatorname{\mathcal{X}}}f(x).$ (1)

We assume that
$\operatorname{\mathcal{X}}\subseteq\operatorname{{\mathbb{R}}}^{n}$ is a
closed, convex and non-empty set. $f$ is differentiable and has Lipschitz
smooth gradients with respect to a norm $\|\cdot\|$, meaning that there exists
$L\in(0,\infty)$ such that $\|\nabla f(x)-\nabla f(y)\|_{*}\leq L\|x-y\|$ for
all $x,y\in\operatorname{\mathcal{X}}$, where $\|\cdot\|_{*}$ is the dual norm
of $\|\cdot\|$. We consider the noiseless setting for simplicity; our results
carry over to the stochastic setting by replacing the key online-to-batch
bound used in our analysis by its stochastic counterpart (Joulani et al.,
2020).

#### Algorithm.

Algorithm 1 describes a typical meta-learning algorithm. Unfortunately, at
this level of generality, little can be said about the its convergence
properties. Instead, we consider a stylized variant of meta-learning,
described in Algorithm 2. This model differs in three regards: (a) it relies
on moving averages (b) we use a different online learning algorithm for the
meta-update, and (c) we make stricter assumptions on the update rule. We
describe each component in turn.

Let $[T]=\\{1,2,\ldots,T\\}$. We are given weights
$\\{\alpha_{t}\\}_{t=1}^{T}$, each $\alpha_{t}>0$, and an initialisation
$(\bar{x}_{0},w_{1})\in\operatorname{\mathcal{X}}\times\operatorname{\mathcal{W}}$.
At each time $t\in[T]$, an update rule
$\varphi:\operatorname{\mathcal{X}}\times\operatorname{\mathcal{W}}\to\operatorname{\mathcal{X}}$
generates the update $x_{t}=\varphi(\bar{x}_{t-1},w_{t})$, where
$\operatorname{\mathcal{W}}\subseteq\operatorname{{\mathbb{R}}}^{m}$ is
closed, convex, and non-empty. We discuss $\varphi$ momentarily. The algorithm
maintains the online average

$\bar{x}_{t}=\frac{x_{1:t}}{\alpha_{1:t}}=(1-\rho_{t})\bar{x}_{t-1}+\rho_{t}x_{t},$
(2)

where $x_{1:t}=\sum_{s=1}^{t}\alpha_{s}x_{s}$,
$\alpha_{1:t}=\sum_{s=1}^{t}\alpha_{s}$, and
$\rho_{t}=\alpha_{t}/\alpha_{1:t}$. Our goal is to establish conditions under
which $\\{\bar{x}_{t}\\}_{t=1}^{T}$ 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-batch conversion (Wang and
Abernethy, 2018; Cutkosky, 2019; Joulani et al., 2020).

Convergence depends on how each $w_{t}$ is chosen. In Algorithm 1, the meta-
learner faces a sequence of losses
$h_{t}:\operatorname{\mathcal{W}}\to\operatorname{{\mathbb{R}}}$ defined by
the composition
$h_{t}(w)=f((1-\rho_{t})\bar{x}_{t-1}+\rho_{t}\varphi(\bar{x}_{t-1},w))$. This
makes meta-learning a form of online optimisation (McMahan, 2017). The meta-
updates in Algorithm 1 is an instance of online gradient descent, which we can
model as Follow-The-Regularized-Leader (FTRL; reviewed in Section 4). Given
some norm $\|\cdot\|$, an initialization $w_{0}$ and $\beta>0$, FTRL sets each
$w_{t}$ according to

$w_{t+1}=\operatorname*{arg\,min\
}_{w\in\operatorname{\mathcal{W}}}\left(\sum_{s=1}^{t}\alpha_{s}\langle\nabla
h_{s}(w_{s}),w\rangle+\frac{1}{2\beta}\|w\|^{2}\right).$ (3)

If $\|\cdot\|$ is the Euclidean norm, the interior solution to Eq. 3 is given
by $w_{t+1}=w_{t}-\alpha_{t}\beta\nabla h_{t}(w_{t})$, the meta-update in
Algorithm 1. It is straightforward to extend Eq. 3 to account for meta-updates
that use AdaGrad-like (Duchi et al., 2011) acceleration by altering the norms
(Joulani et al., 2017).

#### Update rule.

It is not possible to prove convergence outside of the convex setting, since
$\varphi$ may reach a local minimum where it cannot yield better updates, but
the updates are not sufficient to converge. Convexity means that each $h_{t}$
must be convex, which requires that $\varphi$ is affine in $w$ (but may vary
non-linearly in $x$). We also assume that $\varphi$ is smooth with respect to
$\|\cdot\|$, in the sense that it has bounded norm; for all
$x\in\operatorname{\mathcal{X}}$ and all $w\in\operatorname{\mathcal{W}}$ we
assume that there exists $\lambda\in(0,\infty)$ for which

$\|D\varphi(x,w)^{T}\nabla f(x)\|^{2}_{*}\leq\lambda\|\nabla f(x)\|^{2}_{*}.$

These assumptions hold for any smooth update rule up to first-order Taylor
approximation error.

Figure 2: Convex Quadratic. We generate convex quadratic loss functions with
ill-conditioning and compare gradient descent with momentum and AdaGrad to
meta-learning variants. Meta-Momentum uses $\varphi:(x,w)\mapsto w\odot\nabla
f(x)$ while Meta-AdaGrad uses $\varphi:(x,w)\mapsto\nabla f(x)/\sqrt{w}$,
where division is element-wise. _Top:_ loss per iteration for randomly sampled
loss functions. _Bottom:_ cumulative loss (regret) at the end of learning as a
function of learning rate; details in Appendix B.

##  3 Meta-Gradients in the Convex Setting - An Overview

In this section, we provide an informal discussion of our main results (full
analysis; Sections 5 and 6).

#### Meta-Gradients without Optimism.

The main difference between classical optimisation and meta-learning is the
introduction of the update rule $\varphi$. To see how this acts on
optimisation, consider two special cases. If the update rule just return the
gradient, $\varphi=\nabla f$, Algorithm 2 is reduced to gradient descent (with
averaging). The inductive bias is fixed and does not change with past
experience, and so acceleration is not possible—the rate of convergence is
$O(1/\sqrt{T})$ (Wang et al., 2021). The other extreme is an update rule that
only depends on the meta-parameters, $\varphi(x,w)=w$. Here, the meta-learner
has ultimate control and selects the next update without constraints. The only
relevant inductive bias is contained in $w$. To see how this inductive bias is
formed, suppose $\|\cdot\|=\|\cdot\|_{2}$ so that Eq. 3 yields
$w_{t+1}=w_{t}-\alpha_{t}\rho_{t}\beta\nabla f(\bar{x}_{t})$ (assuming an
interior solution). Combining this with the moving average in Eq. 2, we may
write the learner’s iterates as

$\bar{x}_{t}=\bar{x}_{t-1}+\tilde{\rho}_{t}\left(\bar{x}_{t-1}-\bar{x}_{t-2}\right)-\tilde{\beta}_{t}\nabla
f(\bar{x}_{t-1}),$

where each $\tilde{\rho_{t}}=\rho_{t}\frac{1-\rho_{t-1}}{\rho_{t-1}}$ and
$\tilde{\beta}_{t}=\alpha_{t}\rho_{t}\beta$; setting $\beta=1/(2L)$ and each
$\alpha_{t}=t$ yields $\tilde{\rho}_{t}=\frac{t-2}{t+1}$ and
$\tilde{\beta}_{t}=t/(4(t+1)L)$. Hence, the canonical momentum algorithm,
Polyak’s Heavy-Ball method (Polyak, 1964), is obtained as the special case of
meta-learning under the update rule $\varphi:(x,w)\mapsto w$. Because Heavy
Ball carries momentum from past updates, it can encode a model of 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 update rule in the same cumulative manner.
This manifests theoretically through its convergence guarantees.

######  Theorem 1 (_Informal_).

Set $\alpha_{t}=1$ and $\beta=\frac{1}{\lambda L}$. If each $x_{t}$ is
generated under Algorithm 2, then for any viable $\varphi$,
$f(\bar{x}_{T})-f(x^{*})\leq\frac{\lambda
L\operatorname{diam}(\operatorname{\mathcal{W}})}{T}$.

We refer the reader to Theorem 3 for a formal statement. Compared to Heavy
Ball, meta-learning introduces a constant $\lambda$ that captures the
smoothness of the update rule. Hence, while meta-learning does not achieve
better scaling in $T$ through $\varphi$, it can improve upon classical
optimisation by a constant factor if $\lambda<1$. That meta-learning can
improve upon momentum is borne out experimentally. In Figure 2, we consider
the problem of minimizing a convex quadratic $f:x\mapsto\langle x,Qx\rangle$,
where $Q\in\operatorname{{\mathbb{R}}}^{n\times n}$ is PSD but ill-
conditioned. We compare momentum to a meta-learned step-size, i.e.
$\varphi:(x,w)\mapsto w\odot\nabla f(x)$, where $\odot$ is the Hadamard
product. Across randomly sampled $Q$ matrices (details: Appendix B), we find
that introducing a non-linearity $\varphi$ leads to a sizeable improvement in
the rate of convergence. We also compare AdaGrad to a meta-learned version,
$\varphi:(x,w)\mapsto\nabla f(x)/\sqrt{w}$, where division is element-wise.
While AdaGrad is a stronger baseline on account of being parameter-free, we
find that meta-learning the scale vector consistently leads to faster
convergence.

#### Meta-Gradients with Optimism.

It is well known that minimizing a smooth convex function admits convergence
rates of $O(1/T^{2})$. Our analysis of standard meta-gradients does not
achieve such acceleration. Previous work indicate that we should not expect to
either; to achieve the theoretical lower-limit of $O(1/T^{2})$, some form of
_optimism_ (reviewed in Section 4) is required. A typical form of optimism is
to predict the next gradient. This is how Nesterov Acceleration operates
(Nesterov, 1983) and is the reason for its $O(1/T^{2})$ convergence guarantee.

From our perspective, meta-learning is a non-linear transformation of the
iterate $x$. Hence, we should expect optimism to play a similarly crucial
role. Formally, optimism comes in the form of _hint functions_
$\\{\tilde{g}_{t}\\}_{t=1}^{T}$, each
$\tilde{g}_{t}\in\operatorname{{\mathbb{R}}}^{m}$, that are revealed to the
meta-learner prior to selecting $w_{t+1}$. These hints give rise to
_Optimistic Meta-Learning_ (OML) via meta-updates

$w_{t+1}=\operatorname*{arg\,min\
}_{w\in\operatorname{\mathcal{W}}}\left(\alpha_{t+1}\tilde{g}_{t+1}+\sum_{s=1}^{t}\alpha_{s}\langle\nabla
h_{s}(w_{s}),w\rangle+\frac{1}{2\beta_{t}}\|w\|^{2}\right).$ (4)

If the hints are accurate, meta-learning with optimism can achieve an
accelerated rate of $O(\tilde{\lambda}/T^{2})$, where $\tilde{\lambda}$ is a
constant that characterises the smoothness of $\varphi$, akin to $\lambda$.
Again, we find that meta-learning behaves as a non-linear transformation of
classical optimism and its rate of convergence is governed by the geometry it
induces. We summarise this result in the following result.

######  Theorem 2 (Informal).

Let each hint be given by
$\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t})$.
Assume that $\varphi$ is sufficiently smooth. Set $\alpha_{t}=t$ and
$\beta_{t}=\frac{t-1}{2t\tilde{\lambda}L}$, then
$f(\bar{x}_{T})-f(x^{*})\leq\frac{4\tilde{\lambda}L\operatorname{diam}(\operatorname{\mathcal{W}})}{T^{2}-1}$.

For a formal statement, see Theorem 4. These predictions hold empirically in a
non-convex setting. We train a 50-layer ResNet using either SGD with a fixed
learning rate, or an update rule that adapts a per-parameter learning rate
online, $\varphi:(x,w)\mapsto w\odot\nabla f(x)$. We compare the standard
meta-learning approach without optimism to optimistic meta-learning. Figure 1
shows that optimism is critical for meta-learning to achieve acceleration, as
predicted by theory (experiment details in Appendix C).

##  4 Analysis preliminaries: Online Convex Optimisation

In this section, we present analytical tools from the optimisation literature
that we build upon. In a standard optimisation setting, there is no update
rule $\varphi$; instead, the iterates $x_{t}$ are generated by a gradient-
based algorithm, akin to Eq. 3. In particular, our setting reduces to standard
optimisation if $\varphi$ is defined by $\varphi:(x,w)\mapsto w$, in which
case $x_{t}=w_{t}$. A common approach to analysis is to treat the iterates
$x_{1},x_{2},\ldots$ as generated by an online learning algorithm over online
losses, obtain a regret guarantee for the sequence, and use online-to-batch
conversion to obtain a rate of convergence.

#### Online Optimisation.

In online convex optimisation (Zinkevich, 2003), a learner is given a convex
decision set $\operatorname{\mathcal{U}}$ and faces a sequence of convex loss
functions $\\{\alpha_{t}f_{t}\\}_{t=1}^{T}$. At each time $t\in[T]$, it must
make a prediction $u_{t}$ prior to observing $\alpha_{t}f_{t}$, after which it
incurs a loss $\alpha_{t}f_{t}(u_{t})$ and receives a signal—either
$\alpha_{t}f_{t}$ itself or a (sub-)gradient of $\alpha_{t}f_{t}(u_{t})$. The
learner’s goal is to minimise _regret_ ,
$R(T)\coloneqq\sum_{t=1}^{T}\alpha_{t}(f_{t}(u_{t})-f_{t}(u))$, against a
comparator $u\in\operatorname{\mathcal{U}}$. An important property of a convex
function $f$ is $f(u^{\prime})-f(u)\leq\langle\nabla
f(u^{\prime}),u^{\prime}-u\rangle$. Hence, the regret is largest under linear
losses:
$\sum_{t=1}^{T}\alpha_{t}(f_{t}(u_{t})-f_{t}(u))\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f_{t}(u_{t}),u_{t}-u\rangle$. For this reason, it is sufficient to consider
regret under linear loss functions. An algorithm has sublinear regret if
$\lim_{T\to\infty}R(T)/T=0$.

#### FTRL & AO-FTRL.

The meta-update in Eq. 3 is an instance of Follow-The-Regularised-Leader
(FTRL) under linear losses. In Section 6, we show that BMG is an instance of
the Adaptive-Optimistic FTRL (AO-FTRL), which is an extension due to (Rakhlin
and Sridharan, 2013; Mohri and Yang, 2016; Joulani et al., 2020; Wang et al.,
2021). In AO-FTRL, we have a strongly convex regulariser $\|\cdot\|^{2}$. FTRL
and AO-FTRL sets the first prediction $u_{1}$ to minimise $\|\cdot\|^{2}$.
Given linear losses $\\{g_{s}\\}_{s=1}^{t-1}$ and learning rates
$\\{\beta_{t}\\}_{t=1}^{T}$, each $\beta_{t}>0$, the algorithm proceeds
according to

$u_{t}=\operatorname*{arg\,min\
}_{u\in\operatorname{\mathcal{U}}}\left(\alpha_{t}\langle\tilde{g}_{t},u\rangle+\sum_{s=1}^{t-1}\alpha_{s}\langle
g_{s},u\rangle+\frac{1}{2\beta_{t}}\|u\|^{2}\right),$ (5)

where each $\tilde{g}_{t}$ is a “hint” that enables optimistic learning
(Rakhlin and Sridharan, 2013; Mohri and Yang, 2016); setting $\tilde{g}_{t}=0$
recovers the original FTRL algorithm. The goal of a hint is to predict the
next loss vector $g_{t}$; if the predictions are accurate AO-FTRL can achieve
lower regret than its non-optimistic counter-part. Since $\|\cdot\|^{2}$ is
strongly convex, FTRL is well defined in the sense that the minimiser exists,
is unique and finite (McMahan, 2017). The regret of FTRL and AO-FTRL against
any comparator $u\in\operatorname{\mathcal{U}}$ can be upper-bounded by

$R(T)=\sum_{t=1}^{T}\alpha_{t}\langle
g_{t},u_{t}-u\rangle\leq\frac{\|u\|^{2}}{2\beta_{T}}+\frac{1}{2}\sum_{t=1}^{T}\alpha_{t}^{2}\beta_{t}\left\|g_{t}-\tilde{g}_{t}\right\|_{*}^{2}.$
(6)

Hence, hints that predict $g_{t}$ well can reduce the regret substantially.
Without hints, FTRL can guarantee $O(\sqrt{T})$ regret (for non strongly
convex loss functions). However, Dekel et al. (2017) show that under linear
losses, if hints are weakly positively correlated—defined as $\langle
g_{t},\tilde{g}_{t}\rangle\geq\epsilon\|g_{t}\|^{2}$ for some
$\epsilon>0$—then the regret guarantee improves to $O(\log T)$, even for non
strongly-convex loss functions. We believe optimism provides an exciting
opportunity for novel forms of meta-learning. Finally, we note that these
regret bounds (and hence our analysis) can be extended to stochastic
optimisation (Mohri and Yang, 2016; Joulani et al., 2017).

#### Online-to-batch conversion.

The main idea behind online to batch conversion is that, for $f$ convex,
Jensen’s inequality gives
$f(\bar{x}_{T})-f(x^{*})\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(x_{t}),x_{t}-x^{*}\rangle/\alpha_{1:T}$. Hence, one can provide a
convergence rate by first establishing the regret of the algorithm that
generates $x_{t}$, from which one obtains the convergence rate of the moving
average of iterates. Applying this naively yields $O(1/T)$ rate of
convergence. In recent work, Cutkosky (2019) shows that one can upper-bound
the sub-optimality gap by instead querying the gradient gradient at the
average iterate,
$f(\bar{x}_{T})-f(x^{*})\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),x_{t}-x^{*}\rangle/\alpha_{1:T}$, which can yield faster rates
of convergence. Recently, Joulani et al. (2020) tightened the analysis and
proved that the sub-optimality gap can be bounded by

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$ (7)
$\displaystyle\frac{1}{\alpha_{1:T}}\left(R^{x}(T)-\frac{\alpha_{t}}{2L}\|\nabla
f(\bar{x}_{t})-\nabla f(x^{*})\|_{*}^{2}-\frac{\alpha_{1:t-1}}{2L}\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|_{*}^{2}\right),$

were we define $R^{x}(T)\coloneqq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),x_{t}-x^{*}\rangle$ as the regret of the sequence
$\\{x_{t}\\}_{t=1}^{T}$ against the comparator $x^{*}$. With this machinery in
place, we now turn to deriving our main results.

##  5 Analysis

Our analytical goal is to apply the online-to-batch conversion bound in Eq. 7
to the iterates $x_{1},x_{2},\ldots,x_{T}$ that Algorithm 2 generates. Our
main challenge is that the update rule $\varphi$ prevents a straightforward
application of this bound. Instead, we must upper bound the learner’s regret
$R^{x}$ by the meta-learner’s regret, which is defined in terms of the
iterates $w_{1},w_{2},\ldots,w_{T}$. To this end, we may decompose $R^{x}$ as
follows:

$\displaystyle R^{x}(T)$ $\displaystyle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),x_{t}-x^{*}\rangle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w_{t})-x^{*}\rangle$
$\displaystyle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle+\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle.$

The first term in the final expression can be understood as the regret under
convex losses $\ell_{t}(\cdot)=\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},\cdot)\rangle$. Since
$\varphi(\bar{x}_{t-1},\cdot)$ is affine, $\ell_{t}$ is convex and can be
upper bounded by its linearisation. The linearisation reads $\langle
D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t}),\cdot\rangle$, which is
identical the linear losses $\langle\nabla h_{t}(w_{t}),\cdot\rangle$ faced by
the meta-learner in Eq. 3. Hence, we may upper bound $R^{x}(T)$ by

$\displaystyle R^{x}(T)$ $\displaystyle\leq\sum_{t=1}^{T}\alpha_{t}\langle
D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t}),w_{t}-w^{*}\rangle+\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle$
$\displaystyle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
h_{t}(w_{t}),w_{t}-w^{*}\rangle+\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle$
$\displaystyle=R^{w}(T)+\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle,$ (8)

where the last identity follows by definition:
$R^{w}(T)\coloneqq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
h_{t}(w_{t}),w_{t}-w^{*}\rangle$. For the last term in Eq. 8 to be negative,
so that $R^{w}(T)\geq R^{x}(T)$, we need the relative power of the comparator
$w^{*}$ to be greater than that of the comparator $x^{*}$. Intuitively, the
comparator $x^{*}$ is non-adaptive. It must make one choice $x^{*}$ and suffer
the average loss. In contrast, the comparator $w^{*}$ becomes adaptive under
the update rule; it can only choose one $w^{*}$, but on each round it plays
$\varphi(\bar{x}_{t-1},w^{*})$. If $\varphi$ 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, we say that
regret is _preserved_ when moving from $x^{*}$ to $w^{*}$.

######  Definition 1.

Given $f$, $\\{\alpha_{t}\\}_{t=1}^{T}$, and $\\{x_{t}\\}_{t=1}^{T}$, an
update rule
$\varphi:\operatorname{\mathcal{X}}\times\operatorname{\mathcal{W}}\to\operatorname{\mathcal{X}}$
_preserves regret_ if there exists a comparator
$w\in\operatorname{\mathcal{W}}$ that satisfies

$\sum_{t=1}^{T}\alpha_{t}\langle\varphi(\bar{x}_{t-1},w),\nabla
f(\bar{x}_{t})\rangle\leq\sum_{t=1}^{T}\alpha_{t}\langle x^{*},\nabla
f(\bar{x}_{t})\rangle.$ (9)

If such $w$ exists, let $w^{*}$ denote the comparator with smallest norm
$\|w\|$.

By inspecting Eq. 9, we see that if $\varphi(\bar{x}_{t-1},\cdot)$ can be made
to negatively align with the gradient $\nabla f(\bar{x}_{t})$, the update rule
preserves regret. Hence, any update rule that is gradient-like in its
behaviour can be made to preserve regret. However, this must not hold on every
step, only sufficiently often; nor does it imply that the update rule must
explicitly invoke $\nabla f$; for instance, update rules that are affine in
$w$ preserve regret if the diameter of $\operatorname{\mathcal{W}}$ is
sufficiently large, provided the update rule is not degenerate.

######  Lemma 1.

Given $f$, $\\{\alpha_{t}\\}_{t=1}^{T}$, and $\\{x_{t}\\}_{t=1}^{T}$, if
$\varphi$ preserves regret, then

$R^{x}(T)=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),x_{t}-x^{*}\rangle\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle=R^{w}(T).$

Proof: Appendix D. With Lemma 1, we can provide a convergence guarantee for
meta-gradients in the convex setting. The mechanics of the proof is to use
online-to-batch conversion to upper bound $f(\bar{x}_{T})-f(x^{*})\leq
R^{x}(T)/\alpha_{1:T}$ and then appeal to Lemma 1 to obtain
$f(\bar{x}_{T})-f(x^{*})\leq R^{w}(T)/\alpha_{1:T}$, from which point we can
plug in the FTRL regret bound.

######  Theorem 3.

Let $\varphi$ preserve regret and assume Algorithm 2 satisfies the assumptions
in Section 2. Then

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$
$\displaystyle\frac{1}{\alpha_{1:T}}\left(\frac{\|w^{*}\|^{2}}{\beta}+\sum_{t=1}^{T}\frac{\lambda\beta\alpha^{2}_{t}}{2}\|\nabla
f(\bar{x}_{t})\|_{*}^{2}\right.$
$\displaystyle\left.\vphantom{\sum_{t=1}^{T}}-\frac{\alpha_{t}}{2L}\|\nabla
f(\bar{x}_{t})-\nabla f(x^{*})\|_{*}^{2}-\frac{\alpha_{1:t-1}}{2L}\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|_{*}^{2}\right).$

Moreover, if $x^{*}$ is a global minimiser of $f$, setting $\alpha_{t}=1$ and
$\beta=\frac{1}{\lambda L}$ yields

$f(\bar{x}_{T})-f(x^{*})\leq\frac{\lambda
L\operatorname{diam}(\operatorname{\mathcal{W}})}{T}.$

Proof: Appendix D.

##  6 Meta-Learning meets Optimism

The reason Theorem 3 fails to achieve acceleration is because the negative
terms, $-\|\nabla f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|^{2}_{*}$, do not
come into play. This is because the positive term in the bound involves the
norm of the gradient, rather than the norm of the difference of two gradients.
The former is typically a larger quantity and hence we cannot guarantee that
they vanish. To obtain acceleration, we need some form of optimism. In this
section, we consider an alteration to Algorithm 2 that uses AO-FTRL for the
meta-updates. Given some sequence of hints $\\{\tilde{g}_{t}\\}_{t=1}^{T}$,
each $\tilde{g}_{t}\in\operatorname{{\mathbb{R}}}^{m}$, each $w_{t+1}$ is
given by

$w_{t+1}=\operatorname*{arg\,min\
}_{w\in\operatorname{\mathcal{W}}}\left(\alpha_{t+1}\tilde{g}_{t+1}+\sum_{s=1}^{t}\alpha_{s}\langle\nabla
h_{s}(w_{s}),w\rangle+\frac{1}{2\beta_{t}}\|w\|^{2}\right).$ (10)

input : Weights $\\{\beta_{t}\\}^{T}_{t=1}$

input : Update rule $\varphi$

input : Target oracle

input : Initialisation $(x_{0},w_{1})$

for   _$t=1,2,\ldots,T$ :_

$x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$

Query $z_{t}$ from target oracle

$d_{t}(\cdot)=\|z_{t}-x_{t}+\varphi(x_{t},\cdot)\|^{2}$

$w_{t+1}=w_{t}-\beta_{t}\nabla d_{t}(w_{t})$

return _$x_{T}$_

Algorithm 3 BMG in practice.

input : Weights $\\{\alpha_{t}\\}^{T}_{t=1},\\{\beta_{t}\\}^{T}_{t=1}$

input : Update rule $\varphi$

input : Hints $\\{\tilde{g}_{t}\\}^{T}_{t=1}$

input : Initialisation $(\bar{x}_{0},w_{1})$

for   _$t=1,2,\ldots,T$ :_

$x_{t}=\varphi(\bar{x}_{t-1},w_{t})$

$\bar{x}_{t}=(1-\alpha_{t}/\alpha_{1:t})\bar{x}_{t-1}+(\alpha_{t}/\alpha_{1:t})x_{t}$

$g_{t}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t})$

$v_{t}=\alpha_{t+1}\tilde{g}_{t+1}+\sum_{s=1}^{t}\alpha_{s}g_{s}$

$w_{t+1}=\arg\min_{w\in\operatorname{\mathcal{W}}}\langle
v_{t},w\rangle+\frac{1}{2\beta_{t}}\|w\|^{2}$

return _$\bar{x}_{T}$_

Algorithm 4 Convex optimistic meta-learning.

Otherwise, we proceed as in Algorithm 2; for a complete description, see
Algorithm 4. The AO-FTRL updates do not correspond to a standard meta-update.
However, we show momentarily that optimism can be instantiated via the BMG
method, detailed in Algorithm 3. The proof for optimistic meta-gradients
proceed largely as in Theorem 3, it only differs in that we apply the AO-FTRL
regret bound.

######  Theorem 4.

Let $\varphi$ preserve regret and assume Algorithm 4 satisfy the assumptions
in Section 2. Then

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$
$\displaystyle\frac{1}{\alpha_{1:T}}\left(\frac{\|w^{*}\|^{2}}{\beta_{T}}+\sum_{t=1}^{T}\frac{\alpha^{2}_{t}\beta_{t}}{2}\|D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t}\|_{*}^{2}\right.$
$\displaystyle\left.\vphantom{\sum_{t=1}^{T}}-\frac{\alpha_{t}}{2L}\|\nabla
f(\bar{x}_{t})-\nabla f(x^{*})\|_{*}^{2}-\frac{\alpha_{1:t-1}}{2L}\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|_{*}^{2}\right).$

Moreover, assume each $\tilde{g}_{t}$ is such that
$\|D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t}\|_{*}^{2}\leq q\|\nabla f(\bar{x}_{t-1})-\nabla
f(\bar{x}_{t})\|_{*}^{2}$ for some $q>0$. If each $\alpha_{t}=t$ and
$\beta_{t}=\frac{t-1}{2tqL}$, then

$f(\bar{x}_{t})-f(x^{*})\leq\frac{4qL\operatorname{diam}(\operatorname{\mathcal{W}})}{T^{2}-1}.$

###### Proof.

The proof follows the same lines as that of Theorem 3. The only difference is
that the regret of the $\\{w_{t}\\}_{t=1}^{T}$ sequence can be upper bounded
by
$\frac{\|w^{*}\|^{2}}{\beta_{T}}+\frac{1}{2}\sum_{t=1}^{T}\alpha^{2}_{t}\beta_{t}\|\nabla
h_{t}(w_{t})-\tilde{g}_{t}\|_{*}^{2}$ instead of
$\frac{\|w^{*}\|^{2}}{\beta_{T}}+\frac{1}{2}\sum_{t=1}^{T}\alpha^{2}_{t}\beta_{t}\|\nabla
h_{t}(w_{t})\|_{*}^{2}$, as per the AO-FTRL regret bound in Eq. 6. The final
part follows immediately by replacing the norms and plugging in the values for
$\alpha$ and $\beta$. ∎

From Theorem 4, it is clear that if $\tilde{g}_{t}$ is a good predictor of
$D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t})$, then the positive
term in the summation can be cancelled by the negative term. In a classical
optimisation setting, $D\varphi=I_{n}$, and hence it is easy to see that
simply choosing $\tilde{g}_{t}$ to be the previous gradient is sufficient to
achieve the cancellation (Joulani et al., 2020). Indeed, this choice gives us
Nesterov’s Accelerated rate (Wang et al., 2021). The upshot of this is that we
can specialise Algorithm 4 to capture Nesterov’s Accelerated method by
choosing $\varphi:(x,w)\mapsto w$—as in the reduction to Heavy Ball—and
setting the hints to $\tilde{g}_{t}=\nabla f(\bar{x}_{t-1})$. Hence, while the
standard meta-update without optimism contains Heavy Ball as a special case,
the optimistic meta-update contains Nesterov Acceleration as a special case.

In the meta-learning setting, $D\varphi$ is not an identity matrix, and hence
the best targets for meta-learning are different. Naively, choosing
$\tilde{g}_{t}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t-1})$ would
lead to a similar cancellation, but this is not allowed. At iteration $t$, we
have not computed $w_{t}$ when $\tilde{g}_{t}$ is chosen, and hence
$D\varphi(\bar{x}_{t-1},w_{t})$ is not available. The nearest term that is
accessible is $D\varphi(\bar{x}_{t-2},w_{t-1})$.

######  Corollary 1.

Let each $\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})$. Assume that $\varphi$ satisfies

$\left\|D\varphi(x^{\prime},w)^{T}\nabla
f(x)-D\varphi(x^{\prime\prime},w^{\prime})^{T}\nabla
f(x^{\prime})\right\|_{*}^{2}\leq\tilde{\lambda}\left\|\nabla
f(x^{\prime})-\nabla f(x)\right\|_{*}^{2}$

for all $x^{\prime\prime},x^{\prime},x\in\operatorname{\mathcal{X}}$ and
$w,w^{\prime}\in\operatorname{\mathcal{W}}$, for some $\tilde{\lambda}>0$. If
each $\alpha_{t}=t$ and $\beta_{t}=\frac{t-1}{2t\tilde{\lambda}L}$, then
$f(\bar{x}_{T})-f(x^{*})\leq\frac{4\tilde{\lambda}L\operatorname{diam}(\operatorname{\mathcal{W}})}{T^{2}-1}$.

Proof: Appendix D.

###  6.1 Bootstrapped Meta-Gradients

In this section, we present a simplified version of BMG for clarity, with
Appendix E providing a fuller comparison. Essentially, BMG alters the meta-
update in Algorithm 1; instead of directly minimising the loss $f$, it
introduces a sequence of targets $z_{1},z_{2},\ldots$ and the meta-learner’s
goal is select $w$ so that the updated parameters minimise the distance these
targets. Concretely, given an update $x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$,
targets are _bootstrapped_ from $x_{t}$, meaning that a vector $y_{t}$ is
computed to produce the target $z_{t}=x_{t}-y_{t}$. Assuming the distance to
the target is measured under $\frac{1}{2}\|\cdot\|_{2}^{2}$, the BMG meta-
update takes the form

$\displaystyle w_{t+1}$
$\displaystyle=w_{t}-D\varphi(x_{t-1},w_{t})^{T}y_{t}.$

Depending on how $y_{t}$ is computed, it can encode optimism. For instance,
the authors rely on the update rule itself to compute a tangent
$y_{t}=\varphi(x_{t},w_{t})-\nabla f(x_{t}+\varphi(x_{t},w_{t}))$. This
encodes optimism via $\varphi$ because it encourages the meta-learner to build
up momentum (i.e. to accumulate past updates). We can contrast this with the
types of updates produced by AO-FTRL in Eq. 10. If we have hints
$\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\tilde{y}_{t+1}$ for some
$\tilde{y}_{t+1}\in\operatorname{{\mathbb{R}}}^{n}$ and set
$\|\cdot\|=\|\cdot\|_{2}$; assuming an interior solution, Eq. 10 yields

$w_{t+1}=w_{t}-\underbrace{D\varphi(\bar{x}_{t-1},w_{t})^{T}(\alpha_{t+1}\tilde{y}_{t+1}+\alpha_{t}\nabla
f(\bar{x}_{t}))}_{\text{BMG
update}}+\underbrace{\alpha_{t}D\varphi(\bar{x}_{t-2},w_{t-1})^{T}\tilde{y}_{t}}_{\text{FTRL
error correction}}.$ (11)

Hence, BMG encodes very similar dynamics to those of AO-FTRL in Eq. 10. Under
this choice of hints, the main qualitative difference is that AO-FTRL includes
a correction term. The effect of this term is to “undo” previous hints to
avoid feedback loops. Notably, BMG can suffer from divergence due to feedback
if the gradient in $y_{t}$ is not carefully scaled (Flennerhag et al., 2022).
Our theoretical analysis suggests a simple correction method that may
stabilize BMG in practice.

More generally, targets in BMG are isomorphic to the hint function in AO-FTRL
if the measure of distance in BMG is a Bregman divergence under a strongly
convex function (Appendix E). An immediate implication of this is that the
hints in Corollary 1 can be expressed as targets in BMG, and hence if BMG
satisfies the assumptions involved, it converges at a rate
$O(\tilde{\lambda}/T^{2})$. More generally, Theorem 4 provides a sufficient
condition for any target bootstrap in BMG to achieve acceleration.

######  Corollary 2.

Let each $\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\tilde{y}_{t+1}$,
for some $\tilde{y}_{t+1}\in\operatorname{{\mathbb{R}}}^{n}$. If each
$\tilde{y}_{t+1}$ is a better predictor of the next gradient than $\nabla
f(\bar{x}_{t-1})$, in the sense that

$\|D\varphi(\bar{x}_{t-2},w_{t-1})^{T}\tilde{y}_{t}-D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})\|_{*}\leq\tilde{\lambda}\|\nabla f(\bar{x}_{t})-\nabla
f(\bar{x}_{t-1})\|_{*},$

then Algorithm 4 guarantees convergence at a rate $O(\tilde{\lambda}/T^{2})$.

##  7 Conclusion

This paper explores a connection between convex optimisation and meta-
learning. We construct an algorithm for convex optimisation that aligns as
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 a 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-learning to achieve
acceleration, it is important to introduce some form of optimism. From a
classical optimisation point of view, such optimism arises naturally by
providing the meta-learner with hints. If hints are predictive of the learning
dynamics these can lead to significant acceleration. We show that the recently
proposed BMG method provides a natural avenue to incorporate optimism in
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

  * Alet et al. [2020] F. Alet, M. F. Schneider, T. Lozano-Perez, and L. P. Kaelbling.  Meta-Learning Curiosity Algorithms.  In _International Conference on Learning Representations_ , 2020.
  * Andrychowicz et al. [2016] M. Andrychowicz, M. Denil, S. 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.
  * Bengio [2000] Y. Bengio.  Gradient-Based Optimization of Hyperparameters.  _Neural computation_ , 12(8):1889–1900, 2000\.
  * Bengio et al. [1991] Y. Bengio, S. Bengio, and J. Cloutier.  _Learning a Synaptic Learning Rule_.  Université de Montréal, Département d’informatique et de recherche opérationnelle, 1991.
  * Chen et al. [2016] Y. Chen, M. W. Hoffman, S. G. Colmenarejo, M. Denil, T. P. Lillicrap, and N. de Freitas.  Learning to learn for Global Optimization of Black Box Functions.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Cutkosky [2019] A. Cutkosky.  Anytime Online-to-Batch, Optimism and Acceleration.  In _International Conference on Machine Learning_ , 2019.
  * Dekel et al. [2017] O. Dekel, A. Flajolet, N. Haghtalab, and P. Jaillet.  Online learning with a hint.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Denevi et al. [2019] G. Denevi, D. Stamos, C. Ciliberto, and M. Pontil.  Online-Within-Online Meta-Learning.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Duchi et al. [2011] J. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(61):2121–2159, 2011.
  * Fallah et al. [2020] A. Fallah, A. Mokhtari, and A. Ozdaglar.  On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms.  In _International Conference on Artificial Intelligence and Statistics_ , 2020.
  * Finn et al. [2017] C. Finn, P. Abbeel, and S. Levine.  Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks.  In _International Conference on Machine Learning_ , 2017.
  * Finn et al. [2019] C. Finn, A. Rajeswaran, S. Kakade, and S. Levine.  Online Meta-Learning.  In _International Conference on Machine Learning_ , 2019.
  * Flennerhag et al. [2019] S. Flennerhag, P. G. Moreno, N. D. Lawrence, and A. Damianou.  Transferring Knowledge across Learning Processes.  In _International Conference on Learning Representations_ , 2019.
  * Flennerhag et al. [2022] S. Flennerhag, Y. Schroecker, T. Zahavy, H. van Hasselt, D. Silver, and S. Singh.  Bootstrapped Meta-Learning.  In _International Conference on Learning Representations_ , 2022.
  * Hinton and Plaut [1987] G. E. Hinton and D. C. Plaut.  Using Fast Weights to Deblur Old Memories.  In _Cognitive Science Society_ , 1987.
  * Hochreiter et al. [2001] S. Hochreiter, A. S. Younger, and P. R. Conwell.  Learning To Learn Using Gradient Descent.  In _International Conference on Artificial Neural Networks_ , 2001\.
  * Hospedales et al. [2020] T. Hospedales, A. Antoniou, P. Micaelli, and A. Storkey.  Meta-Learning in Neural Networks: A Survey.  _arXiv preprint arXiv:2004.05439_ , 2020.
  * Joulani et al. [2017] 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.
  * Joulani et al. [2020] P. Joulani, A. Raj, A. Gyorgy, and C. Szepesvári.  A Simpler Approach to Accelerated Optimization: Iterative Averaging Meets Optimism.  In _International Conference on Machine Learning_ , 2020.
  * Khodak et al. [2019] M. Khodak, M.-F. F. Balcan, and A. S. Talwalkar.  Adaptive Gradient-Based Meta-Learning Methods.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Kirsch et al. [2019] L. Kirsch, S. van Steenkiste, and J. Schmidhuber.  Improving Generalization in Meta Reinforcement Learning Using Learned Objectives.  _arXiv preprint arXiv:1910.04098_ , 2019.
  * Luketina et al. [2022] J. Luketina, S. Flennerhag, Y. Schroecker, D. Abel, T. Zahavy, and S. Singh.  Meta-gradients in non-stationary environments.  In _ICLR Workshop on Agent Learning in Open-Endedness_ , 2022.
  * Maclaurin et al. [2015] D. Maclaurin, D. Duvenaud, and R. Adams.  Gradient-Based Hyperparameter Optimization Through Reversible Learning.  In _International conference on machine learning_ , pages 2113–2122. PMLR, 2015.
  * Mahmood et al. [2012] A. R. Mahmood, R. S. Sutton, T. Degris, and P. M. Pilarski.  Tuning-Free Step-Size Adaptation.  In _ICASSP_ , 2012.
  * McMahan [2017] H. B. McMahan.  A survey of algorithms and analysis for adaptive online learning.  _The Journal of Machine Learning Research_ , 18(1):3117–3166, 2017.
  * Mohri and Yang [2016] M. Mohri and S. Yang.  Accelerating Online Convex Optimization via Adaptive Prediction.  In _International Conference on Artificial Intelligence and Statistics_ , 2016.
  * Nesterov [1983] Y. E. Nesterov.  A method for solving the convex programming problem with convergence rate o (1/k^ 2).  In _Dokl. akad. nauk Sssr_ , volume 269, pages 543–547, 1983.
  * Nichol et al. [2018] A. Nichol, J. Achiam, and J. Schulman.  On First-Order Meta-Learning Algorithms.  _arXiv preprint ArXiv:1803.02999_ , 2018.
  * Oh et al. [2020] J. Oh, M. Hessel, W. M. Czarnecki, Z. Xu, H. P. van Hasselt, S. Singh, and D. Silver.  Discovering Reinforcement Learning Algorithms.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Polyak [1964] B. T. Polyak.  Some Methods of Speeding up the Convergence of Iteration Methods.  _USSR Computational Mathematics and Mathematical Physics_ , 4(5):1–17, 1964.
  * Rakhlin and Sridharan [2013] S. Rakhlin and K. Sridharan.  Optimization, Learning, and Games with Predictable Sequences.  In _Advances in Neural Information Processing Systems_ , 2013.
  * Real et al. [2020] E. Real, C. Liang, D. R. So, and Q. V. Le.  AutoML-Zero: Evolving Machine Learning Algorithms From Scratch.  In _International Conference on Machine Learning_ , 2020.
  * Schmidhuber [1987] J. Schmidhuber.  _Evolutionary Principles in Self-Referential Learning_.  PhD thesis, Technische Universität München, 1987.
  * van Erven and Koolen [2016] T. van Erven and W. M. Koolen.  MetaGrad: Multiple Learning Rates in Online Learning.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Vinyals et al. [2016] O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra.  Matching Networks for One Shot Learning.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Wang et al. [2022] H. Wang, Y. Wang, R. Sun, and B. Li.  Global convergence of maml and theory-inspired neural architecture search for few-shot learning.  In _Computer Vision and Pattern Recognition_ , 2022.
  * Wang and Abernethy [2018] J.-K. Wang and J. Abernethy.  Acceleration through Optimistic No-Regret Dynamics.  _arXiv preprint arXiv:1807.10455_ , 2018.
  * Wang et al. [2021] 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.11309_ , 2021.
  * Wang et al. [2016] J. X. Wang, Z. Kurth-Nelson, D. Tirumala, H. Soyer, J. Z. Leibo, R. Munos, C. Blundell, D. Kumaran, and M. Botvinick.  Learning to Reinforcement Learn.  In _Annual Meeting of the Cognitive Science Society_ , 2016.
  * Xu et al. [2018a] T. Xu, Q. Liu, L. Zhao, and J. Peng.  Learning to Explore with Meta-Policy Gradient.  In _International Conference on Machine Learning_ , 2018a.
  * Xu et al. [2018b] Z. Xu, H. P. van Hasselt, and D. Silver.  Meta-Gradient Reinforcement Learning.  In _Advances in Neural Information Processing Systems_ , 2018b.
  * Xu et al. [2020] Z. Xu, H. P. van Hasselt, M. Hessel, J. Oh, S. Singh, and D. Silver.  Meta-gradient reinforcement learning with an objective discovered online.  _Advances in Neural Information Processing Systems_ , 33:15254–15264, 2020.
  * Zahavy et al. [2020] T. Zahavy, Z. Xu, V. Veeriah, M. Hessel, J. 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.
  * Zinkevich [2003] M. Zinkevich.  Online Convex Programming and Generalized Infinitesimal Gradient Ascent.  In _International Conference on Machine Learning_ , 2003.

## Appendix

##  Appendix A Notation

Table 1: Notation Indices
---
$t$ |  Iteration index: $t\in\\{1,...,T\\}$.
$T$ |  Total number of iterations.
$[T]$ |  The set $\\{1,2,\ldots,T\\}$.
$i$ |  Component index: $x^{i}$ is the $i$th component of $x=(x^{1},\ldots,x^{n})$.
$\alpha_{a:b}$ |  Sum of weights: $\alpha_{a:b}=\sum_{s=a}^{b}\alpha_{s}$
$x_{a:b}$ |  Weighted sum: $x_{a:b}=\sum_{s=a}^{b}\alpha_{s}x_{s}$
$\bar{x}_{a:b}$ |  Weighted average: $\bar{x}_{a:b}=x_{a:b}/\alpha_{a:b}$
Parameters
$x^{*}\in\operatorname{\mathcal{X}}$ |  Minimiser of $f$.
$x_{t}\in\operatorname{\mathcal{X}}$ |  Parameter at time $t$
$\bar{x}_{t}\in\operatorname{\mathcal{X}}$ |  Moving average of $\\{x_{s}\\}_{s=1}^{t}$ under weights $\\{\alpha_{s}\\}_{s=1}^{t}$.
$\rho_{t}\in(0,\infty)$ |  Moving average coefficient $\alpha_{t}/\alpha_{1:t}$.
$w_{t}\in\operatorname{\mathcal{W}}$ |  Meta parameters
$w^{*}\in\operatorname{\mathcal{X}}$ |  $w\in\operatorname{\mathcal{W}}$ that retains regret with smallest norm $\|w\|$.
$\alpha_{t}\in(0,\infty)$ |  Weight coefficients
$\beta_{t}\in(0,\infty)$ |  Meta-learning rate
Maps
$f:\operatorname{\mathcal{X}}\to\operatorname{{\mathbb{R}}}$ |  Objective function
$\|\cdot\|:\operatorname{\mathcal{X}}\to\operatorname{{\mathbb{R}}}$ |  Norm on $\operatorname{\mathcal{X}}$.
$\|\cdot\|_{*}:\operatorname{\mathcal{X}}^{*}\to\operatorname{{\mathbb{R}}}$ |  Dual norm of $\|\cdot\|$.
$h_{t}:\operatorname{\mathcal{W}}\to\operatorname{{\mathbb{R}}}$ |  Online loss faced by the meta learner
$R^{x}(T)$ |  Regret of $\\{x_{t}\\}_{t=1}^{T}$ against $x^{*}$: $R^{x}(T)\coloneqq\sum_{t=1}^{T}\alpha_{t}\langle\nabla f(\bar{x}_{t}),x_{t}-x^{*}\rangle$.
$R^{w}(T)$ |  $R^{w}(T)\coloneqq\sum_{t=1}^{T}\alpha_{t}\langle\nabla f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle$.
$\varphi:\operatorname{{\mathbb{R}}}^{n}\times\operatorname{{\mathbb{R}}}^{m}\to\operatorname{{\mathbb{R}}}^{n}$ |  Generic update rule used in practice
$D\varphi(x,\cdot):\operatorname{{\mathbb{R}}}^{m}\\!\to\\!\operatorname{{\mathbb{R}}}^{n\times m}$ |  Jacobian of $\varphi$ w.r.t. its second argument, evaluated at $x\in\operatorname{{\mathbb{R}}}^{n}$.
$\varphi:\operatorname{\mathcal{X}}\times\operatorname{\mathcal{W}}\to\operatorname{\mathcal{X}}$ |  Update rule in convex setting
$D\varphi(x,\cdot):\operatorname{\mathcal{W}}\to\operatorname{{\mathbb{R}}}^{n\times m}$ |  Jacobian of $\varphi$ w.r.t. its second argument, evaluated at $x\in\operatorname{\mathcal{X}}$.
$B^{\mu}:\operatorname{{\mathbb{R}}}^{n}\\!\times\\!\operatorname{{\mathbb{R}}}^{n}\\!\to\\![0,\infty)$ |  Bregman divergence under $\mu:\operatorname{{\mathbb{R}}}^{n}\to\operatorname{{\mathbb{R}}}$.
$\mu:\operatorname{{\mathbb{R}}}^{n}\to\operatorname{{\mathbb{R}}}$ |  Convex distance generating function.

##  Appendix B Convex Quadratic Experiments

#### Loss function.

We consider the problem of minimising a convex quadratic loss functions
$f:\operatorname{{\mathbb{R}}}^{2}\to\operatorname{{\mathbb{R}}}$ of the form
$f(x)=x^{T}Qx$, where $Q$ is randomly sampled as follows. We sample a random
orthogonal matrix $U$ from the Haar distribution scipy.stats.ortho_group. We
construct a diagonal matrix of eigenvalues, ranked smallest to largest, with
$\lambda_{i}=i^{2}$. Hence, the first dimension has an eigenvalue $1$ and the
second dimension has eigenvalue $4$. The matrix $Q$ is given by
$U^{T}\operatorname{diag}(\lambda_{1},\ldots,\lambda_{n})U$.

#### Protocol.

Given that the solution is always $(0,0)$, this experiment revolves around
understanding how different algorithms deal with curvature. Given symmetry in
the solution and ill-conditioning, we fix the initialisation to $x_{0}=(4,4)$
for all sampled $Q$s and all algorithms and train for $100$ iterations. For
each $Q$ and each algorithm, we sweep over the learning rate, decay rate, and
the initialization of $w$ see Table 2. For each method, we then report the
results for the combination of hyper parameters that performed the best.

#### Results.

We report the learning curves for the best hyper-parameter choice for 5
randomly sampled problems in the top row of Figure 2 (columns 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 are relatively insensitive to
hyper-parameter choice, meta-learned improve for certain choices, but are
never worse than baselines.

Table 2: Hyper-parameter sweep on Convex Quadratics. All algorithms are tuned for learning rate and initialisation of $w$. Baselines are tuned for decay rate; meta-learned variant are tuned for the meta-learning rate. Learning rate | [.1, .3, .7, .9, 3., 5.]
---|---
$w$ init scale | [0., 0.3, 1., 3., 10., 30.]
Decay rate / Meta-learning rate | [0.001, 0.003, 0.01, .03, .1, .3, 1., 3., 10., 30.]

##  Appendix C Imagenet Experiments

#### Protocol.

We train a 50-layer ResNet following the Haiku example, available at
https://github.com/deepmind/dm-haiku/blob/main/examples/imagenet. We modify
the default setting to run with SGD. We compare default SGD to variants that
meta-learn an element-wise learning rate online, i.e. $(x,w)\mapsto
w\odot\nabla f(x)$. For each variant, we sweep over the learning rate (for
SGD) or meta-learning rate. We report results for the best hyper-parameter
over three independent runs.

#### 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_{t+1}=w_{t}-\beta\nabla h_{t}(w_{t})$, where
$h_{t}=f(x_{t}+w_{t}\odot\nabla f(x_{t}))$. Because the update rule is linear
in $w$, we can compute the meta-gradient analytically:

$\nabla h_{t}(w_{t})=\nabla_{w}f(x+\varphi(x,w))=D\varphi(x,w)^{T}\nabla
f(x^{\prime})=\nabla f(x)\odot\nabla f(x^{\prime}),$

where $x^{\prime}=x+\varphi(x,w)$. Hence, we can compute the meta-updates in
Algorithm 1 manually as $w_{t+1}=\max\\{w_{t}-\beta\nabla f(x_{t})\odot\nabla
f(x_{t+1}),0.\\}$, where we introduce the $\max$ operator on an element-wise
basis to avoid negative learning rates. Empirically, this was important to
stabilize training.

#### Optimistic meta-learning.

For optimistic meta-learning, we proceed much in the same way, but include a
gradient prediction $\tilde{g}_{t+1}$. For our prediction, we use the previous
gradient, $\nabla f(x_{t+1})$, as our prediction. Following Eq. 11, this
yields meta-updates of the form

$w_{t+1}=\max\,\Big{\\{}w_{t}-\beta\nabla f(x_{t+1})\odot\left(\nabla
f(x_{t+1})+\nabla f(x_{t})\right)-\nabla f(x_{t})\odot\nabla
f(x_{t}),0.\Big{\\}}.$

#### Results.

We report Top-1 accuracy on the held-out test set as a 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 a significant acceleration as well as
improved final performance, increasing the mean final top-1 accuracy from
$\leavevmode\nobreak\ 72\%$ to $\leavevmode\nobreak\ 75\%$.

Table 3: Hyper-parameter sweep on Imagenet. (Meta-)learning rate | [0.001, 0.01, 0.02, 0.05, 0.1]
---|---

##  Appendix D Proofs

This section provides complete proofs. We restate the results for convenience.

Lemma 1. _Given $f$, $\\{\alpha_{t}\\}_{t=1}^{T}$, and
$\\{x_{t}\\}_{t=1}^{T}$, if $\varphi$ preserves regret, then_

$R^{x}(T)=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),x_{t}-x^{*}\rangle\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{t}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle=R^{w}(T).$

###### Proof.

Starting from $R^{x}$ in Eq. 8, if the update rule preserves regret, there
exists $w^{*}\in\operatorname{\mathcal{W}}$ for which

$\displaystyle R^{x}(T)=$ $\displaystyle\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w_{t})-x^{*}\rangle$
$\displaystyle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle+\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle=R^{w}(T),$

since $w^{*}$ is such that $\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w^{*})-x^{*}\rangle\leq 0$. ∎

Theorem 3. _Let $\varphi$ preserve regret and assume Algorithm 2 satisfy the
assumptions in Section 2. Then_

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$
$\displaystyle\frac{1}{\alpha_{1:T}}\left(\frac{\|w^{*}\|^{2}}{\beta}+\sum_{t=1}^{T}\frac{\lambda\beta\alpha^{2}_{t}}{2}\|\nabla
f(\bar{x}_{t})\|_{*}^{2}\right.$
$\displaystyle\left.\vphantom{\sum_{t=1}^{T}}-\frac{\alpha_{t}}{2L}\|\nabla
f(\bar{x}_{t})-\nabla f(x^{*})\|_{*}^{2}-\frac{\alpha_{1:t-1}}{2L}\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|_{*}^{2}\right).$

_If $x^{*}$ is a global minimiser of $f$, setting $\alpha_{t}=1$ and
$\beta=\frac{1}{\lambda L}$ yields $f(\bar{x}_{T})-f(x^{*})\leq\frac{\lambda
L\operatorname{diam}(\operatorname{\mathcal{W}})}{T}$._

###### Proof.

Since $\varphi$ preserves regret, by Lemma 1, the regret term $R^{x}(T)$ in
Eq. 7 is upper bounded by $R^{w}(T)$. We therefore have

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$ (12)
$\displaystyle\frac{1}{\alpha_{1:T}}\left(R^{w}(T)-\frac{\alpha_{t}}{2L}\|\nabla
f(\bar{x}_{t})-\nabla f(x^{*})\|_{*}^{2}-\frac{\alpha_{1:t-1}}{2L}\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\|_{*}^{2}\right).$

Next, we need to upper-bound $R^{w}(T)$. Since,
$R^{w}(T)=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle$,
the regret of $\\{w_{t}\\}_{t=1}^{T}$ is defined under loss functions
$h_{t}:\operatorname{\mathcal{W}}\to\operatorname{{\mathbb{R}}}$ given by
$h_{t}=\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w))\rangle$. By assumption of convexity
in $\varphi$, each $h_{t}$ is convex in $w$. Hence, the regret under
$\\{\alpha_{t}h_{t}\\}_{t=1}^{T}$ can be upper bounded by the regret under the
linear losses $\\{\alpha_{t}\langle\nabla
h_{t}(w_{t}),\cdot\rangle\\}_{t=1}^{T}$. These linear losses correspond to the
losses used in the meta-update in Eq. 3. Since the meta-update is an instance
of FTRL, we may upper-bound $R^{w}(T)$ by Eq. 6 with each $\tilde{g}_{t}=0$.
Putting this together along with smoothness of $\varphi$,

$\displaystyle R^{x}(T)$ $\displaystyle\leq R^{w}(T)$
$\displaystyle=\sum_{t=1}^{T}\alpha_{t}\langle\nabla
f(\bar{x}_{T}),\varphi(\bar{x}_{t-1},w_{t})-\varphi(\bar{x}_{t-1},w^{*})\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\alpha_{t}\langle\nabla
h_{t}(w_{t}),w_{t}-w^{*}\rangle$
$\displaystyle\leq\frac{\|w^{*}\|^{2}}{\beta}+\frac{\beta}{2}\sum_{t=1}^{T}\alpha^{2}_{t}\|\nabla
h_{t}(w_{t})\|_{*}^{2}$
$\displaystyle=\frac{\|w^{*}\|^{2}}{\beta}+\frac{\beta}{2}\sum_{t=1}^{T}\alpha^{2}_{t}\|D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})\|_{*}^{2}$
$\displaystyle\leq\frac{\|w^{*}\|^{2}}{\beta}+\frac{\lambda\beta}{2}\sum_{t=1}^{T}\alpha^{2}_{t}\|\nabla
f(\bar{x}_{t})\|_{*}^{2}.$ (13)

Putting Eq. 12 and Eq. 13 together gives the stated bound. Next, if $x^{*}$ is
the global optimiser, $\nabla f(x^{*})=0$ by first-order condition. Setting
$\beta=1/(L\lambda)$ and $\alpha_{t}=1$ means the first two norm terms in the
summation cancel. The final norm term in the summation is negative and can be
ignored. We are left with $f(\bar{x}_{T})-f(x^{*})\leq\frac{\lambda
L\|w^{*}\|^{2}}{T}\leq\frac{\lambda
L\operatorname{diam}(\operatorname{\mathcal{W}})}{T}$. ∎

Corollary 1. _Let each
$\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla f(\bar{x}_{t})$.
Assume that $\varphi$ satisfies_

$\left\|D\varphi(x^{\prime},w)^{T}\nabla
f(x)-D\varphi(x^{\prime\prime},w^{\prime})^{T}\nabla
f(x^{\prime})\right\|_{*}^{2}\leq\tilde{\lambda}\left\|\nabla
f(x^{\prime})-\nabla f(x)\right\|_{*}^{2}$

_for all $x^{\prime\prime},x^{\prime},x\in\operatorname{\mathcal{X}}$ and
$w,w^{\prime}\in\operatorname{\mathcal{W}}$, for some $\tilde{\lambda}>0$. If
each $\alpha_{t}=t$ and $\beta_{t}=\frac{t-1}{2t\tilde{\lambda}L}$, then
$f(\bar{x}_{T})-f(x^{*})\leq\frac{4\tilde{\lambda}L\operatorname{diam}(\operatorname{\mathcal{W}})}{T^{2}-1}$._

###### Proof.

Plugging in the choice of $\tilde{g}_{t}$ and using that

$\left\|D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-D\varphi(x_{t-2},w_{t-1})^{T}\nabla
f(\bar{x}_{t-1})\right\|_{*}^{2}\leq\tilde{\lambda}\left\|\nabla
f(\bar{x}_{t-1})-\nabla f(\bar{x}_{t})\right\|_{*}^{2},$

the bound in Theorem 4 becomes

$\displaystyle f(\bar{x}_{T})-f(x^{*})\leq$
$\displaystyle\frac{1}{\alpha_{1:T}}\left(\frac{\|w^{*}\|^{2}}{\beta_{T}}+\frac{1}{2}\sum_{t=1}^{T}\left(\tilde{\lambda}\alpha^{2}_{t}\beta_{t}-\frac{\alpha_{1:t-1}}{L}\right)\|\nabla
f(\bar{x}_{t})-\nabla f(\bar{x}_{t-1})\|_{*}^{2}\right),$

where we drop the negative terms $\|\nabla f(\bar{x}_{t})-\nabla
f(x^{*})\|_{*}^{2}$. Setting $\alpha_{t}=t$ yields
$\alpha_{1:t-1}=\frac{(t-1)t}{2}$, while setting
$\beta_{t}=\frac{t-1}{2t\tilde{\lambda}L}$ means
$\tilde{\lambda}\alpha_{t}^{2}\beta_{t}=\frac{(t-1)t}{2L}$. Hence,
$\tilde{\lambda}\alpha_{t}^{2}\beta_{t}-\alpha_{1:t-1}/L$ cancels and we get

$f(\bar{x}_{T})-f(x^{*})\leq\frac{\|w^{*}\|^{2}}{\beta_{T}\alpha_{1:T}}=\frac{4\|w^{*}\|^{2}\tilde{\lambda}L}{(T-1)(T+1)}\leq\frac{4\tilde{\lambda}L\operatorname{diam}(\operatorname{\mathcal{W}})}{(T-1)(T+1)}=\frac{4\tilde{\lambda}L\operatorname{diam}(\operatorname{\mathcal{W}})}{T^{2}-1}.$

∎

Corollary 2. _Let each
$\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\tilde{y}_{t+1}$, for some
$\tilde{y}_{t+1}\in\operatorname{{\mathbb{R}}}^{n}$. If each $\tilde{y}_{t+1}$
is a better predictor of the next gradient than $\nabla f(\bar{x}_{t-1})$, in
the sense that_

$\|D\varphi(\bar{x}_{t-2},w_{t-1})^{T}\tilde{y}_{t}-D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})\|_{*}\leq\tilde{\lambda}\|\nabla f(\bar{x}_{t})-\nabla
f(\bar{x}_{t-1})\|_{*},$

_then Algorithm 4 guarantees convergence at a rate
$O(\tilde{\lambda}/T^{2})$._

###### Proof.

The proof follows the same argument as Corollary 1. ∎

##  Appendix E BMG

_Errata: this was incorrectly referred to as Appendix F in our original
submission._

In this section, we provide a more comprehensive reduction of BMG to AO-FTRL.
First, we provide a more general definition of BMG. Let
$\mu:\operatorname{\mathcal{X}}\to\operatorname{{\mathbb{R}}}$ be a convex
distance generating function and define the Bregman Divergence
$B^{\mu}:\operatorname{{\mathbb{R}}}^{n}\times\operatorname{{\mathbb{R}}}^{n}\to\operatorname{{\mathbb{R}}}$
by

$B^{\mu}_{z}(x)=\mu(x)-\mu(z)-\langle\nabla\mu(z),x-z\rangle.$

Given initial condition $(x_{0},w_{1})$, the BMG updates proceed according to

$\displaystyle x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$ $\displaystyle
w_{t+1}=w_{t}-\beta_{t}\nabla d_{t}(w_{t}),$ (14)

where $d_{t}:\operatorname{{\mathbb{R}}}^{n}\to\operatorname{{\mathbb{R}}}$ is
defined by $d_{t}(w)=B^{\mu}_{z_{t}}(x_{t-1}+\varphi(x_{t-1},w_{t}))$, where
each $z_{t}\in\operatorname{{\mathbb{R}}}^{n}$ is referred to as a target. See
Algorithm 5 for an algorithmic summary. A bootstrapped target uses the meta-
learner’s most recent update, $x_{t}$, to compute the target,
$z_{t}=x_{t}+y_{t}$ for some tangent vector
$y_{t}\in\operatorname{{\mathbb{R}}}^{n}$. This tangent vector represents a
form of optimism, and provides a signal to the meta-learner as to what would
have been a more efficient update. In particular, the author’s consider using
the meta-learned update rule to construct $y_{t}$;
$y_{t}=\varphi(x_{t},w_{t})-\nabla f(x_{t}\varphi(x_{t},w-t))$. Note that
$x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$, and hence this tangent vector is
obtained by applying the update rule again, but now to $x_{t}$. For this
tangent to represent an improvement, it must be _assumed that $w_{t}$ is a
good parameterisation_. Hence, bootstrapping represents a form of optimism. To
see how BMG relates to Algorithm 4, and in particular, Eq. 10, expand Eq. 14
to get

$w_{t+1}=w_{t}-\beta_{t}D\varphi(x_{t-1},w_{t})^{T}\left(\nabla\mu(x_{t})-\nabla\mu(z_{t})\right).$
(15)

input : Weights $\\{\rho_{t}\\}^{T}_{t=1},\\{\beta_{t}\\}^{T}_{t=1}$

input : Update rule $\varphi$

input : Matching function $B^{\mu}$

input : Target oracle

input : Initialisation $(x_{0},w_{1})$

for   _$t=1,2,\ldots,T$ :_

$x_{t}=x_{t-1}+\varphi(x_{t-1},w_{t})$

Query $z_{t}$ from target oracle

$d_{t}:w\mapsto B^{\mu}_{z_{t}}(x_{t-1}+\varphi(x_{t-1},w))$

$w_{t+1}=w_{t}-\beta_{t}\nabla d_{t}(w_{t})$

return _$x_{T}$_

Algorithm 5 BMG in practice (general version).

In contrast, AO-FTRL reduces to a slightly different type of update.

######  Lemma 2.

Consider Algorithm 4. Given online losses
$h_{t}:\operatorname{\mathcal{W}}\to\operatorname{{\mathbb{R}}}$ defined by
$\\{\langle D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t}),\cdot\rangle\\}_{t=1}^{T}$ and hint functions
$\\{\langle\tilde{g}_{t},\cdot,\\}\rangle_{t=1}^{T}$, with each
$\tilde{g}_{t}\in\operatorname{{\mathbb{R}}}^{m}$. If
$\|\cdot\|=(1/2)\|\cdot\|_{2}$, an interior solution to Eq. 10 is given by

$w_{t+1}=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right).$

###### Proof.

By direct computation:

$\displaystyle w_{t+1}$ $\displaystyle=\operatorname*{arg\,min\
}_{w\in\operatorname{\mathcal{W}}}\left(\alpha_{t+1}\langle\tilde{g}_{t+1},w\rangle+\sum_{s=1}^{t}\alpha_{s}\langle
D\varphi(\bar{x}_{s-1},w_{s})^{T}\nabla
f(\bar{x}_{s}),w\rangle+\frac{1}{2\beta_{t}}\|w\|_{2}^{2}\right)$
$\displaystyle=-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\sum_{s=1}^{t}\alpha_{t}D\varphi(\bar{x}_{s-1},w_{s})^{T}\nabla
f(\bar{x}_{s}))\right)$
$\displaystyle=-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})+\left(\sum_{s=1}^{t-1}\alpha_{t}D\varphi(\bar{x}_{s-1},w_{s})^{T}\nabla
f(\bar{x}_{s}))\right)\right)$
$\displaystyle=-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right)$
$\displaystyle\quad-\beta_{t}\left(\alpha_{t}\tilde{g}_{t}+\sum_{s=1}^{t-1}\alpha_{t}D\varphi(\bar{x}_{s-1},w_{s})^{T}\nabla
f(\bar{x}_{s}))\right)$
$\displaystyle=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right).$

∎

AO-FTRL includes a decay rate $\beta_{t}/\beta_{t-1}$; this decay rate can be
removed by instead using optimistic online mirror descent [Rakhlin and
Sridharan, 2013, Joulani et al., 2017]—to simplify the exposition we consider
only FTRL-based algorithms in this paper. An immediate implication of Lemma 2
is the error-corrected version of BMG.

######  Corollary 3.

Setting $\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}\tilde{g}_{t+1}$ for
some $\tilde{y}_{t+1}\in\operatorname{{\mathbb{R}}}^{n}$ yields an error-
corrected version of the BMG meta-update in Eq. 14. Specifically, the meta-
updates in Lemma 2 becomes

$w_{t+1}=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\underbrace{\beta_{t}D\varphi(\bar{x}_{t-1},w_{t})^{T}(\alpha_{t+1}\tilde{y}_{t+1}+\alpha_{t}\nabla
f(\bar{x}_{t}))}_{\text{BML
update}}+\underbrace{\beta_{t}\alpha_{t}D\varphi(\bar{x}_{t-2},w_{t-1})^{T}\tilde{y}_{t}}_{\text{FTRL
error correction}}.$

###### Proof.

Follows immediately by substituting for each $\tilde{g}_{t+1}$ in Lemma 2. ∎

To illustrate this connection, Let $\mu=f$. In this case, the BMG update reads
$w_{t+1}=w_{t}-\beta_{t}D\varphi({x}_{t-1},w_{t})^{T}(\nabla f(z_{t})-\nabla
f(x_{t}))$. The equivalent update in the convex optimisation setting (i.e.
Algorithm 4) is obtained by setting $\tilde{y}_{t+1}=\nabla f(z_{t})$, in
which case Corollary 3 yields

$w_{t+1}=\frac{\beta_{t+1}}{\beta_{t}}w_{t}-\beta_{t}D\varphi(\bar{x}_{t-1},w_{t})^{T}(\alpha_{t+1}\nabla
f(z_{t})-\alpha_{t}\nabla f(\bar{x}_{t}))+\xi_{t},$

where $\xi_{t}=\beta_{t}\alpha_{t}D\varphi(\bar{x}_{t-2},w_{t-1})^{T}\nabla
f(\bar{x}_{t}-1)$ denotes the error correction term we pick up through AO-
FTRL. Since Algorithm 5 does not average its iterates—while Algorithm 4
does—we see that these updates (ignoring $\xi_{t}$) are identical up to scalar
coefficients (that can be controlled for by scaling each $\beta_{t}$ and each
$\tilde{g}_{t+1}$ accordingly).

More generally, the mapping from targets in BMG and hints in AO-FTRL takes on
a more complicated pattern. Our next results show that we can always map one
into the other. To show this, we need to assume a certain recursion. It is
important to notice however that at each iteration introduces an unconstrained
variable and hence the assumption on the recursion is without loss of
generality (as the free variable can override it).

######  Theorem 5.

Targets in Algorithm 5 and hints in algorithm 4 commute in the following
sense. BMG $\rightarrow$ AO-FTRL. Let BMG targets $\\{z_{t}\\}_{t=1}^{T}$ by
given. A sequence of hints $\\{\tilde{g}\\}_{t=1}^{T}$ can be constructed
recursively by

$\alpha_{t+1}\tilde{g}_{t+1}=D\varphi(\bar{x}_{t-1},w_{t})^{T}(\nabla\mu(\bar{x}_{t})-\nabla\mu(z_{t})-\alpha_{t}\nabla
f(\bar{x}_{t}))+\alpha_{t}\tilde{g}_{t},\qquad t\in[T],$ (16)

so that interior updates for Algorithm 4 are given by

$w_{t+1}=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}\left(\nabla\mu(z_{t})-\nabla\mu(\bar{x}_{t})\right).$

AO-FTRL $\rightarrow$ BMG. Conversely, assume a sequence
$\\{\tilde{y}_{t}\\}_{t=1}^{T}$ are given, each
$\tilde{y}_{t}\in\operatorname{{\mathbb{R}}}^{n}$. If $\mu$ strictly convex, a
sequence of BMG targets $\\{z_{t}\\}_{t=1}^{T}$ can be constructed recursively
by

$z_{t}=\nabla\mu^{-1}\left(\nabla\mu(x_{t})-(\alpha_{t+1}\tilde{y}_{t+1}+\alpha_{t}\nabla
f(x_{t}))\right)\qquad t\in[T],$

so that BMG updates in Eq. 14 are given by

$w_{t+1}=w_{t}-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right),$

where each $\tilde{g}_{t+1}$ is the BMG-induced hint function, given by

$\alpha_{t+1}\tilde{g}_{t+1}=\alpha_{t+1}D\varphi(x_{t-1},w_{t})^{T}\tilde{y}_{t+1}+\alpha_{t}\tilde{g}_{t}.$

###### Proof.

First, consider BMG $\rightarrow$ AO-FTRL. First note that $\tilde{g}_{1}$ is
never used and can thus be chosen arbitrarily—here, we set $\tilde{g}_{1}=0$.
For $w_{2}$, Lemma 2 therefore gives the interior update

$w_{2}=\frac{\beta_{2}}{\beta_{1}}w_{1}-\beta_{1}(\alpha_{2}\tilde{g}_{2}+\alpha_{1}D\varphi(\bar{x}_{0},w_{1})^{T}\nabla
f(\bar{x}_{1})).$

Since the formulate for $\tilde{g}_{2}$ in Eq. 16 only depends on quantities
with iteration index $t=0,1$, we may set
$\alpha_{2}\tilde{g}_{t}=D\varphi(\bar{x}_{0},w_{1})^{T}(\nabla\mu(\bar{x}_{1})-\nabla\mu(z_{t})-\alpha_{t}\nabla
f(\bar{x}_{1}))$. This gives the update

$w_{2}=\frac{\beta_{2}}{\beta_{1}}w_{1}-\beta_{1}D\varphi(\bar{x}_{0},w_{1})^{T}(\nabla\mu(\bar{x}_{1})-\nabla\mu(z_{1})).$

Now assume the recursion holds up to time $t$. As before, we may choose
$\alpha_{t+1}\tilde{g}_{t+1}$ according to the formula in Eq. 16 since all
quantities on the right-hand side depend on quantities computed at iteration
$t$ or $t-1$. Subtituting this into Lemma 2, we have

$\displaystyle w_{t+1}$
$\displaystyle=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}\left(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right)$
$\displaystyle=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}\left(D\varphi(\bar{x}_{t-1},w_{t})^{T}(\nabla\mu(\bar{x}_{t})-\nabla\mu(z_{t})-\alpha_{t}\nabla
f(\bar{x}_{t}))+\alpha_{t}\tilde{g}_{t}\right.$
$\displaystyle\quad\left.+\alpha_{t}(D\varphi(\bar{x}_{t-1},w_{t})^{T}\nabla
f(\bar{x}_{t})-\tilde{g}_{t})\right)$
$\displaystyle=\frac{\beta_{t}}{\beta_{t-1}}w_{t}-\beta_{t}D\varphi(\bar{x}_{t-1},w_{t})^{T}(\nabla\mu(\bar{x}_{t})-\nabla\mu(z_{t})).$

AO-FTRL $\rightarrow$ BMG. The proof in the other direction follows similarly.
First, note that for $\mu$ strictly convex, $\nabla\mu$ is invertible. Then,
$z_{1}=\nabla\mu^{-1}(\nabla\mu(x_{1})-(\alpha_{2}\tilde{y}_{2}+\alpha_{1}\nabla
f(x_{1})))$. This target is permissible since $x_{1}$ is already computed and
$\\{\tilde{y}_{t}\\}_{t=1}^{T}$ is given. Substituting this into the BMG meta-
update in Eq. 14, we find

$\displaystyle w_{2}$
$\displaystyle=w_{1}-\beta_{1}D\varphi(x_{0},w_{1})^{T}(\nabla\mu(x_{1})-\nabla\mu(\nabla\mu^{-1}(\nabla\mu(x_{1})-(\alpha_{2}\tilde{y}_{2}+\alpha_{1}\nabla
f(x_{1})))))$
$\displaystyle=w_{1}-\beta_{1}D\varphi(x_{0},w_{1})^{T}(\alpha_{2}\tilde{y}_{2}+\alpha_{1}\nabla
f(x_{1}))$
$\displaystyle=w_{1}-\beta_{1}\left(\alpha_{2}\tilde{g}_{2}+\alpha_{1}(D\varphi(\bar{x}_{0},w_{1})^{T}\nabla
f(\bar{x}_{1})-\tilde{g}_{1})\right),$

where the last line uses that $\tilde{g}_{2}$ is defined by
$\alpha_{2}\tilde{g}_{2}-\alpha_{1}\tilde{g}_{1}=D\varphi(\bar{x}_{0},w_{1})^{T}\tilde{y}_{2}$
and $\tilde{g}_{1}$ is arbitrary. Again, assume the recursion holds to time
$t$. We then have

$\displaystyle w_{t+1}$
$\displaystyle=w_{t}-\beta_{t}D\varphi(x_{t-1},w_{t})^{T}\left(\nabla\mu(x_{t})-\nabla\mu(z_{t})\right)$
$\displaystyle=w_{t}-\beta_{t}D\varphi(x_{t-1},w_{t})^{T}(\nabla\mu(x_{t})$
$\displaystyle\quad-\nabla\mu(\nabla\mu^{-1}(\nabla\mu(x_{t})-(\alpha_{t+1}\tilde{y}_{t+1}+\alpha_{t}\nabla
f(x_{t})))))$
$\displaystyle=w_{t}-\beta_{t}D\varphi(x_{t-1},w_{t})^{T}(\alpha_{t+1}\tilde{y}_{t+1}+\alpha_{t}\nabla
f(x_{t}))$
$\displaystyle=w_{t}-\beta_{t}(\alpha_{t+1}\tilde{g}_{t+1}+\alpha_{t}(D\varphi(x_{t-1},w_{t})^{T}\nabla
f(x_{t})-\tilde{g}_{t})).$

∎


$\\{i,j\\}$ is absent in $\mathcal{G}(\mathcal{M}^{i})$, we further have,

$D_{\mathcal{M}^{i}}(\ell,i)>2.$ (A.51)

This implies $N(\ell)$ does not change in $\mathcal{M}$ and $\mathcal{M}^{i}$.
Hence,

$W_{\ell}(\mathcal{M})=W_{\ell}(\mathcal{M}^{i}).$

Next we show that if $D_{\mathcal{M}}(\ell,i)\leq 1$ we have
$D_{\mathcal{M}^{j}}(\ell,i)\geq 2$ and $D_{\mathcal{M}^{ij}}(\ell,i)\geq 2$.
Suppose not, let $D_{\mathcal{M}^{j}}(\ell,i)\leq 1$. If $j=\ell$, then
clearly this is false as the edge $\\{i,j\\}$ edge is absent in
$\mathcal{G}(\mathcal{M}^{j})$. If $j\neq\ell$, then by (A.49) and (A.50), we
get,

$D_{\mathcal{M}^{j}}(\ell,i)\geq 2.$

This is a contradiction. Further, if $D_{\mathcal{M}^{ij}}(\ell,i)\leq 1$ and
$j=\ell$, then this is similarly false as the edge $\\{i,j\\}$ edge is absent
in $\mathcal{G}(\mathcal{M}^{ij})$. If $j\neq\ell$, then by (A.49) and (A.51),
we get,

$D_{\mathcal{M}^{ij}}(\ell,i)\geq 2.$

Again we get a contradiction. Thus if $D_{\mathcal{M}^{j}}(\ell,i)\geq 2$ and
$D_{\mathcal{M}^{ij}}(\ell,i)\geq 2$, $N(\ell)$ is same in $\mathcal{M}^{j}$
and $\mathcal{M}^{ij}$. Hence,

$W_{\ell}(\mathcal{M}^{j})=W_{\ell}(\mathcal{M}^{ij}).$

This implies if $D_{\mathcal{M}}(\ell,j)\leq 1$, then (A.48) holds. Similarly
if $D_{\mathcal{M}^{i}}(\ell,j)\leq 1$ or $D_{\mathcal{M}^{j}}(\ell,j)\leq 1$
or $D_{\mathcal{M}^{ij}}(\ell,j)\leq 1$, then (A.48) holds. Now if
$D_{\mathcal{M}}(\ell,j),D_{\mathcal{M}^{i}}(\ell,j),D_{\mathcal{M}^{j}}(\ell,j),D_{\mathcal{M}^{ij}}(\ell,j)>1$,
then $N(\ell)$ does not change in $\mathcal{M}$ and $\mathcal{M}^{j}$ implying

$W_{\ell}(\mathcal{M})=W_{\ell}(\mathcal{M}^{j}).$

Also $N(\ell)$ does not change in $\mathcal{M}^{i}$ and $\mathcal{M}^{ij}$
implying

$W_{\ell}(\mathcal{M}^{i})=W_{\ell}(\mathcal{M}^{ij}).$

This implies the lemma. ∎

###  A.5 Proof of Lemma 4.5

To reduce notation we write $f_{X,Y}(\cdot,\cdot)$, $f_{X}(\cdot)$,
$f_{Y}(\cdot)$ and $F_{Y}(\cdot)$ to mean $f_{X,Y}^{(n)}(\cdot)$,
$f_{X}^{(n)}(\cdot)$, $f_{Y}^{(n)}(\cdot)$ and $F_{Y}^{(n)}(\cdot)$
respectively. We will write $(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$ to mean the
random variables $(X_{n,1},Y_{n,1}),\ldots,(X_{n,n},Y_{n,n})\sim
f_{X,Y}^{(n)}$ from the triangular array. We will also write $\mathbf{X}$ to
mean $(X_{1},\dots,X_{n})$. It is useful to note some properties of $g(y|x)$
which we will use throughout the proof.

  * a)

$\int g(y|x)dy=1\quad\text{and}\quad\int g(y|x)f_{X}(x)dx=f_{Y}(y).$ (A.52)

In this sense, $g(y|x)$ is like a conditional density, although it can take
negative values.

  * b)

Recalling the definition of $g$, we write

$G(y|x)=\int_{-\infty}^{y}g(t|x)dt=\tfrac{1}{p}f_{X,Y}(y|x)+(1-\tfrac{1}{p})F_{Y}(y);\quad\quad\int
G(y|x)f_{X}(x)dx=F_{Y}(y).$ (A.53)

  * c)

For any $y,\,x_{1},\,x_{2}$, (A1) implies there exist $\eta\in(0,1],$
$\theta>1$ and $C>0$ such that

$\begin{split}\left|G(y|x_{1})-G(y|x_{2})\right|&\leq(1+L_{1}^{(n)}(x_{1},y)+L_{2}^{(n)}(x_{2},y))\left|x_{1}-x_{2}\right|^{\eta}\\\
\underset{n\to\infty}{\lim\sup}\int&(L_{1}^{(n)}(x,y))^{\theta}f_{X}(x)f_{Y}(y)dy\leq
C.\end{split}$ (A.54)

We will prove the three parts of Lemma 4.5 as Lemmas A.2, A.3 and A.4
presented below.

######  Lemma A.2.

$\left|T_{1}-1\right|\lesssim\left(n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\dfrac{(\log
n)^{2}}{n}\right)^{\left(\tfrac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\tfrac{\eta\gamma}{\gamma+1}\right)}\right)\mathbbm{1}(\xi(f_{X,Y}^{(n)})>0)$.

####  A.5.1 Proof of Lemma A.2

$T_{1}$ involves two contributions from $f_{Y}(y)$ and one from $g(y|x)$. Thus

$\begin{split}T_{1}&=\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})f_{Y}(y_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}\\\
&+\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})g(y_{k}|x_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}\\\
&+\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})f_{Y}(y_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}.\end{split}$
(A.55)

Now for the first term of $T_{1}$, we use Fubini’s theorem to write

$\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})f_{Y}(y_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})(g(y_{j}|x_{1})+g(y_{j}|x_{j})-g(y_{j}|x_{1}))f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle\hskip 30.0ptf_{Y}(y_{k})f_{Y}(y_{1})dy_{1}dy_{k}dy_{j}$
$\displaystyle=:$ $\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})\int
g(y|x_{1})f_{X}(x_{1})dx_{1}f_{Y}(y_{1})f_{Y}(y_{k})dydy_{1}dy_{k}+E_{n}$
$\displaystyle=$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})f_{Y}(y)f_{Y}(y_{1})f_{Y}(y_{k})dydy_{1}dy_{k}+E_{n}=\dfrac{1}{3}+E_{n},$

where we use the fact that $\int g(y|x)f_{X}(x)dx=f_{Y}(y)$ from (A.52). The
remainder term is

$\displaystyle E_{n}=$ $\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\int(g(y_{j}|x_{j})-g(y_{j}|x_{1}))f_{Y}(y_{1})f_{Y}(y_{k})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=$ $\displaystyle\int\int\limits_{y_{k}}^{\infty}\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\int\limits_{y_{k}}^{\infty}(g(y_{j}|x_{j})-g(y_{j}|x_{1}))f_{Y}(y_{k})f_{Y}(y_{1})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=$ $\displaystyle\int\int\limits_{y_{k}}^{\infty}\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)[G_{Y|X_{1}=x_{1}}(y_{k})-G_{Y|X_{j}=x_{j}}(y_{k})]f_{Y}(y_{k})f_{Y}(y_{1})dy_{1}dy_{k}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle\leq$
$\displaystyle\int\int\limits_{y_{k}}^{\infty}\int\left|G_{Y|X_{1}}(y_{k})-G_{Y|X_{N(1)}}(y_{k})\right|f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}f_{Y}(y_{k})f_{Y}(y_{1})dy_{1}dy_{k}$
$\displaystyle\leq$
$\displaystyle\int\int\min\\{(1+L_{1}^{(n)}(x_{1},y_{k})+L_{2}^{(n)}(x_{N(1)},y))|x_{1}-x_{N(1)}|^{\eta},1\\}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}(1-F_{Y}(y_{k}))f_{Y}(y_{k})dy_{k}$
$\displaystyle\lesssim$ $\displaystyle\,\mathbb{P}(|X_{1}-X_{N(1)}|\geq
1)+\left\\{\mathbb{E}\left(1+(L_{1}^{(n)}(X_{1},Y_{k}))^{\theta}+(L_{2}^{(n)}(X_{1},Y_{k}))^{\theta}\right)\right\\}^{\frac{1}{\theta}}$
$\displaystyle\left\\{\mathbb{E}|X_{1}-X_{N(1)}|^{\frac{\theta\eta}{\theta-1}}\mathbbm{1}(|X_{1}-X_{N(1)}|\leq
1)\right\\}^{\frac{\theta-1}{\theta}}$ $\displaystyle\lesssim$
$\displaystyle\,\,n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\frac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)},$
(A.56)

where we use (A.54) in the second last line, and Lemma A.5 in the last line.
By analogous calculation, the second and third terms in $T_{1}$ can be written
as

$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})f_{Y}(y)f_{Y}(y_{1})f_{Y}(y_{k})dydy_{1}dy_{k}+O\left(\left(\frac{(\log
n)^{2}}{n}\right)^{\left(\tfrac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\tfrac{\eta\gamma}{\gamma+1}\right)}\right)$
$\displaystyle=$
$\displaystyle\dfrac{1}{3}+O\left(n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\frac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)}\right).$

Finally, when $\xi(f_{X,Y}^{(n)})=0$ $X_{i}$ and $Y_{i}$ are independent, and
hence $g(y|x)=f_{Y}(y)$ for all $x$. It can be checked that in this case
$E_{n}=0$ and similarly the other error terms are all zero. This finishes the
proof of Lemma A.2, i.e., part i) of Lemma 4.5. ∎

######  Lemma A.3.

$\left|T_{2}-\left(\dfrac{2}{3}+H(f,g)\right)\right|\lesssim\left(n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\dfrac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)}\right)\mathbbm{1}(\xi(f_{X,Y}^{(n)})>0).$

####  A.5.2 Proof of Lemma A.3

The second term deals with the case where one of the three is from $f_{Y}(y)$
and the other two are from $g(y|x)$:

$\begin{split}T_{2}&=\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})g(y_{k}|x_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}\\\
&+\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})g(y_{k}|x_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}\\\
&+\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})f_{Y}(y_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}.\end{split}$
(A.57)

For the first term of $T_{2}$, by interchanging the integrals,

$\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})g(y_{k}|x_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})g(y_{k}|x_{k})f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}$
$\displaystyle=$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})\left[\int
g(y_{1}|x_{1})f_{X}(x_{1})dx_{1}\int
g(y_{k}|x_{k})f_{X}(x_{k})dx_{k}\right]f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}$
$\displaystyle=$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})f_{Y}(y_{1})f_{Y}(y_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}=\dfrac{1}{3}$
(A.58)

where the last line follows from (A.52). The second term in $T_{2}$ is

$\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})g(y_{k}|x_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})f_{Y}(y_{1})g(y_{k}|x_{k})$
$\displaystyle\hskip
100.0pt(g(y_{j}|x_{1})+g(y_{j}|x_{j})-g(y_{j}|x_{1}))f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}dy_{1}dy_{k}dy_{j}$
$\displaystyle=:$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})\left[\int
g(y_{j}|x_{1})f_{X}(x_{1})dx_{1}\int
g(y_{k}|x_{k})f_{X}(x_{k})dx_{k}\right]f_{Y}(y_{1})dy_{1}dy_{k}dy_{j}+E^{\prime}_{n}$
$\displaystyle=$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})f_{Y}(y_{1})f_{Y}(y_{k})f_{Y}(y_{j})dy_{1}dy_{k}dy_{j}+E_{n}^{\prime}=\dfrac{1}{3}+E_{n}^{\prime}$
(A.59)

where the last line follows from (A.52). Just as in equation (A.5.1), the
remainder term

$\displaystyle E_{n}^{\prime}$ $\displaystyle=$
$\displaystyle\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})(g(y_{j}|x_{j})-g(y_{j}|x_{1}))g(y_{k}|x_{k})d\mu(\mathbf{x})f_{Y}(y_{1})dy_{1}dy_{k}dy_{j}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})(g(y_{j}|x_{j})-g(y_{j}|x_{1}))f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}\times$
$\displaystyle\hskip 50.0pt\times\left[\int
g(y_{k}|x_{k})f_{X}(x_{k})dx_{k}\right]f_{Y}(y_{1})dy_{1}dy_{k}dy_{j}$
$\displaystyle=$ $\displaystyle E_{n}$ $\displaystyle\lesssim$
$\displaystyle\,\,n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\frac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)}.$
(A.60)

We use the fact that $j\neq k$ in the second equality and Lemma A.5 in the
last step. With a remainder term $E_{n}^{\prime\prime}$ defined similarly as
$E_{n}$ and $E_{n}^{\prime},$ we can write the third term as

$\displaystyle\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})f_{Y}(y_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=:$
$\displaystyle\int\mathbbm{1}(y_{k}<\min\\{y_{1},y\\})\left[\int
g(y_{1}|x_{1})g(y|x_{1})f_{X}(x_{1})dx_{1}\right]f_{Y}(y_{k})dy_{1}dy_{k}dy+E^{\prime\prime}_{n}$
$\displaystyle=$
$\displaystyle\int\mathbb{E}\left(\int_{t}^{\infty}g(y|X)dy\right)^{2}f_{Y}(t)dt+E_{n}^{\prime\prime}$
$\displaystyle=$ $\displaystyle H(f,g)+E_{n}^{\prime\prime}.$ (A.61)

Indeed

$\displaystyle E_{n}^{\prime\prime}$ $\displaystyle=$
$\displaystyle\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})(g(y_{j}|x_{j})-g(y_{j}|x_{1}))g(y_{1}|x_{1})f_{\mathbf{X}}(\mathbf{x})d\mathbf{x}f_{Y}(y_{k})dy_{1}dy_{k}dy_{j}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)\int\limits_{y_{k}}^{\infty}(g(y_{j}|x_{j})-g(y_{j}|x_{1}))dy_{j}\int\limits_{y_{k}}^{\infty}g(y_{1}|x_{1})dy_{1}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}f_{Y}(y_{k})dy_{k}$
$\displaystyle=$ $\displaystyle\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)[G_{Y|X_{1}=x_{1}}(y_{k})-G_{Y|X_{j}=x_{j}}(y_{k})](1-G_{Y|X_{1}=x_{1}}(y_{k}))f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}f_{Y}(y_{k})dy_{k}$
$\displaystyle=$
$\displaystyle\int\int[G_{Y|X_{1}}(y_{k})-G_{Y|X_{N(1)}}(y_{k})](1-G_{Y|X_{1}}(y_{k}))f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}f_{Y}(y_{k})dy_{k}$
$\displaystyle\lesssim$ $\displaystyle\,\mathbb{P}(|X_{1}-X_{N(1)}|\geq
1)+\left\\{\mathbb{E}\left(1+(L_{1}^{(n)}(X_{1},Y_{k}))^{\theta}+(L_{2}^{(n)}(X_{1},Y_{k}))^{\theta}\right)\right\\}^{\frac{1}{\theta}}$
$\displaystyle\left\\{\mathbb{E}|X_{1}-X_{N(1)}|^{\frac{\theta\eta}{\theta-1}}\mathbbm{1}(|X_{1}-X_{N(1)}|\leq
1)\right\\}^{\frac{\theta-1}{\theta}}$ $\displaystyle\lesssim$
$\displaystyle\,\,n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\frac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)},$
(A.62)

where the last step follows by mimicking the last line of (A.5.1). Adding
(A.5.2)-(A.5.2) proves Lemma A.3 when $\xi(f_{X,Y}^{(n)})>0$.

Once again $\xi(f_{X,Y}^{(n)})=0$ means $g(y|x)=f_{Y}(y)$ for all $x$, which
implies that $H(f,g)$, $E_{n}^{\prime}$ and $E_{n}^{\prime\prime}$ are equal
to zero. ∎

######  Lemma A.4.

$\left|T_{3}-H(f,g)\right|\lesssim\,\,\left(n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\dfrac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)}\right)\mathbbm{1}(\xi(f_{X,Y}^{(n)})>0).$

####  A.5.3 Proof of Lemma A.4

Finally in the third term, the contributions for all of $Y_{k}$; $Y_{1}$;
$Y_{N(1)}$ are from $g(y|x)$:

$\displaystyle T_{3}$ $\displaystyle=\int\int\sum_{j\neq
1,k}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})g(y_{k}|x_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=\int\int\sum_{j\neq
1}\mathbbm{1}(N(1)=j)\mathbbm{1}(y_{k}<\min\\{y_{1},y_{j}\\})g(y_{1}|x_{1})f_{Y}(y_{k})g(y_{j}|x_{j})dy_{1}dy_{k}dy_{j}f_{\mathbf{X}}(\mathbf{x})\,d\mathbf{x}$
$\displaystyle=H(f,g)+E_{n}^{\prime\prime}$
$\displaystyle=H(f,g)+O\left(n^{-\frac{\gamma}{\gamma+1}}(\log{n})^{2}+\left(\dfrac{(\log{n})^{2}}{n}\right)^{\left(\frac{\gamma(\theta-1)}{\theta(\gamma+1)}\wedge\frac{\eta\gamma}{\gamma+1}\right)}\right).$

The first line is by definition of $T_{3}.$ The second line follows by
integrating over $x_{k}$ (notice that $j\neq k$). The third and fourth lines
follow by comparing to (A.61) and (A.5.2) respectively. Once again
$\xi(f_{X,Y}^{(n)})=0$ means $g(y|x)=f_{Y}(y)$ for all $x$, which implies that
$H(f,g)$, $E_{n}^{\prime\prime}$ are equal to zero. ∎

Lemmas A.2, A.3 and A.4 together prove Lemma 4.5. ∎

###  A.6 Auxiliary Lemma

######  Lemma A.5.

Under (A2), given any $\epsilon>0$,

$\mathbb{P}\left(|X_{1}-X_{N(1)}|\geq\epsilon\right)\lesssim
n^{-\frac{\gamma}{\gamma+1}}+\frac{(\log{n})^{2}n^{-\frac{\gamma}{\gamma+1}}}{\epsilon}.$

Consequently, for any $p\leq 1$,

$\mathbb{E}|X_{1}-X_{N(1)}|^{p}\mathbbm{1}(|X_{1}-X_{N(1)}|\leq
1)\lesssim\left(\frac{(\log{n})^{2}}{n}\right)^{p}.$

###### Proof of Lemma A.5.

The proof follows by retracing the steps of [2, Lemma 14.1] and a
straightforward application of Lyapunov’s inequality. ∎