# MetaOptimize:
A Framework for Optimizing Step Sizes and Other Meta-parameters

Arsalan Sharifnassab  Saber Salehkaleybar  Richard Sutton

###### Abstract

This paper addresses the challenge of optimizing meta-parameters (i.e.,
hyperparameters) in machine learning algorithms, a critical factor influencing
training efficiency and model performance. Moving away from the
computationally expensive traditional meta-parameter search methods, we
introduce MetaOptimize framework that dynamically adjusts meta-parameters,
particularly step sizes (also known as learning rates), during training. More
specifically, MetaOptimize can wrap around any first-order optimization
algorithm, tuning step sizes on the fly to minimize a specific form of regret
that accounts for long-term effect of step sizes on training, through a
discounted sum of future losses. We also introduce low complexity variants of
MetaOptimize that, in conjunction with its adaptability to multiple
optimization algorithms, demonstrate performance competitive to those of best
hand-crafted learning rate schedules across various machine learning
applications.

Step-size Optimization, Step-size Adaptation, Meta-parameter Optimization,
Machine Learning

##  1 Introduction

Optimization algorithms used in machine learning involve meta-parameters
(i.e., hyperparameters) that substantially influence their performance. These
meta-parameters are typically identified through a search process, such as
grid search or other trial-and-error methods, prior to training. However, the
computational cost of this meta-parameter search is significantly larger than
that of training with optimal meta-parameters (Dahl et al., 2023; Jin, 2022).
Meta-parameter optimization seeks to streamline this process by concurrently
adjusting meta-parameters during training, moving away from the
computationally expensive and often sub-optimal trial and error search
methods.

Meta-parameter optimization is particularly important in continual learning
(De Lange et al., 2021), its primary domain, where dynamic environments or
evolving loss functions necessitate meta-parameters, like step sizes, to adapt
to optimal time-varying values rather than settling on a static value as in
the stationary case. Nevertheless, this work concentrates on the stationary
scenario, demonstrating the competitiveness of meta-parameter optimization
even in this case.

In this work, we propose _MetaOptimize_ as a framework for optimizing meta-
parameters to minimize a notion of regret, specifically accounting for the
long-term influence of step sizes on future loss. The framework is applicable
to a broad range of meta-parameters, however our primary focus in this paper
is on step sizes as a critical meta-parameter that is universally present.

MetaOptimize brings additional benefits beyond simplifying the search process.
Firstly, it enables a dynamic step-size adjustment during training,
potentially accelerating the learning process. Traditional methods typically
require manual customization of learning rate schedules for each problem,
often following an optimal pattern of initial increase and subsequent decay
(Amid et al., 2022). As our experiments show, step sizes obtained from
MetaOptimize follow similar patterns automatically.

Secondly, varying step sizes across different blocks of a neural network, such
as layers or neurons, has been shown to improve performance (Singh et al.,
2015; Howard & Ruder, 2018). Manually tuning or using grid search for block-
wise step-sizes is impractical in networks with numerous blocks. Our
MetaOptimize framework can automatically manage blockwise step sizes.

The concept of meta step-size optimization can be traced back to (Kesten,
1958), Delta-bar-Delta (Sutton, 1981; Jacobs, 1988), and its incremental
variant, IDBD (Sutton, 1992). Over the years, numerous methods have been
developed to address this challenge, detailed further in Section 8. This
research distinguishes itself from prior work through the following key
aspects:

  * •

We introduce a novel formalization of step-size optimization as minimizing a
specific form of regret, essentially a discounted sum of future losses. We
demonstrate how to effectively address this challenge in a causal manner.

  * •

Our MetaOptimize framework is general in the sense that it can wrap around any
arbitrary first-order optimization algorithm, also called _base update_ ,
(such as SGD, RMSProp (Hinton et al., 2012), Adam (Kingma & Ba, 2014), or Lion
(Chen et al., 2023))), for which it optimizes step sizes via an algorithm of
desire (such as SGD, Adam, RMSProp, or Lion), called the _meta update_.

  * •

We illustrate that some existing methods (like IDBD (Sutton, 1992), its
extension (Xu et al., 2018), and hypergradient descent (Baydin et al., 2017))
are actually specific instances or approximations within our broader framework
(detailed in Section 5).

  * •

We provide some approximation methods, that when integrated into our
framework, lead to computational complexity overhead as minimal as an inner
product of the network-weights’ dimension (see Section 6).

  * •

Our experimental results demonstrate that certain combinations of base and
meta updates are highly effective, being competitive to manually designed
learning rate schedules on datasets like CIFAR10 (Krizhevsky et al., 2009),
ImageNet (Deng et al., 2009), and language modeling applications (Eldan & Li,
2023).

##  2 Problem Setting

We introduce a general continual optimization setting that, for a given
sequence of loss functions $f_{t}(\cdot):\mathbb{R}^{n}\to\mathbb{R}$,
$t=0,1,2,\ldots$, aims to find a sequence of weight vectors
$\boldsymbol{w}_{1},\boldsymbol{w}_{2},\boldsymbol{w}_{3},\ldots$ to minimize
a discounted sum of future loss over time:

$F^{\gamma}_{t}\overset{\text{\tiny
def}}{=}(1-\gamma)\,\sum_{\tau>t}\gamma^{\tau-t-1}f_{\tau}(\boldsymbol{w}_{\tau}),$
(1)

where $\gamma\in[0,1)$ is a fixed constant, often very close to $1$, called
the _discount factor_. As an important special case, the above setting
includes stationary supervised learning if $f_{t}$ are samples of a static
distribution, for all $t$. In this case, minimizing $F^{\gamma}_{t}$ results
in rapid minimization of the expected loss.

Consider an arbitrary first order optimization algorithm (including but not
limited to SGD, RMSProp (Hinton et al., 2012), Adam (Kingma & Ba, 2014), and
Lion (Chen et al., 2023)), for updating the $\boldsymbol{w}_{t}$. At each time
$t$, this algorithm takes the gradient $\nabla f_{t}(\boldsymbol{w}_{t})$ of
the immediate loss function, along with an $m$-dimensional vector
$\boldsymbol{\beta}_{t}$ of meta-parameters, and updates $\boldsymbol{w}_{t}$
and possibly some internal variables (e.g., momentum in Adam or trace of
gradient squares in RMSProp), based on a fixed update rule
$\operatorname{Alg}_{\textrm{base}}$, referred to as the _base-update_ ,

$\boldsymbol{x}_{t}=\operatorname{Alg}_{\textrm{base}}(\boldsymbol{x}_{t},\nabla
f_{t}(\boldsymbol{w}_{t}),\boldsymbol{\beta}_{t}),$ (2)

where $\boldsymbol{x}_{t}\overset{\text{\tiny
def}}{=}\operatorname{Stack}(\boldsymbol{w}_{t},\,\tilde{\boldsymbol{x}}_{t})$
is an $\tilde{n}$-dimensional vector obtained by stacking $\boldsymbol{w}_{t}$
and all internal variables of the algorithm that are being updated (e.g.,
momentum), denoted by $\tilde{\boldsymbol{x}}_{t}$.

The goal of the MetaOptimize framework is to find a sequence of meta-
parameters $\boldsymbol{\beta}_{t}$, for $t=1,2,\ldots$, such that when
plugged into the base update, (2), results in relative minimization of
$F^{\gamma}_{t}$ defined in (1).

Step-size optimization is a special case of the above framework where at each
time $t$, the $m$ dimensional vector $\boldsymbol{\beta}_{t}$ is used to
determine the $n$-dimensional (weight-wise) vector $\boldsymbol{\alpha}_{t}$
of step sizes (typically $m\ll n$), through a fixed function
$\sigma:\mathbb{R}^{m}\to\mathbb{R}^{n}$,

$\boldsymbol{\alpha}_{t}=\sigma(\boldsymbol{\beta}_{t}).$ (3)

A typical choice is to partition weights of the neural network into $m$
blocks, associate each block to an entry of $\boldsymbol{\beta}$, and let the
step sizes over each block be equal to $\exp(\beta)$ for the corresponding
entry $\beta$. With a suitable choice of $m$, we can have a single shared
scalar step-size for all of the weights, or have layer-wise, node-wise, or
even weight-wise step sizes. It is particularly beneficial to consider a
function $\sigma$ of the exponential form, mentioned above, because of two
reasons (Sutton, 1992). First, it ensures that $\boldsymbol{\alpha}_{t}$ will
always be positive. Second, a constant change in $\boldsymbol{\beta}_{t}$
would lead to a multiplicative change in $\boldsymbol{\alpha}_{t}$, making it
suitable for adapting step sizes with different orders of magnitude.

Notation conventions: For any vector $\boldsymbol{v}$, we denote by
$\left[\boldsymbol{v}\right]$ a diagonal matrix with diagonal entries derived
from $\boldsymbol{v}$. We denote by $\sigma^{\prime}(\boldsymbol{\beta}_{t})$
the Jacobian of $\boldsymbol{\alpha}_{t}$ with respect to
$\boldsymbol{\beta}_{t}$.

##  3 Forward and Backward Views

Since the definition of $F^{\gamma}_{t}$ in (1) relies on information forward
into the future, minimizing it in a causal way necessitates alternative views,
which we will discuss in this section. In order to motivate our approach, we
start by considering a hypothetical meta-parameter optimization algorithm that
has oracle access to future information (e.g., future loss), in which we
update $\boldsymbol{\beta}_{t}$ along the gradient of $F^{\gamma}_{t}$ with
respect to $\boldsymbol{\beta}_{t}$; that is for $t=0,1,2,\ldots$,

$\begin{split}\boldsymbol{\beta}_{t+1}&=\boldsymbol{\beta}_{t}-\eta\frac{d}{d\,\boldsymbol{\beta}_{t}}F^{\gamma}_{t}\\\
&=\boldsymbol{\beta}_{t}-\eta\,(1-\gamma)\,\sum_{\tau>t}\gamma^{\tau-t-1}\frac{d}{d\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}),\end{split}$
(4)

for some fixed _meta step size_ , $\eta>0$. This _forward-view_ update however
requires that at time $t$, we have access to $f_{\tau}(\cdot)$ and
$\boldsymbol{w}_{\tau}$ for all $\tau>t$, which are typically unavailable. To
circumvent this problem, we adopt an idea similar to the _eligibility traces_
in reinforcement learning (Sutton, 1988; Sutton & Barto, 2018). More
specifically, instead of the forward-view update, we introduce an update of
the following type, which we call the _backward-view_ update. At time
$\tau=0,1,2,\ldots$, we let

$\boldsymbol{\beta}_{\tau+1}\leftarrow\boldsymbol{\beta}_{\tau}-\eta\,(1-\gamma)\,\sum_{t<\tau}\gamma^{\tau-t-1}\frac{d}{d\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}).$
(5)

Note that every term
$\gamma^{\tau-t-1}\frac{d\,f_{\tau}(\boldsymbol{w}_{\tau})}{d\,\boldsymbol{\beta}_{t}}$
in the right hand side of (4) also appears in (5), but is applied at time
$\tau$ instead of time $t$, which is the earliest time that all required
information for computing this term are gathered causally. Consequently, the
$\widehat{\nabla_{\boldsymbol{\beta}}F}_{\tau}$ defined below serves as a
causal proxy for ${d\,F^{\gamma}_{\tau}}/{d\,\boldsymbol{\beta}_{\tau}}$;

$\widehat{\nabla_{\boldsymbol{\beta}}F}_{\tau}\overset{\text{\tiny
def}}{=}(1-\gamma)\sum_{t=0}^{\tau-1}\gamma^{\tau-t-1}\frac{d}{d\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}).$
(6)

It follows from chain rule that

$\widehat{\nabla_{\boldsymbol{\beta}}F}_{\tau}=\mathcal{H}_{\tau}^{T}\nabla
f_{\tau}(\boldsymbol{w}_{\tau}).$ (7)

where

$\mathcal{H}_{\tau}\overset{\text{\tiny
def}}{=}(1-\gamma)\sum_{t=0}^{\tau-1}\gamma^{\tau-t-1}\frac{d\boldsymbol{w}_{\tau}}{d\,\boldsymbol{\beta}_{t}}.$
(8)

The ${d\boldsymbol{w}_{\tau}}/{d\,\boldsymbol{\beta}_{t}}$ in (8) denotes the
Jacobian matrix of $\boldsymbol{w}_{\tau}$ with respect to
$\boldsymbol{\beta}_{t}$. Therefore, $\mathcal{H}_{\tau}$ is an $n\times m$
matrix such that $\mathcal{H}_{\tau}\,\boldsymbol{v}$, for any $m\times 1$
vector $\boldsymbol{v}$, equals the change in $\boldsymbol{w}_{\tau}$ if we
increment all past $\boldsymbol{\beta}_{t}$ along
$\gamma^{\tau-t}\,\boldsymbol{v}$.

##  4 General Meta Update of step sizes

The general idea is to update $\boldsymbol{\beta}_{t}$ via any first order
optimization algorithm to minimize $F^{\gamma}_{t}$, while using the surrogate
gradient $\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}$ in place of
$\nabla_{\boldsymbol{\beta}}F^{\gamma}_{t}$, to preserve causality of the
updates. More specifically, for $t=1,2,\ldots$, let

$\begin{split}\boldsymbol{y}_{t+1}&=\operatorname{Alg}_{\textrm{meta}}\big{(}\boldsymbol{y}_{t},\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}\big{)}\\\
&=\operatorname{Alg}_{\textrm{meta}}\big{(}\boldsymbol{y}_{t},\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}\end{split}$ (9)

be the _meta update_ , where $\boldsymbol{y}_{t}\overset{\text{\tiny
def}}{=}\operatorname{Stack}(\boldsymbol{\beta}_{t},\,\tilde{\boldsymbol{y}}_{t})$
is an $\tilde{m}$-dimensional vector obtained from stacking
$\boldsymbol{\beta}_{t}$ and all other internal variables
$\tilde{\boldsymbol{y}}_{t}$ of the algorithm (e.g., momentum), and the second
equality follows from (7). Examples of $\operatorname{Alg}_{\textrm{meta}}$
include SGD, RMSprop, Adam, and Lion algorithms. Note that in all cases, we
pass $\widehat{\nabla_{\boldsymbol{\beta}}F}$ to the algorithm as the
gradient.

In each iteration, after performing the base update (2), we compute
$\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})$ and plug it into (9) to
update $\boldsymbol{y}$ (and in particular $\boldsymbol{\beta}$). Therefore,
the algorithm is complete if have access to $\mathcal{H}_{t}$. In the rest of
this section, we show how $\mathcal{H}_{t}$ can be obtained via an incremental
update. The complete description of MetaOptimize framework is given in
Algorithm 1.

Let $\boldsymbol{h}_{t}$ be an $nm$-dimensional vector obtained by stacking
the columns of the $n\times m$ matrix $\mathcal{H}_{t}$. It follows from the
chain rule that for any times $t$ and $\tau$ with $t\geq\tau$,

$\begin{split}\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}&=\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}\,\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}\,+\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{x}_{t}}\,\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}}+\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}\,\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}},\\\
\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}&=\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}\,\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}+\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}\,\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}}+\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}\,\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}},\\\
\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}&=\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{y}_{t}}\,\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}\,+\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}\,\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}}+\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}\,\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}}.\end{split}$

Letting

$G_{t}\overset{\text{\tiny
def}}{=}{\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]},$ (10)

the above set of equations can be equivalently written as

$\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\
\end{array}\end{array}\right]=G_{t}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\end{array}\right].$

It follows that

$\sum_{\tau=0}^{t}\gamma^{t-\tau}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\
\end{array}\end{array}\right]=G_{t}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-11pt}\hfil\\\
\end{array}\end{array}\right]+\,G_{t}\sum_{\tau=0}^{t-1}\gamma^{t-\tau}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}}}\\\
\vspace{-11pt}\hfil\\\ \end{array}\end{array}\right].$ (11)

Let

$\displaystyle Y_{t}$ $\displaystyle\overset{\text{\tiny
def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{d\,\boldsymbol{y}_{t}}{d\,\boldsymbol{\beta}_{\tau}}$
(12) $\displaystyle X_{t}$ $\displaystyle\overset{\text{\tiny
def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{d\,\boldsymbol{x}_{t}}{d\,\boldsymbol{\beta}_{\tau}},$
(13) $\displaystyle Q_{t}$ $\displaystyle\overset{\text{\tiny
def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{d\,\boldsymbol{h}_{t}}{d\,\boldsymbol{\beta}_{\tau}}.$
(14)

Note also that ${d\,\boldsymbol{x}_{t}}/{d\,\boldsymbol{\beta}_{t}}=0$,
${d\,\boldsymbol{h}_{t}}/{d\,\boldsymbol{\beta}_{t}}=0$, and
${d\,\boldsymbol{y}_{t}}/{d\,\boldsymbol{\beta}_{t}}={d\,\operatorname{Stack}(\boldsymbol{\beta}_{t},\,\tilde{\boldsymbol{y}}_{t})}/{d\,\boldsymbol{\beta}_{t}}=\operatorname{Stack}(I,\,0)$.
Plugging these into (11), we obtain

$\left[\begin{array}[]{c}\\!Y_{t+1}\\!\\\ \\!X_{t+1}\\!\\\
\\!Q_{t+1}\\!\end{array}\right]=G_{t}\left(\gamma\left[\begin{array}[]{c}\\!Y_{t}\\!\\\
\\!X_{t}\\!\\\
\\!Q_{t}\\!\end{array}\right]+(1-\gamma)\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\left[\begin{array}[]{c}\\!I\\!\\\ \\!0\\!\end{array}\right]}\\\
\vspace{-11pt}\hfil\\\ \end{array}\\\ 0\\\ 0\end{array}\right]\right).$ (15)

Matrices $X_{t},Y_{t},Q_{t}$ can be computed iteratively using (15). The
matrix $\mathcal{H}_{t}$ in (8) is then obtained from $X_{t}$ by noting that
$\boldsymbol{x}_{t}=\operatorname{Stack}(\boldsymbol{w}_{t},\,\tilde{\boldsymbol{x}}_{t})$,
and therefore $\mathcal{H}_{t}$ is a sub-matrix of $X_{t}$ constituting the
first $n$ rows of $X_{t}$.

To complete Algorithm 1, one only needs to compute the matrix $G_{t}$ in (10)
for the given pair of base and meta updates,
$\operatorname{Alg}_{\textrm{base}}$ and $\operatorname{Alg}_{\textrm{meta}}$.
In Appendix A, we compute $G_{t}$ for some popular first order optimization
algorithms, namely SGD, AdamW, and Lion. Interestingly, the first row of
blocks in $G_{t}$ appears to depend only on
$\operatorname{Alg}_{\textrm{meta}}$, and the second and third rows of blocks
depend only on $\operatorname{Alg}_{\textrm{base}}$. This facilitates the
derivation and implementation for different combinations of base and meta
algorithms.

Algorithm 1 MetaOptimize Framework

Given: Base-update $\operatorname{Alg}_{\textrm{base}}$, meta-update
$\operatorname{Alg}_{\textrm{meta}}$,

Parameters: Discount-factor $\gamma\leq 1$.

Initialize: $X_{0}=0_{(n+\tilde{n})\times m}$, $Y_{0}=\big{[}I_{m\times
m}\,|\,{0}_{m\times\tilde{m}}\big{]}^{T}$, and $Q_{0}={0}_{nm\times m}$.

for $t=0,1,2,\ldots$ do

$\boldsymbol{x}_{t+1}\leftarrow\operatorname{Alg}_{\textrm{base}}(\boldsymbol{x}_{t},\nabla
f_{t}(\boldsymbol{w}_{t}),\boldsymbol{\beta}_{t})$.

$\mathcal{H}_{t}=$ sub-matrix of $X_{t}$, constituting its first $n$ rows.

$\boldsymbol{y}_{t+1}\,\leftarrow\operatorname{Alg}_{\textrm{meta}}\big{(}\boldsymbol{y}_{t},\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}$.

Update $X_{t}$, $Y_{t}$, and $Q_{t}$ from (15), using $G_{t}$ in (10).

end for

##  5 Reducing Complexity

The matrix $G_{t}$ in (10) is typically a large matrix, which limits the
practicality of the algorithm. Below, we discuss two approximations of
$G_{t}$, that lead to more practical algorithms.

2$\times$2 approximation:  The vector $\boldsymbol{h}_{t}$, obtained from
stacking the columns of $\mathcal{H}_{t}$, is a large vector of length $mn$.
Therefore, the last row and column of blocks in $G_{t}$ have huge dimensions.
Moreover, as we show in Appendix A, the term
$d\boldsymbol{h}_{t+1}/d\boldsymbol{x}_{t}$ typically involves third order
derivatives of $f_{t}$ with respect to $\boldsymbol{w}_{t}$, which is not
practically computable.

In the 2$\times$2 approximation, we resolve the above problems by completely
zeroing out all blocks in the last row and also in the last column of blocks
in $G_{t}$. Consequently, we can also remove $Q_{t}$ from the algorithm. This
appears to have little impact on the performance, as we empirically observed
in some simple settings. Note that in matrix $G_{t}$, as defined in (10), the
block $d\,\boldsymbol{x}_{t+1}/d\,\boldsymbol{h}_{t}$ is always zero since
$\mathcal{H}_{t}$ appears nowhere in the base update (2). Consequently, $Q$
had no direct impact on $X$ (and therefore $\mathcal{H}$), and could impact
$X$ indirectly merely via $Y$.

L-approximation:  Herein, we take a step further, and in addition to the last
row and the last column of blocks of $G_{t}$, we also zero out the block in
the first row and the second column of $G_{t}$. In other words, we let

$G^{L}_{t}\overset{\text{\tiny
def}}{=}{\left[\begin{array}[]{cc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{0}\\\ \vspace{-10pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]},$ (16)

and simplify (15) as

$\left[\begin{array}[]{c}\\!Y_{t+1}\\!\\\
\\!X_{t+1}\\!\end{array}\right]=G^{L}_{t}\left(\gamma\left[\begin{array}[]{c}\\!Y_{t}\\!\\\
\\!X_{t}\\!\end{array}\right]+(1-\gamma)\left[\begin{array}[]{c}\\!I\\!\\\
\\!0\\!\\\ \hline\cr 0\end{array}\right]\right).$ (17)

We have empirically observed that the resulting algorithm typically performs
as good as the 2$\times$2 approximation, and even results in improved
stability in some cases.

Intuition of MetaOptimize updates: Algorithm 2 provides a 2$\times$2
approximation of MetaOptimize for the case where both base and meta updates
use SGD, and under scalar step-size (detailed derivation in Appendix A). It
shows that $\mathcal{H}_{t}$ traces past gradients, decaying at rate
$\gamma(I-\left[\boldsymbol{\alpha}\right]\nabla^{2}f_{t})$. This decay
ensures that if past gradients poorly approximate future ones due to large
$\nabla^{2}f_{t}$ or $\boldsymbol{\alpha}$, their influence fades more
rapidly. If the current gradient aligns positively with past gradients (i.e.,
$-\mathcal{H}_{t}^{T}\nabla f_{t}>0$), the algorithm increases the step-size
$\boldsymbol{\alpha}$ for quicker adaptation; if negatively correlated, it
reduces the step-size to prevent issues like zigzagging. $Y_{t}$ in (12)
reflects the impact of changes in past $\boldsymbol{\beta}$ on the current
value of $\boldsymbol{\beta}$, amplifying the increment in the
$\mathcal{H}_{t+1}$ update if $\boldsymbol{\beta}$ has been consistently
rising or falling over the recent past. It is also worth noting that in
Algorithm 2, under the L-approximation, $Y_{t}$ remains constant, equal to
$I$. A similar phenomenon occurs also when Adam, RMSProp, or Lion algorithms
are used instead of SGD.

Algorithm 2 MetaOptimize with $2\times 2$ approximation,
$(\operatorname{Alg}_{\textrm{base}},\operatorname{Alg}_{\textrm{meta}})=$
(SGD, SGD) and scalar step-size.

Initialize: $\mathcal{H}_{0}=\boldsymbol{0}_{n\times 1},Y_{0}=0_{1\times 1}$.

for $t=1,2,\ldots$ do

$\boldsymbol{\alpha}_{t}=e^{\beta_{t}}\,\boldsymbol{1}_{n\times 1}$

Base update:

$\boldsymbol{w}_{t+1}\,=\,\boldsymbol{w}_{t}\,-\,\boldsymbol{\alpha}_{t}\nabla
f_{t}(\boldsymbol{w}_{t})$

$\hat{Y}_{t}=\gamma Y_{t}+(1-\gamma)$

$\mathcal{H}_{t+1}=\gamma\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}(\boldsymbol{w}_{t})\big{)}\mathcal{H}_{t}-\hat{Y}_{t}\boldsymbol{\alpha}_{t}\nabla
f_{t}(\boldsymbol{w}_{t})$

$Y_{t+1}=\hat{Y}_{t}-\gamma\eta\mathcal{H}_{t}^{T}\nabla^{2}f_{t}(\boldsymbol{w}_{t})\mathcal{H}_{t}$

Meta update:

$\beta_{t+1}=\beta_{t}-\eta\,\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})$

end for

Containing some existing algorithms as special cases:  As special cases of the
above L-approximation method, we obtain IDBD algorithm (Sutton, 1982) and its
extension (Xu et al., 2018), if we limit $\operatorname{Alg}_{\textrm{base}}$
and $\operatorname{Alg}_{\textrm{meta}}$ to SGD algorithm. Refer to Appendix
B.1 for a more detailed discussion.

Our algorithm also contains the hyper-gradient descent algorithm (Baydin et
al., 2017) as a special case, where we are using the SGD algorithm for both
base and meta updates and applying further approximation on $G_{t}$ by zeroing
out its second column completely (or alternatively setting $\gamma=0$). Refer
to Appendix B.2 for more details. In this algorithm, however, the step size is
updated towards minimizing the immediate loss $f_{t}$ rather than the
discounted sum of future loss, $F^{\gamma}_{t}$, ignoring the long-term effect
of step sizes on future loss, which in turn typically results in a less
competitive performance.

##  6 Hessian-Free MetaOptimize

The step-size optimization algorithms discussed so far typically involve
second derivative (Hessian), $\nabla^{2}f_{t}(\boldsymbol{w}_{t})$, of the
loss function. In particular, the Hessian matrix typically appears in the
middle column of blocks in the $G_{t}$ matrix; e.g., in the
$d\boldsymbol{w}_{t+1}/d\boldsymbol{w}_{t}$ block where
$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\nabla
f_{t}(\boldsymbol{w}_{t})$. Consequently, the update in (15) involves a
Hessian-matrix-product of the form
$\nabla^{2}f_{t}(\boldsymbol{w}_{t})\mathcal{H}_{t}$, which increases per-step
computational complexity of the algorithm. The added computational overhead
would be still manageable if $m$ is small. In particular for $m=1$ (i.e., the
case that a scalar step-size is used for update of all weights),
$\mathcal{H}_{t}$ would be a vector; and one can leverage efficient Hessian-
vector-product computation techniques that have the same complexity as
gradient computation (Pearlmutter, 1994).

Interestingly, for certain base and meta algorithms, we can eliminate the
Hessian without much compromising the performance. An example of such (base or
meta) algorithms is the Lion algorithm (Chen et al., 2023). The Lion
algorithm, when used as the base algorithm, updates $\boldsymbol{w}_{t}$ as

$\displaystyle\boldsymbol{m}_{t+1}=\rho\,\boldsymbol{m}_{t}+(1-\rho)\,\nabla
f_{t}(\boldsymbol{w}_{t}),$
$\displaystyle\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t},$

where $\rho,c\in[0,1)$, $\kappa$ is a nonnegative weight-decay parameter, and
$\operatorname{Sign}(\cdot)$ is the entry-wise sign function. In the special
cases of $c=0$ or $\rho=0$, $\boldsymbol{m}_{t}$ can be eliminated and the
above update simplifies to
$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}\nabla
f_{t}\big{)}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t}$. In this case,
it is easy to see that the derivatives of $\boldsymbol{x}_{t}$ in (10) are
Hessian-free. The above argument can be extended to arbitrary values of $c$
and $\rho$. In Appendix A.1.3 (respectively Appendix A.3.2), we show that if
$\operatorname{Alg}_{\textrm{meta}}$ ($\operatorname{Alg}_{\textrm{base}}$) is
the Lion algorithm, then the first row (second and third rows) of blocks in
$G$ would be Hessian-free. In summary, Algorithm 1 turns Hessian-free, if Lion
is used in both base and meta updates. This elimination of Hessian results
from the flatness of the $\operatorname{Sign}$ function when ignoring the
discontinuity of $\operatorname{Sign}$ at $0$.

For other algorithms, we may consider their _Hessian-free approximation_ by
zeroing out any Hessian term in $G_{t}$. The Hessian-free approximation turns
out to be a good approximation, especially for base and meta algorithms that
involve gradient normalization, like RMSProp and Adam. Note that, the sign
function used in the Lion algorithm is an extreme form of normalization that
divides a vector by its absolute value. We could instead use softer forms of
normalization, such as normalizing to square root of a trace of squared
vector, as in RMSProp. Such normalizations typically result in two opposing
Hessian-based terms in $\mathcal{H}_{t}$’s update (stemming from
$\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{w}_{t}}$ and
$\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{v}_{t}}$ blocks of matrix
$G_{t}$), aiming to cancel out, particularly when consecutive gradients are
positively correlated. The main advantage of Hessian-free methods lies in
their computational congeniality, as discussed next.

Figure 1: Learning curves of CIFAR10 dataset for the selected (base, meta)
combinations.

For base and meta updates including SGD, RMSProp, AdamW, and Lion, the
Hessian-free 2$\times$2 approximation has low computational complexity,
requiring only a few vector-products per iteration beyond the computations
required for the base and meta updates. When Hessian terms in $2\times 2$
approximation of $G_{t}$ are zeroed out, it consists of blocks, each block
being block-diagonal, leading to $X_{t}$ and $Y_{t}$ that also consist of
blocks, with each block being block-diagonal. Thus, $X_{t}$ and $Y_{t}$
matrices can be simplified to vector forms, avoiding costly matrix
multiplications. Moreover computational overhead remains the same for general
blockwise step-sizes (including layer-wise and weight-wise cases). We note
also that for the meta updates mentioned above if we use no weight-decay in
the meta update, Hessian-free 2$\times$2 approximation becomes equivalent to
Hessian-free L-approximation. Algorithm 3 presents Hessian-free approximations
for some selected base and meta updates.

Figure 2: Evolution of scalar step-sizes during training, demonstrating
robustness to initial step-sizes. The experiment used (Lion, Lion) as (base,
meta) updates and was on CIFAR10 dataset. Figure 3: Evolution of blockwise
step-sizes during training in CIFAR10 dataset, using (SGD with momentum, Adam)
as (base, meta) update.

##  7 Experiments

In this section, we evaluate the MetaOptimize framework on various benchmarks.
Out of several possible combinations of base and meta algorithms and
approximations, we report a few Hessian-free combinations that showed better
performance, the psuedocode of which is given in Algorithm 3. Moreover, for
these combinations, we set the initial step sizes to one or two orders of
magnitudes lower than the range of good fixed step sizes, with no specific
tuning. We compare with some popular optimizers (such as Adam, RMSProp, and
Lion) as baselines. Their meta-parameters are well-tuned for each task
separately.

We performed experiments in the following learning tasks: 1- Image
classification on CIFAR10 (Krizhevsky et al., 2009) and ImageNet dataset (Deng
et al., 2009). 2- Language modeling on TinyStories dataset (Eldan & Li, 2023).
Experiment details are given in Appendix C.

Algorithm 3 Hessian-Free algorithms with 2$\times$2 approximation used in
experiments

Parameters: $\eta>0$ (default $10^{-3}$), $\gamma\in[0,1]$ (default $1$)

Initialize: $\boldsymbol{h}_{0}=\boldsymbol{0}_{n\times 1}$.

for $t=1,2,\ldots$ do

$\boldsymbol{\alpha}_{t}=\sigma(\boldsymbol{\beta}_{t})$, exponential
scalar/blockwise

Base update:

if $\operatorname{Alg}_{\textrm{base}}$ is Hessian-free AdamW then

$\boldsymbol{m}_{t+1}\,=\,\rho\,\boldsymbol{m}_{t}\,+\,\nabla
f_{t}(\boldsymbol{w}_{t})$.

$\boldsymbol{v}_{t+1}\,=\,\lambda\,\boldsymbol{v}_{t}\,+\,\nabla
f_{t}(\boldsymbol{w}_{t})^{2}$.

$\mu_{t}\,=\,\left(\frac{1-\rho}{{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1-\rho^{t}}}\right)\,/\,\sqrt{\frac{1-\lambda}{1-\lambda^{t}}}$.

$\boldsymbol{w}_{t+1}\,=\,\boldsymbol{w}_{t}\,-\,\boldsymbol{\alpha}_{t}\mu_{t}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t}$

$\boldsymbol{h}_{t+1}=\gamma\boldsymbol{h}_{t}-\gamma\kappa\boldsymbol{\alpha}_{t}\,\boldsymbol{h}_{t}-\mu_{t}\boldsymbol{\alpha}_{t}\left(\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}+\kappa\boldsymbol{w}_{t}\right)$.

else if $\operatorname{Alg}_{\textrm{base}}$ is Lion then

$\boldsymbol{m}_{t+1}\,=\,\rho\,\boldsymbol{m}_{t}\,+\,\nabla
f_{t}(\boldsymbol{w}_{t})$.

$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t}$.

$\boldsymbol{h}_{t+1}=\gamma\boldsymbol{h}_{t}-\gamma\kappa\boldsymbol{\alpha}_{t}\boldsymbol{h}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t}$.

end if

Meta update:

$\boldsymbol{y}=\boldsymbol{h}_{t}\,\nabla f_{t}(\boldsymbol{w}_{t})$

if $\operatorname{Alg}_{\textrm{meta}}$ is Hessian-free Adam then

$\bar{\boldsymbol{m}}_{t+1}\,=\,\bar{\rho}\,\bar{\boldsymbol{m}}_{t}\,+\,\boldsymbol{y}$.

$\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}\,=\,\bar{\lambda}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}\,+\,\boldsymbol{y}^{2}$.

$\bar{\mu}_{t}\,=\,\left(\frac{1-\bar{\rho}}{{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1-\bar{\rho}^{t}}}\right)\,/\,\sqrt{\frac{1-\bar{\lambda}}{1-\bar{\lambda}^{t}}}$.

$\boldsymbol{\beta}_{t+1}\,=\,\boldsymbol{\beta}_{t}\,-\,\eta\,\bar{\mu}_{t}\,\frac{\bar{\boldsymbol{m}}_{t}}{\sqrt{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}$.

else if $\operatorname{Alg}_{\textrm{meta}}$ is Lion then

$\bar{\boldsymbol{m}}_{t+1}\,=\,\bar{\rho}\,\bar{\boldsymbol{m}}_{t}\,+\,\boldsymbol{y}$.

$\boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}\bar{c}\,\bar{\boldsymbol{m}}_{t}+(1-\bar{c})\boldsymbol{y}\big{)}$.

end if

end for

###  7.1 Image classification

####  7.1.1 CIFAR10 dataset

We trained ResNet-18 for 60 epochs with a batch size of 100. We chose four
combinations of (base, meta) algorithms for Hessian-free MetaOptimize, namely
(AdamW, Adam), (Lion, Lion), (RMSprop, Adam), and (SGD with momentum, Adam);
and compared them with corresponding baselines; i.e., AdamW, Lion, RMSprop,
and SGD with momentum, with their well-tuned fixed step sizes. In our
algorithms, in addition to scalar step-sizes, we also considered block-wise
step-sizes by partitioning layers of the ResNet18 network into six blocks
(first and last linear blocks and 4 ResNet blocks). The results depicted in
Figure suggest that each tested base-meta combination, whether scalar or
blockwise, surpasses the performance of the well-tuned baseline. Notably, the
approach enhances the base update of SGD with momentum, initially
underperforming, to an optimization algorithm that matches the performance of
other combinations.

Interestingly, as demonstrated in Figure 2, the MetaOptimize algorithms show
remarkable robustness to initial step-size choices, even for initial step
sizes that are several orders of magnitude smaller than the optimal fixed
step-size.

Figure 3 depicts the blockwise step sizes for (SGD with momentum, Adam) across
different blocks, showing an almost increasing trend from the first to the
last block (output layer), which is generally a desirable pattern. For the
blockwise versions of (AdamW, Adam), (Lion, Lion), and (RMSProp, Adam)
updates, however, we did not observe such variability, observing that the
first five blocks exhibit similar trends and values over time but the last
block follows a distinct trend, growing larger and rising at a later time.

####  7.1.2 ImageNet dataset

We trained ResNet-18 for 90 epochs with a batch size of 256. The results are
shown in Figure 4. We evaluated MetaOptimize with (base, meta) combinations
(AdamW, Adam) and (Lion, Lion), for scalar and also blockwise step-sizes with
the same blocks as in the CIFAR10 experiment. Baselines included Lion, Adam
with well-tuned fixed step-sizes, and AdamW with a well-tuned cosine decay
learning rate scheduler with a 10k iterations warmup. Figure reveals all
(base, meta) algorithm combinations had a steeper rise than AdamW, with
(AdamW, Lion) scalar version outperforming others throughout training. Unlike
with CIFAR10, blockwise versions did not enhance performance here.

Figure 4: Learning curves of ImageNet dataset.

###  7.2 Language modeling

In our language model experiments, we utilized the TinyStories dataset (Eldan
& Li, 2023), a synthetic collection of brief stories designed for children
aged 3 to 4. This dataset proves effective for training and evaluating
language models that are significantly smaller than the current state-of-the-
art, and capable of crafting stories that are not only fluent and coherent but
also diverse.

We used the implementation in (Karpathy, 2024) for training 15M parameter
model with a batch size of 128 for 30k iterations on the TinyStories dataset.
MetaOptimize, with combinations (AdamW, Lion) and (Lion, Lion), was tested
against baselines including AdamW and Lion with well-tuned fixed step sizes,
and AdamW with a well-tuned cosine decay learning rate scheduler and 1k
iterations warmup. Results show MetaOptimize outperforms fixed step size
baselines, with an initial delay due to small initial stepsizes. However it
falls short of beating the well-tuned learning rate scheduler within 30k
iterations.

Figure 5: Learning curves of TinyStories dataset.

##  8 Related Work

Automatic adaptation of step sizes, has been an important research topic in
the literature of stochastic optimization. Several works aimed to remove the
manual tuning of learning rates via adaptations of classical line search
(Rolinek & Martius, 2018; Vaswani et al., 2019; Paquette & Scheinberg, 2020;
Kunstner et al., 2023) and Polyak step size (Berrada et al., 2020; Loizou et
al., 2021), stochastic proximal methods (Asi & Duchi, 2019), stochastic
quadratic approximation (Schaul et al., 2013), hyper-gradient descent (Baydin
et al., 2017), and nested hyper-gradient descent (Chandra et al., 2022). A
limitation of most of these methods is their potential underperformance when
their meta-parameters are not optimally configured for specific problems (Ivgi
et al., 2023). Additionally, the primary focus of most of these methods is on
minimizing immediate loss rather than considering the long-term effects of
step sizes on future loss.

Normalization techniques proposed over past few years, such as RMSProp AdaGrad
(Duchi et al., 2011), (Hinton et al., 2012), and Adam (Kingma & Ba, 2014),
have significantly enhanced training and learning processes. While these
algorithms show promise in the stationary problems, these normalization
techniques do not optimize effective step sizes and are prone to have sub-
optimal performance especially in the continual learning settings (Degris et
al., 2024).

An early practical step-size optimization method was the Incremental-Delta-
Bar-Delta (IDBD) algorithm, proposed in (Sutton, 1992), aiming to optimize the
step-size vector to minimize a special form of quadratic loss functions in the
continual setting. This algorithm was then extended in (Xu et al., 2018) for
use in neural networks, and in (Mahmood et al., 2012) (respectively (Javed,
2020)) for some specific meta update (respectively base update) other than
SGD. However, the development of IDBD and its extensions included some
implicit assumptions, notably overlooking the impact of step-size dynamics on
the formulation of step-size update rules. Our paper extends the IDBD
research, significantly broadening the framework and establishing a solid
basis for the derivations. IDBD and its extensions have been used in various
machine learning tasks including independent component analysis (Schraudolph &
Giannakopoulos, 1999), human motion tracking (Kehl & Van Gool, 2006),
classification (Koop, 2007; Andrychowicz et al., 2016), and reinforcement
learning (Xu et al., 2018; Young et al., 2018). Refer to (Sutton, 2022) for a
comprehensive history of step-size optimization.

There is also a line of research on the so-called parameter-free optimization
that aims to remove the need for step-size tuning with almost no knowledge of
the problem properties. Most of these methods are primarily designed for
stochastic convex optimization (Luo & Schapire, 2015; Orabona & Pál, 2016),
while more recent ones (Orabona & Tommasi, 2017; Ivgi et al., 2023) were
applied to supervised learning tasks with small or moderate sample sizes.

##  9 Limitations and Future Works

Our work represents a step toward unlocking the potential of meta-parameter
optimization, with substantial room for further exploration, some of which we
outline here:
Hessian: We confined our experiments to Hessian-free methods for practicality,
though Hessian-based algorithms could offer superior performance. These
methods, however, face challenges requiring additional research. The Hessian
matrix is notably noisy, impacting $\mathcal{H}_{t+1}$ multiplicatively,
necessitating smoothing and clipping techniques. Additionally, the Hessian
approximates the loss landscape’s curvature but fails to account for non-
differentiable curvatures, such as those from ReLU unit breakpoints,
significant at training’s end. From a computational perspective, developing
low-complexity methods for approximate Hessian matrix products, especially for
adjusting step-sizes at the layer and weight levels, is essential.

Blockwise step-sizes: While step sizes can vary much in granularity, our
experiments focused on scalar and blockwise step-sizes. While increasing the
number of step sizes is anticipated to enhance performance, our experimental
findings in Section 7 reveal that this improvement is not consistent across
the MetaOptimize approximations evaluated. Further investigation is needed in
future research.

Other approximations: We explored a limited set of MetaOptimize’s possible
approximations, leaving a comprehensive analysis of various approximations for
future research.

Other meta-parameters: Our study was limited to differentiable meta-
parameters, not covering discrete ones like batch size or network layer count.
We also did not investigate several significant differentiable meta-parameters
beyond step-sizes, deferring such exploration to future work.

Continual learning: Although continual step-size optimization is primarily
aimed at continual learning, this study focused on the stationary case,
demonstrating MetaOptimize’s competitiveness in a context that is particularly
challenging for it. Investigating the framework within continual learning
presents a promising direction for future research.

##  10 Acknowledgments

The authors want to thank Csaba Szepesvári and Khurram Javed for for providing
feedback on earlier versions of this work.

##  11 Potential Broader Impact

This paper presents work whose goal is to advance the field of machine
learning. There are many potential societal consequences of our work, none of
which we feel must be specifically highlighted here.

## References

  * Amid et al. (2022) Amid, E., Anil, R., Fifty, C., and Warmuth, M. K.  Step-size adaptation using exponentiated gradient updates.  _arXiv preprint arXiv:2202.00145_ , 2022.
  * Andrychowicz et al. (2016) Andrychowicz, M., Denil, M., Gomez, S., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., and De Freitas, N.  Learning to learn by gradient descent by gradient descent.  _Advances in neural information processing systems_ , 29, 2016.
  * Asi & Duchi (2019) Asi, H. and Duchi, J. C.  The importance of better models in stochastic optimization.  _Proceedings of the National Academy of Sciences_ , 116(46):22924–22930, 2019.
  * Baydin et al. (2017) Baydin, A. G., Cornish, R., Rubio, D. M., Schmidt, M., and Wood, F.  Online learning rate adaptation with hypergradient descent.  _arXiv preprint arXiv:1703.04782_ , 2017.
  * Berrada et al. (2020) Berrada, L., Zisserman, A., and Kumar, M. P.  Training neural networks for and by interpolation.  In _International conference on machine learning_ , pp. 799–809. PMLR, 2020.
  * Chandra et al. (2022) Chandra, K., Xie, A., Ragan-Kelley, J., and Meijer, E.  Gradient descent: The ultimate optimizer.  _Advances in Neural Information Processing Systems_ , 35:8214–8225, 2022.
  * Chen et al. (2023) Chen, X., Liang, C., Huang, D., Real, E., Wang, K., Liu, Y., Pham, H., Dong, X., Luong, T., Hsieh, C., et al.  Symbolic discovery of optimization algorithms. arxiv 2023.  _arXiv preprint arXiv:2302.06675_ , 2023.
  * Dahl et al. (2023) Dahl, G. E., Schneider, F., Nado, Z., Agarwal, N., Sastry, C. S., Hennig, P., Medapati, S., Eschenhagen, R., Kasimbeg, P., Suo, D., et al.  Benchmarking neural network training algorithms.  _arXiv preprint arXiv:2306.07179_ , 2023.
  * De Lange et al. (2021) De Lange, M., Aljundi, R., Masana, M., Parisot, S., Jia, X., Leonardis, A., Slabaugh, G., and Tuytelaars, T.  A continual learning survey: Defying forgetting in classification tasks.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(7):3366–3385, 2021.
  * Degris et al. (2024) Degris, T., Javed, K., Sharifnassab, A., Liu, Y., and Sutton, R.  Step-size optimization for continual learning, 2024.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Duchi et al. (2011) Duchi, J., Hazan, E., and Singer, Y.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of machine learning research_ , 12(7), 2011.
  * Eldan & Li (2023) Eldan, R. and Li, Y.  Tinystories: How small can language models be and still speak coherent english?  _arXiv preprint arXiv:2305.07759_ , 2023.
  * Hinton et al. (2012) Hinton, G., Srivastava, N., and Swersky, K.  Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.  _Cited on_ , 14(8):2, 2012.
  * Howard & Ruder (2018) Howard, J. and Ruder, S.  Universal language model fine-tuning for text classification.  _arXiv preprint arXiv:1801.06146_ , 2018.
  * Ivgi et al. (2023) Ivgi, M., Hinder, O., and Carmon, Y.  Dog is sgd’s best friend: A parameter-free dynamic step size schedule.  _arXiv preprint arXiv:2302.12022_ , 2023.
  * Jacobs (1988) Jacobs, R. A.  Increased rates of convergence through learning rate adaptation.  _Neural networks_ , 1(4):295–307, 1988.
  * Javed (2020) Javed, K.  Step-size adaptation for rmsprop.  _Technical Report_ , 2020.  URL https://khurramjaved.com/reports/idbd_rmsprop.pdf.
  * Jin (2022) Jin, H.  Hyperparameter importance for machine learning algorithms.  _arXiv preprint arXiv:2201.05132_ , 2022.
  * Karpathy (2024) Karpathy, A.  llama2.c: Inference llama 2 in one file of pure c.  https://github.com/karpathy/llama2.c, 2024.  GitHub repository.
  * Kehl & Van Gool (2006) Kehl, R. and Van Gool, L.  Markerless tracking of complex human motions from multiple views.  _Computer Vision and Image Understanding_ , 104(2-3):190–209, 2006.
  * Kesten (1958) Kesten, H.  Accelerated stochastic approximation.  _The Annals of Mathematical Statistics_ , pp. 41–59, 1958.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Koop (2007) Koop, A.  _Investigating Experience: Temporal Coherence and Empirical Knowledge Representation. University of Alberta MSc_.  PhD thesis, thesis, 2007.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kunstner et al. (2023) Kunstner, F., Portella, V. S., Schmidt, M., and Harvey, N.  Searching for optimal per-coordinate step-sizes with multidimensional backtracking.  _arXiv preprint arXiv:2306.02527_ , 2023.
  * Loizou et al. (2021) Loizou, N., Vaswani, S., Laradji, I. H., and Lacoste-Julien, S.  Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 1306–1314. PMLR, 2021.
  * Luo & Schapire (2015) Luo, H. and Schapire, R. E.  Achieving all with no parameters: Adanormalhedge.  In _Conference on Learning Theory_ , pp. 1286–1304. PMLR, 2015\.
  * Mahmood et al. (2012) Mahmood, A. R., Sutton, R. S., Degris, T., and Pilarski, P. M.  Tuning-free step-size adaptation.  In _2012 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , pp. 2121–2124. IEEE, 2012.
  * Orabona & Pál (2016) Orabona, F. and Pál, D.  Coin betting and parameter-free online learning.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Orabona & Tommasi (2017) Orabona, F. and Tommasi, T.  Training deep networks without learning rates through coin betting.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Paquette & Scheinberg (2020) Paquette, C. and Scheinberg, K.  A stochastic line search method with expected complexity analysis.  _SIAM Journal on Optimization_ , 30(1):349–376, 2020.
  * Pearlmutter (1994) Pearlmutter, B. A.  Fast exact multiplication by the hessian.  _Neural computation_ , 6(1):147–160, 1994.
  * Rolinek & Martius (2018) Rolinek, M. and Martius, G.  L4: Practical loss-based stepsize adaptation for deep learning.  _Advances in neural information processing systems_ , 31, 2018.
  * Schaul et al. (2013) Schaul, T., Zhang, S., and LeCun, Y.  No more pesky learning rates.  In _International conference on machine learning_ , pp. 343–351. PMLR, 2013.
  * Schraudolph & Giannakopoulos (1999) Schraudolph, N. and Giannakopoulos, X.  Online independent component analysis with local learning rate adaptation.  _Advances in neural information processing systems_ , 12, 1999.
  * Singh et al. (2015) Singh, B., De, S., Zhang, Y., Goldstein, T., and Taylor, G.  Layer-specific adaptive learning rates for deep networks.  In _2015 IEEE 14th International Conference on Machine Learning and Applications (ICMLA)_ , pp. 364–368. IEEE, 2015.
  * Sutton (1982) Sutton, R.  A theory of salience change dependent on the relationship between discrepancies on successive trials on which the stimulus is present.  _Unpublished working paper_ , 1982.
  * Sutton (1981) Sutton, R. S.  Adaptation of learning rate parameters.  In _Goal Seeking Com- ponents for Adaptive Intelligence: An Initial Assessment_. by A. G. Barto and R. S. Sutton. Air Force Wright Aeronautical Laboratories Technical Report AFWAL- TR-81-1070. Wright-Patterson Air Force Base, Ohio 45433., 1981.
  * Sutton (1988) Sutton, R. S.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3:9–44, 1988.
  * Sutton (1992) Sutton, R. S.  Adapting bias by gradient descent: An incremental version of delta-bar-delta.  In _AAAI_ , volume 92, pp. 171–176. San Jose, CA, 1992.
  * Sutton (2022) Sutton, R. S.  A history of meta-gradient: Gradient methods for meta-learning.  _arXiv preprint arXiv:2202.09701_ , 2022.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Vaswani et al. (2019) Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., and Lacoste-Julien, S.  Painless stochastic gradient: Interpolation, line-search, and convergence rates.  _Advances in neural information processing systems_ , 32, 2019.
  * Xu et al. (2018) Xu, Z., van Hasselt, H. P., and Silver, D.  Meta-gradient reinforcement learning.  _Advances in neural information processing systems_ , 31, 2018.
  * Young et al. (2018) Young, K., Wang, B., and Taylor, M. E.  Metatrace: Online step-size tuning by meta-gradient descent for reinforcement learning control.  _arXiv preprint arXiv:1805.04514_ , 2018.

Appendices

##  Appendix A Step-size Optimization for Different Choices of Base and Meta
updates

In this appendix, we derive $G_{t}$ defined in (10) for different choices of
algorithms for base and meta updates, and propose corresponding step-size
optimization algorithms.

Consider the following partitions of $G_{t}$,

$G^{\textrm{meta}}_{t}\overset{\text{\tiny
def}}{=}\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (18)
$G^{\textrm{base}}_{t}\overset{\text{\tiny
def}}{=}\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (19)

Then,

$G_{t}={\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\right]}=\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{G^{\textrm{meta}}_{t}}\\\ \vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {G^{\textrm{base}}_{t}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (20)

In the sequel, we study base and meta updates separately, because
$\operatorname{Alg}_{\textrm{base}}$ and $\operatorname{Alg}_{\textrm{meta}}$
impact disjoint sets of blocks in $G_{t}$. In particular, as we will see, the
choice of $\operatorname{Alg}_{\textrm{base}}$ only affects
$G^{\textrm{base}}$ while the choice of $\operatorname{Alg}_{\textrm{meta}}$
only affects $G^{\textrm{meta}}$.

Before delving into computing $G^{\textrm{base}}_{t}$ and
$G^{\textrm{meta}}_{t}$ for different base and meta algorithms, we further
simplify these matrices.

###  A.1 Derivation of $G^{\textrm{meta}}$ for Different Meta Updates

We start by simplifying $G^{\textrm{meta}}$, and introducing some notations.

Note that the meta update has no dependence on internal variables,
$\tilde{\boldsymbol{x}}$, of the base algorithm. As a result,

$\frac{d\,\boldsymbol{y}_{t+1}}{d\,\tilde{\boldsymbol{x}}_{t}}=0.$ (21)

Then,

$G^{\textrm{meta}}_{t}=\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\tilde{\boldsymbol{x}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (22)

where the third equality is due to (21). Let

$L_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{c|c|c|c}\quad\nabla
f_{t}(\boldsymbol{w}_{t})^{T}&0&0&0\\\ \hline\cr
0&\begin{array}[]{c}\vspace{-9pt}\hfil\\\ \quad\nabla
f_{t}(\boldsymbol{w}_{t})^{T}\end{array}&0&0\\\ \hline\cr
0&0&\begin{array}[]{c}\vspace{-4pt}\hfil\\\ \quad\ddots\\\
\vspace{-4pt}\hfil\\\ \end{array}&0\\\ \hline\cr
0&0&0&\begin{array}[]{c}\vspace{-9pt}\hfil\\\ \quad\nabla
f_{t}(\boldsymbol{w}_{t})^{T}\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>1}\end{array}\\\ \begin{array}[]{c}\vspace{-9pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>2}\end{array}\\\ \begin{array}[]{c}\vspace{-4pt}\hfil\\\
\,\,{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\vspace{-4pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-9pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>m}\end{array}\end{array}$ (23)

and recall that $\boldsymbol{h}_{t}$ is a vectorization of $\mathcal{H}_{t}$.
Then,

$\mathcal{H}_{t}\nabla f_{t}(\boldsymbol{w}_{t})=L_{t}\boldsymbol{h}_{t}.$
(24)

We now proceed to derivation of $G^{\textrm{meta}}$ for different choices of
$\operatorname{Alg}_{\textrm{meta}}$.

####  A.1.1 Meta SGD

Here, we consider SGD for the meta update (9),

$\boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}-\eta\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}=\boldsymbol{\beta}_{t}-\eta\,\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t}),$ (25)

where $\eta$ is a scalar, called the _meta step size_. In this case,
$\boldsymbol{y}_{t}=\boldsymbol{\beta}_{t}$. It then follows from (25) that

$\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{h}_{t}}\,=\,-\eta\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}\,=\,-\eta\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}L_{t}\boldsymbol{h}_{t}\big{)}\,=\,-\eta
L_{t},$ (26)

where the second equality is due to (24). Consequently, from (22), we obtain

$\begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {I}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{-\eta\mathcal{H}^{T}_{t}\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{0}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {-\eta L_{t}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],\end{split}$ (27)

where the last inequality follows from (26) and simple differentiations of
(25). Here, $\nabla^{2}f_{t}(\boldsymbol{w}_{t})$ denotes the Hessian of
$f_{t}$ at $\boldsymbol{w}_{t}$.

####  A.1.2 Meta Adam

The meta update based on the Adam algorithm is as follows,

$\begin{split}\bar{\boldsymbol{m}}_{t+1}&=\bar{\rho}\,\bar{\boldsymbol{m}}_{t}\,+\,\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t}),\\\
\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}&=\bar{\lambda}\,\boldsymbol{v}_{t}\,+\,\big{(}\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}^{2},\\\
\bar{\mu}_{t}&=\left(\frac{1-\bar{\rho}}{{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1-\bar{\rho}^{t}}}\right)\,/\,\sqrt{\frac{1-\bar{\lambda}}{1-\bar{\lambda}^{t}}},\\\
\boldsymbol{\beta}_{t+1}&=\boldsymbol{\beta}_{t}\,-\,\eta\,\bar{\mu}_{t}\frac{\bar{\boldsymbol{m}}_{t}}{\sqrt{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\end{split}$
(28)

where $\bar{\boldsymbol{m}}_{t}$ is the momentum vector,
$\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}$ is the trace of squared
surrogate-meta-gradient. Since Adam algorithm needs to keep track of
$\boldsymbol{\beta}_{t}$, $\bar{\boldsymbol{m}}_{t}$, and
$\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}$, we have

$\boldsymbol{y}_{t}=\left[\begin{array}[]{c}\boldsymbol{\beta}_{t}\\\
\bar{\boldsymbol{m}}_{t}\\\
\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}\end{array}\right].$ (29)

Recall the following notation convention at the end of the Introduction
section: for any $k\geq 1$, and any $k$-dimensional vector
$\boldsymbol{v}=[v_{1},\ldots,v_{k}]$, we denote the the corresponding
diagonal matrix by $\left[\boldsymbol{v}\right]$:

$\left[\boldsymbol{v}\right]\overset{\text{\tiny
def}}{=}\left[\begin{array}[]{ccc}v_{1}&\cdots&0\\\ \vdots&\ddots&\vdots\\\
0&\cdots&v_{k}\end{array}\right].$ (30)

Consequently, from (22), we obtain

$\begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{c|cc|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccc|cc|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccc|cc|c}I&-\eta\bar{\mu}_{t}\Big{[}\frac{1}{\sqrt{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\Big{]}&\frac{\eta\bar{\mu}_{t}}{2}\Big{[}\frac{\bar{\boldsymbol{m}}_{t}}{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}^{1.5}}\Big{]}&0&0&0\\\
0&\bar{\rho}I&0&\mathcal{H}_{t}^{T}\nabla^{2}f_{t}&0&\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{h}_{t}}\\\
0&0&\bar{\lambda}I&2\big{[}\mathcal{H}_{t}^{T}\nabla
f_{t}\big{]}\mathcal{H}_{t}^{T}\nabla^{2}f_{t}&0&\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}}{d\,\boldsymbol{h}_{t}}\end{array}\right],\end{split}$
(31)

where the last equality follows by calculating derivatives of (28). For the
two remaining terms in the last column of $G_{t}$, we have

$\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{h}_{t}}\,=\,\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}\,=\,\eta\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}L_{t}\boldsymbol{h}_{t}\big{)}\,=\eta\,L_{t}.$
(32)

where the first equality follows from the update of
$\bar{\boldsymbol{m}}_{t+1}$ in (28), and the second equality is due to (24).
In the same vein,

$\frac{d\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}}{d\,\boldsymbol{h}_{t}}\,=\,\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}^{2}\,=\,\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}L_{t}\boldsymbol{h}_{t}\big{)}^{2}\,=\,2\big{[}L_{t}\boldsymbol{h}_{t}\big{]}\frac{d}{d\,\boldsymbol{h}_{t}}\big{(}L_{t}\boldsymbol{h}_{t}\big{)}\,=\,2\big{[}L_{t}\boldsymbol{h}_{t}\big{]}\,L_{t}\,=\,2\big{[}\mathcal{H}_{t}^{T}\,\nabla
f_{t}(\boldsymbol{w}_{t})\big{]}\,L_{t},$ (33)

where the first equality follows from the update of
$\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}$ in (28), the second
equality is due to (24), and the last equality is again from (24).

Plugging (32) and (33) into (31), we obtain

$G^{\textrm{meta}}_{t}=\left[\begin{array}[]{ccc|cc|c}I&-\eta\bar{\mu}_{t}\Big{[}\frac{1}{\sqrt{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\Big{]}&\frac{\eta\bar{\mu}_{t}}{2}\Big{[}\frac{\bar{\boldsymbol{m}}_{t}}{\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}^{1.5}}\Big{]}&0&0&0\\\
0&\bar{\rho}I&0&\mathcal{H}_{t}^{T}\nabla^{2}f_{t}&0&\eta\,L_{t}\\\
0&0&\bar{\lambda}I&2\big{[}\mathcal{H}_{t}^{T}\nabla
f_{t}\big{]}\mathcal{H}_{t}^{T}\nabla^{2}f_{t}&0&2\big{[}\mathcal{H}_{t}^{T}\,\nabla
f_{t}\big{]}\,L_{t}\end{array}\right].$ (34)

####  A.1.3 Meta Lion

The meta update based on the lion algorithm is as follows

$\displaystyle\bar{\boldsymbol{m}}_{t+1}=\rho\,\bar{\boldsymbol{m}}_{t}+(1-\rho)\,\widehat{\nabla_{\boldsymbol{\beta}}F}_{t},$
(35)
$\displaystyle\boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}-\eta\operatorname{Sign}\big{(}c\,\bar{\boldsymbol{m}}_{t}+(1-c)\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}\big{)},$
(36)

where $\eta$ is a scalar, called the _meta step size_ , and $\rho,c\in[0,1)$.
Note that the meta algorithm operates on a low dimensional space. Therefore,
we drop the regularizers like weight-decay in the meta updates, as they are
primarily aimed to resolve the overfitting problem in high dimensional
problems. Substituting $\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}$ with
$\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})$ we obtain the following
meta updates

$\displaystyle\bar{\boldsymbol{m}}_{t+1}=\rho\,\bar{\boldsymbol{m}}_{t}+(1-\rho)\,\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t}),$ (37)
$\displaystyle\boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}-\eta\operatorname{Sign}\big{(}c\,\bar{\boldsymbol{m}}_{t}+(1-c)\mathcal{H}_{t}^{T}\nabla
f_{t}(\boldsymbol{w}_{t})\big{)}.$ (38)

In this case,

$\boldsymbol{y}_{t}=\left[\begin{array}[]{c}\boldsymbol{\beta}_{t}\\\
\bar{\boldsymbol{m}}_{t}\end{array}\right],$

and

$\begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{ccccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{\beta}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {I}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{0}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {0}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{0}\\\ \vspace{-10pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],\end{split}$ (39)

where the last equality follows from (38). Consider the following block
representation of $Y_{t}$:

$Y_{t}=\left[\begin{array}[]{c}B_{t}\\\ Y^{\bar{m}}_{t}\end{array}\right].$
(40)

Since the base algorithm, does not take $\bar{\boldsymbol{m}}$ as input, as we
will see in (42) and (43) of next subsection (Appendix A.2),
$\frac{d\,\bar{\boldsymbol{m}}_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}$ is the
only non-zero block of $G_{t}$ in its column of blocks (i.e.,
$\frac{d\,s_{t+1}}{d\,\bar{\boldsymbol{m}}_{t}}=0$ for every variable $s$
other than $\bar{\boldsymbol{m}}$). Consequently, it follows from (15) that
$Y^{\bar{m}}_{t}$ as defined in (40), has no impact on the update of
$X_{t+1}$, $B_{t+1}$, and $Q_{t+1}$. Therefore, we can zero-out the rows and
columns of $G^{\textrm{meta}}$ that correspond to derivative of
$\bar{\boldsymbol{m}}$. As such we obtain the following equivalent of
$G^{\textrm{meta}}$ in (39) from an algorithmic perspective:

$\begin{split}G^{\textrm{meta}}_{t}\equiv\left[\begin{array}[]{cc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{I_{m\times m}}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {0}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{0}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {0}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].\end{split}$ (41)

As a result, we get $B_{t}=I$ for all times $t$.

###  A.2 Derivation of $G^{\textrm{base}}$ for Different Base Updates

We now turn our focus to computation of $G^{\textrm{base}}$ . Let us start by
simplifying $G^{\textrm{base}}$, and introducing some notations.

Note that the base update has no dependence on internal variables,
$\tilde{\boldsymbol{y}}$, of the meta update. As a result,

$\frac{d\,\boldsymbol{x}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}=0.$ (42)

Moreover, it follows from the definition of $\mathcal{H}_{t}$ in (8) that

$\frac{d\,\mathcal{H}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{d}{d\tilde{\boldsymbol{y}}_{t}}\,\left(\frac{d\boldsymbol{w}_{t+1}}{d\,\boldsymbol{\beta}_{\tau}}\right)=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{d}{d\boldsymbol{\beta}_{\tau}}\,\left(\frac{d\boldsymbol{w}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}\right)=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{d}{d\boldsymbol{\beta}_{\tau}}\,\left(0\right)=0,$

where the third equality follows from (42). Therefore,

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}=0.$ (43)

Note also that $\operatorname{Alg}_{\textrm{base}}$ does not take
$\mathcal{H}_{t}$ as input, and therefore,

$\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}=0.$ (44)

Consequently, we can simplify $G^{\textrm{base}}_{t}$ as follows,

$G^{\textrm{base}}_{t}=\left[\begin{array}[]{ccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\tilde{\boldsymbol{y}}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (45)

where the last equality is due to (42), (43), and (44).

On an independent note, consider the following block representation of
$Y_{t}$,

$Y_{t}=\left[\begin{array}[]{c}B_{t}-\frac{1-\gamma}{\gamma}I\\\
\tilde{Y}_{t}\end{array}\right],$ (46)

Therefore,

$\gamma Y_{t}+(1-\gamma)\left[\begin{array}[]{c}I\\\
0\end{array}\right]=\left[\begin{array}[]{c}B_{t}\\\
\tilde{Y}_{t}\end{array}\right]$

It then follows from (20) and (15) that

$\left[\begin{array}[]{c}X_{t+1}\\\
Q_{t+1}\end{array}\right]=\gamma\,G^{\textrm{base}}_{t}\left[\begin{array}[]{c}\left[\begin{array}[]{c}B_{t}\\\
\tilde{Y}_{t}\end{array}\right]\\\ X_{t}\\\ Q_{t}\end{array}\right].$ (47)

Moreover, from the definition of $Y_{t}$ in (12), we have

$\begin{split}\frac{d\,B_{t}}{d\,\boldsymbol{x}_{t}}&=(1-\gamma)\frac{d}{d\,\boldsymbol{x}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\left(\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{x}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\big{(}0\big{)}=0,\\\
\frac{d\,B_{t}}{d\,\boldsymbol{\beta}_{t}}&=(1-\gamma)\frac{d}{d\,\boldsymbol{\beta}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\left(\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{\beta}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\big{(}I\big{)}=0,\\\
\frac{d\,B_{t}}{d\,\boldsymbol{h}_{t}}&=(1-\gamma)\frac{d}{d\,\boldsymbol{h}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\left(\frac{d\,\boldsymbol{\beta}_{t}}{d\,\boldsymbol{h}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{d}{d\,\boldsymbol{\beta}_{\tau}}\big{(}0\big{)}=0.\end{split}$
(48)

Finally, recall the definition

$\sigma^{\prime}(\boldsymbol{\beta}_{t})\overset{\text{\tiny
def}}{=}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\boldsymbol{\beta}_{t}}$ (49)

as the Jacobian of $\boldsymbol{\alpha}_{t}$ with respect to
$\boldsymbol{\beta}_{t}$.

We now proceed to derivation of $G^{\textrm{base}}$ for different choices of
$\operatorname{Alg}_{\textrm{base}}$.

###  A.3 Base SGD

Base SGD algorithm makes the following base update in each iteration:

$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\nabla
f_{t}(\boldsymbol{w}_{t}).$ (50)

In this case, $\boldsymbol{x}_{t}=\boldsymbol{w}_{t}$ and
$X_{t}=\mathcal{H}_{t}$. Then, $G^{\textrm{base}}_{t}$ in (45) can be
simplified to

$\begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cccc}-\left[\nabla
f_{t}(\boldsymbol{w}_{t})\right]\sigma^{\prime}(\boldsymbol{\beta}_{t})&0&I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}(\boldsymbol{w}_{t})&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],\end{split}$ (51)

where the last equality follows by computing simple derivatives of
$\boldsymbol{w}_{t+1}$ in (50).

We proceed to compute the three remaining entries of $G^{\textrm{base}}_{t}$,
i.e., ${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{\beta}_{t}}$,
${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{w}_{t}}$, and
${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{h}_{t}}$. Note that by plugging the
first row of $G^{\textrm{base}}_{t}$, given in (51), into (47), and noting
that $\mathcal{H}_{t}=X_{t}$, we obtain

$\mathcal{H}_{t+1}=\gamma\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}(\boldsymbol{w}_{t})\big{)}\mathcal{H}_{t}\,-\,\gamma\left[\nabla
f_{t}(\boldsymbol{w}_{t})\right]\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t},$
(52)

for all $t\geq 0$. By vectorizing both sides of (52) we obtain

$\boldsymbol{h}_{t+1}\,=\,\gamma\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}\big{)}\,\mathcal{H}_{t}^{[1]}\,-\,\left[\nabla
f_{t}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}\big{)}\,\mathcal{H}_{t}^{[2]}\,-\,\left[\nabla
f_{t}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[2]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}\big{)}\,\mathcal{H}_{t}^{[m]}\,-\,\left[\nabla
f_{t}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (53)

Note that for any pair of same-size vectors $\boldsymbol{a}$ and
$\boldsymbol{b}$, we have
$\left[\boldsymbol{a}\right]\boldsymbol{b}=\left[\boldsymbol{b}\right]\boldsymbol{a}$
where $\left[\boldsymbol{a}\right]$ and $\left[\boldsymbol{b}\right]$ are
diagonal matrices of $\boldsymbol{a}$ and $\boldsymbol{b}$, respectively.
Therefore, (53) can be equivalently written in the following form

$\boldsymbol{h}_{t+1}\,=\,\gamma\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}\big{)}\,\mathcal{H}_{t}^{[1]}\,-\,\big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}\big{]}\,\nabla
f_{t}}\\\ \vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{(}I-\left[\boldsymbol{\alpha}_{t}\right]\nabla^{2}f_{t}\big{)}\,\mathcal{H}_{t}^{[m]}\,-\,\big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}\big{]}\,\nabla
f_{t}}\\\ \vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (54)

By taking the derivative of (53) with respect to $\boldsymbol{h}_{t}$, we
obtain

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}=\gamma\,\left[\begin{array}[]{c|c|c|c}\begin{array}[]{c}I-\left[\boldsymbol{\alpha}_{t}\right]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})\\\
\vspace{-6pt}\hfil\\\ \end{array}&0&0&0\\\ \hline\cr
0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\left[\boldsymbol{\alpha}_{t}\right]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})\\\
\vspace{-6pt}\hfil\\\ \end{array}&0&0\\\ \hline\cr
0&0&\begin{array}[]{c}\vspace{-4pt}\hfil\\\ \ddots\\\ \vspace{-4pt}\hfil\\\
\end{array}&0\\\ \hline\cr 0&0&0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\left[\boldsymbol{\alpha}_{t}\right]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>1\textrm{st}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>2\textrm{nd}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-4pt}\hfil\\\
\,\,{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\vspace{-4pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>m\textrm{th}}\end{array}\end{array}.$ (55)

In the above equation, note that $d\,B_{t}/d\,\boldsymbol{h}_{t}=0$ due to
(48). Let $\beta_{t}[i]$ and $w_{t}[j]$ denote the $i$th and $j$th entries of
$\boldsymbol{\beta}_{t}$ and $\boldsymbol{w}_{t}$, for $i=1,\ldots,m$ and
$j=1,\ldots,n$, respectively. It then follows from (53) and (48) that

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[1]}\Big{]}\nabla^{2}f_{t}\,\mathcal{H}_{t}^{[1]}\,+\,\left[\nabla
f_{t}\right]\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[1]}\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\cdots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[m]}\Big{]}\nabla^{2}f_{t}\,\mathcal{H}_{t}^{[1]}\,+\,\left[\nabla
f_{t}\right]\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[{m}]}\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\ddots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[1]}\Big{]}\nabla^{2}f_{t}\,\mathcal{H}_{t}^{[m]}\,+\,\left[\nabla
f_{t}\right]\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[1]}\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\cdots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[m]}\Big{]}\nabla^{2}f_{t}\,\mathcal{H}_{t}^{[m]}\,+\,\left[\nabla
f_{t}\right]\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[{m}]}\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (56)

where $\frac{\partial}{\partial\beta}$ stands for the entry-wise partial
derivative of a matrix with respect to a scalar variable $\beta$. In the same
vein, (54) and (48) imply that

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}=-\gamma\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{\alpha}_{t}\right]\frac{d\,(\nabla^{2}f_{t}(\boldsymbol{w}_{t})\,\mathcal{H}_{t}^{[1]})}{d\,\boldsymbol{w}_{t}}\,+\,\big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}\big{]}\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{\alpha}_{t}\right]\frac{d\,(\nabla^{2}f_{t}(\boldsymbol{w}_{t})\,\mathcal{H}_{t}^{[{m}]})}{d\,\boldsymbol{w}_{t}}\,+\,\big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}\big{]}\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (57)

Finally, $G^{\textrm{base}}_{t}$ is obtained by plugging (55), (56), and (57)
into (51).

In the special case that $\boldsymbol{\beta}$ is a scalar (equivalently
$m=1$), and furthermore $\alpha=\sigma(\beta)=e^{\beta}$, matrix
$G^{\textrm{base}}_{t}$ would be simplified to

$G_{t}^{\textrm{base
(scalar)}}=\left[\begin{array}[]{cccc}\vspace{6pt}1&-\eta\,\boldsymbol{h}_{t}^{T}\nabla^{2}f_{t}(\boldsymbol{w}_{t})&-\eta\,\nabla
f_{t}(\boldsymbol{w}_{t})^{T}\\\ \vspace{6pt}-\alpha\nabla
f_{t}(\boldsymbol{w}_{t})&I-\alpha\nabla^{2}f_{t}(\boldsymbol{w}_{t})&0\\\
-\gamma\alpha\nabla^{2}f_{t}(\boldsymbol{w}_{t})\boldsymbol{h}_{t}-B_{t}\,\alpha\nabla
f_{t}(\boldsymbol{w}_{t})&\quad-\gamma\alpha\frac{d\,\left(\nabla^{2}f_{t}(\boldsymbol{w}_{t})\boldsymbol{h}_{t}\right)}{d\boldsymbol{w}_{t}}-B_{t}\,\alpha\nabla^{2}f_{t}(\boldsymbol{w}_{t})&\gamma\big{(}I-\alpha\nabla^{2}f_{t}(\boldsymbol{w}_{t})\big{)}\end{array}\right].$

####  A.3.1 Base AdamW

The base update according to the AdamW algorithm (Loizou et al., 2021) is as
follows,

$\begin{split}\boldsymbol{m}_{t+1}&=\rho\,\boldsymbol{m}_{t}\,+\,\nabla
f_{t}(\boldsymbol{w}_{t}),\\\
\boldsymbol{v}_{t+1}&=\lambda\,\boldsymbol{v}_{t}\,+\,\nabla
f_{t}(\boldsymbol{w}_{t})^{2},\\\
\mu_{t}&=\left(\frac{1-\rho}{{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color@gray@fill{.75}1-\rho^{t}}}\right)\,/\,\sqrt{\frac{1-\lambda}{1-\lambda^{t}}},\\\
\boldsymbol{w}_{t+1}&=\boldsymbol{w}_{t}\,-\,\boldsymbol{\alpha}_{t}\mu_{t}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t},\end{split}$
(58)

where $\boldsymbol{m}_{t}$ is the momentum vector, $\boldsymbol{v}_{t}$ is the
trace of gradient square used for normalization, and $\kappa>0$ is a weight-
decay parameter. Therefore the base algorithm needs to keep track of
$\boldsymbol{w}_{t},\boldsymbol{m}_{t},\boldsymbol{v}_{t}$, i.e.,

$\boldsymbol{x}_{t}=\left[\begin{array}[]{c}\boldsymbol{w}_{t}\\\
\hfill\boldsymbol{m}_{t}\\\ \boldsymbol{v}_{t}\end{array}\right].$ (59)

It then follows from (45) that

$\begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cc|ccc|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{m}_{t}}&\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{v}_{t}}&0\\\
\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{\beta}_{t}}&0&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{w}_{t}}&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{m}_{t}}&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{v}_{t}}&0\\\
\frac{d\,\boldsymbol{v}_{t+1}}{d\,\boldsymbol{\beta}_{t}}&0&\frac{d\,\boldsymbol{v}_{t+1}}{d\,\boldsymbol{w}_{t}}&\frac{d\,\boldsymbol{v}_{t+1}}{d\,\boldsymbol{m}_{t}}&\frac{d\,\boldsymbol{v}_{t+1}}{d\,\boldsymbol{v}_{t}}&0\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{v}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{cc|ccc|c}-\mu_{t}\Big{[}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}+\kappa\boldsymbol{w}_{t}\Big{]}\sigma^{\prime}(\boldsymbol{\beta}_{t})&0&I-\kappa\left[\boldsymbol{\alpha}_{t}\right]&-\mu_{t}\Big{[}\frac{\boldsymbol{\alpha}_{t}}{\sqrt{\boldsymbol{v}_{t}}}\Big{]}&\frac{\mu_{t}}{2}\Big{[}\frac{\boldsymbol{\alpha}_{t}\boldsymbol{m}_{t}}{\boldsymbol{v}_{t}^{1.5}}\Big{]}&0\\\
0&0&\nabla^{2}f_{t}&\rho I&0&0\\\ 0&0&2\left[\nabla
f_{t}\right]\,\nabla^{2}f_{t}&0&\lambda I&0\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{v}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\end{split}$ (60)

where the last equality follows from simple derivative computations in (58).

We proceed to compute the terms in the last row of the $G^{\textrm{base}}_{t}$
above. Consider the following block representation of $X_{t}$,

$X_{t}=\left[\begin{array}[]{c}\mathcal{H}_{t}\\\ \hfill X^{m}_{t}\\\
X^{v}_{t}\end{array}\right],$ (61)

Plugging the first row of $G^{\textrm{base}}_{t}$, given in (60), into (47),
implies that

$\mathcal{H}_{t+1}=-\gamma\mu_{t}\Big{[}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}+\kappa\boldsymbol{w}_{t}\Big{]}\sigma^{\prime}(\boldsymbol{\beta}_{t})B_{t}\,+\,\gamma\big{(}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big{)}\mathcal{H}_{t}\,-\,\gamma\mu_{t}\Big{[}\frac{\boldsymbol{\alpha}_{t}}{\sqrt{\boldsymbol{v}_{t}}}\Big{]}\,X^{m}_{t}\,+\,\gamma\frac{\mu_{t}}{2}\Big{[}\frac{\boldsymbol{\alpha}_{t}\boldsymbol{m}_{t}}{\boldsymbol{v}_{t}^{1.5}}\Big{]}\,X^{v}_{t}.$
(62)

for all $t\geq 0$. Note that for any pair of same-size vectors
$\boldsymbol{a}$ and $\boldsymbol{b}$, we have
$\left[\boldsymbol{a}\right]\boldsymbol{b}=\left[\boldsymbol{b}\right]\boldsymbol{a}$
where $\left[\boldsymbol{a}\right]$ and $\left[\boldsymbol{b}\right]$ are
diagonal matrices of $\boldsymbol{a}$ and $\boldsymbol{b}$, respectively.
Therefore, the $i$th column in the matrix equation (62) can be equivalently
written as

$\mathcal{H}^{[i]}_{t+1}=-\gamma\mu_{t}\Big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[i]}_{t}\Big{]}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}+\kappa\boldsymbol{w}_{t}\,+\,\gamma\big{(}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big{)}\mathcal{H}^{[i]}_{t}\,-\,\gamma\mu_{t}\Big{[}X^{m\,[i]}_{t}\Big{]}\,\frac{\boldsymbol{\alpha}_{t}}{\sqrt{\boldsymbol{v}_{t}}}\,+\,\gamma\frac{\mu_{t}}{2}\Big{[}X^{v\,[i]}_{t}\Big{]}\,\frac{\boldsymbol{\alpha}_{t}\boldsymbol{m}_{t}}{\boldsymbol{v}_{t}^{1.5}},$
(63)

where $B^{[i]}_{t}$, $\mathcal{H}^{[i]}_{t}$, $X^{m\,[i]}_{t}$, and
$X^{v\,[i]}_{t}$ stand for the $i$th columns of $B_{t}$, $\mathcal{H}_{t}$,
$X^{m}_{t}$, and $X^{v}_{t}$, respectively. Following similar arguments as in
(48), it is easy to show that

$\begin{split}&\frac{d\,X^{m}_{t}}{d\,\boldsymbol{\beta}_{t}}=\frac{d\,X^{v}_{t}}{d\,\boldsymbol{\beta}_{t}}=0,\\\
&\frac{d\,X^{m}_{t}}{d\,\boldsymbol{w}_{t}}=\frac{d\,X^{v}_{t}}{d\,\boldsymbol{w}_{t}}=0,\\\
&\frac{d\,X^{m}_{t}}{d\,\boldsymbol{m}_{t}}=\frac{d\,X^{v}_{t}}{d\,\boldsymbol{m}_{t}}=0,\\\
&\frac{d\,X^{m}_{t}}{d\,\boldsymbol{v}_{t}}=\frac{d\,X^{v}_{t}}{d\,\boldsymbol{v}_{t}}=0,\\\
&\frac{d\,X^{m}_{t}}{d\,\boldsymbol{h}_{t}}=\frac{d\,X^{v}_{t}}{d\,\boldsymbol{h}_{t}}=0.\end{split}$
(64)

Note that $\boldsymbol{h}_{t}$ is an $nm$-dimensional vector derived from
stacking the columns of $\mathcal{H}_{t}$. Therefore, we consider a block
representation of $\boldsymbol{h}_{t}$ consisting of $m$ blocks, each of which
corresponds to a column of $\mathcal{H}_{t}$. By taking the derivative of (62)
with respect to $\boldsymbol{h}_{t}$, and using (64), we obtain

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}=\gamma\,\left[\begin{array}[]{c|c|c|c}\begin{array}[]{c}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\\
\vspace{-6pt}\hfil\\\ \end{array}&0&0&0\\\ \hline\cr
0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\\ \vspace{-6pt}\hfil\\\
\end{array}&0&0\\\ \hline\cr 0&0&\begin{array}[]{c}\vspace{-4pt}\hfil\\\
\ddots\\\ \vspace{-4pt}\hfil\\\ \end{array}&0\\\ \hline\cr
0&0&0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>1\textrm{st}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>2\textrm{nd}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-4pt}\hfil\\\
\,\,{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\vspace{-4pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>m\textrm{th}}\end{array}\end{array}.$ (65)

Let $\beta_{t}[i]$ and $w_{t}[j]$ denote the $i$th and $j$th entries of
$\boldsymbol{\beta}_{t}$ and $\boldsymbol{w}_{t}$, for $i=1,\ldots,m$ and
$j=1,\ldots,n$, respectively. Note that
${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{\beta}_{t}}$ is a block matrix, in
the form of an $m\times m$ array of $n\times 1$ blocks,
$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}[i,j]\overset{\text{\tiny
def}}{=}\frac{d\,\mathcal{H}_{t+1}^{[i]}}{d\,\beta_{t}[j]}$, for
$i,j=1,\ldots,m$. It then follows from (62) and (64) that, for
$i,j=1,\ldots,m$,

$\begin{split}\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}[i,j]=&\frac{d\,\mathcal{H}_{t+1}^{[i]}}{d\,\beta_{t}[j]}\\\
=&-\gamma\mu_{t}\Big{[}\frac{\boldsymbol{m}_{t}}{\sqrt{\boldsymbol{v}_{t}}}+\kappa\boldsymbol{w}_{t}\Big{]}\left(\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[j]}\right)B^{[i]}_{t}\,+\,\gamma\left(I-\kappa\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[j]}\Big{]}\right)\mathcal{H}^{[i]}_{t}\\\
\,&-\,\gamma\mu_{t}\Big{[}\frac{1}{\sqrt{\boldsymbol{v}_{t}}}\Big{]}\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[j]}\Big{]}\,X^{m\,[i]}_{t}\,+\,\gamma\frac{\mu_{t}}{2}\Big{[}\frac{\boldsymbol{m}_{t}}{\boldsymbol{v}_{t}^{1.5}}\Big{]}\,\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[j]}\Big{]}\,X^{v\,[i]}_{t},\end{split}$
(66)

where $\frac{\partial}{\partial\beta}$ stands for the entry-wise partial
derivative of a matrix with respect to a scalar variable $\beta$.

In the same vein, it follows from (63) and (64) that

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}=-\gamma\mu_{t}\kappa\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[1]}_{t}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[m]}_{t}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (67)
$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}=\gamma\mu_{t}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{\boldsymbol{\alpha}_{t}X^{v\,[1]}_{t}}{2\,\boldsymbol{v}_{t}^{1.5}}-\frac{\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[1]}_{t}}{\sqrt{\boldsymbol{v}_{t}}}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{\boldsymbol{\alpha}_{t}X^{v\,[m]}_{t}}{2\,\boldsymbol{v}_{t}^{1.5}}-\frac{\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[m]}_{t}}{\sqrt{\boldsymbol{v}_{t}}}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (68)
$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{v}_{t}}=\frac{\gamma\mu_{t}}{2}\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{1}{\boldsymbol{v}_{t}^{1.5}}\Big{]}\,\Big{[}\big{(}\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[1]}_{t}\big{)}\boldsymbol{m}_{t}+\boldsymbol{\alpha}_{t}\,X^{m\,[1]}_{t}\,-\,\frac{3\boldsymbol{\alpha}_{t}\boldsymbol{m}_{t}X^{v\,[1]}_{t}}{2\,\boldsymbol{v}_{t}}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\par\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\Big{[}\frac{1}{\boldsymbol{v}_{t}^{1.5}}\Big{]}\,\Big{[}\big{(}\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[m]}_{t}\big{)}\boldsymbol{m}_{t}+\boldsymbol{\alpha}_{t}\,X^{m\,[m]}_{t}\,-\,\frac{3\boldsymbol{\alpha}_{t}\boldsymbol{m}_{t}X^{v\,[m]}_{t}}{2\,\boldsymbol{v}_{t}}\Big{]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right].$ (69)

Finally, $G^{\textrm{base}}_{t}$ is obtained by plugging (65), (66), (67),
(68), and (69) into (60).

####  A.3.2 Base Lion

The lion algorithm, when used for base update, is as follows

$\displaystyle\boldsymbol{m}_{t+1}=\rho\,\boldsymbol{m}_{t}+(1-\rho)\,\nabla
f_{t}(\boldsymbol{w}_{t}),$ (70)
$\displaystyle\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}-\kappa\boldsymbol{\alpha}_{t}\boldsymbol{w}_{t},$ (71)

where $\boldsymbol{m}_{t}$ is called the momentum, $\kappa>0$ is the weight-
decay parameter, $\rho,c\in[0,1)$ are constants, and
$\operatorname{Sign}(\cdot)$ is a function that computes entry-wise sign of a
vector. Let

$\boldsymbol{x}_{t}=\left[\begin{array}[]{c}\boldsymbol{w}_{t}\\\
\hfill\boldsymbol{m}_{t}\end{array}\right].$ (72)

It then follows from (45) that

$\begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{x}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{x}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccccc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\frac{d\,\boldsymbol{w}_{t+1}}{d\,\boldsymbol{m}_{t}}&0\\\
\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{\beta}_{t}}&0&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{w}_{t}}&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{m}_{t}}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\\\
&=\left[\begin{array}[]{ccccc}-\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\big{[}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}+\kappa\boldsymbol{w}_{t}\big{]}\sigma^{\prime}(\boldsymbol{\beta}_{t})}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\,0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{I-\kappa\left[\boldsymbol{\alpha}_{t}\right]}\\\ \vspace{-10pt}\hfil\\\
\end{array}&0&0\\\
\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{\beta}_{t}}&0&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{w}_{t}}&\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{m}_{t}}&0\\\
\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&0&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]\end{split}$ (73)

where the second equality is due to (72) and the last equality follows from
(71). Consider the following block representation of $X_{t}$,

$X_{t}=\left[\begin{array}[]{c}\mathcal{H}_{t}\\\ \hfill
X^{m}_{t}\end{array}\right].$ (74)

Plugging the first row of $G^{\textrm{base}}_{t}$, given in (73), into (47),
implies that

$\mathcal{H}_{t+1}=-\gamma\big{[}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}+\kappa\boldsymbol{w}_{t}\big{]}\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}\,+\,\gamma\big{(}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big{)}\mathcal{H}_{t}$
(75)

For simplicity of notation, we define the diagonal matrix $S_{t}$ as

$S_{t}\overset{\text{\tiny
def}}{=}\big{[}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}+\kappa\boldsymbol{w}_{t}\big{]}.$ (76)

Then,

$\boldsymbol{h}_{t+1}=\gamma\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{-S_{t}\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}\,+\,\gamma\big{(}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big{)}\mathcal{H}_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{-S_{t}\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}\,+\,\gamma\big{(}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big{)}\mathcal{H}_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}.\end{array}\right]$ (77)

It follows that

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{m}_{t}}=0,$ (78)

and

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{e}_{1}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\cdots&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{e}_{n}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\vdots&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\ddots}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\vdots\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{e}_{1}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\cdots&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\boldsymbol{e}_{n}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (79)

where $\boldsymbol{e}_{i}$ is the $i$th unit vector (i.e., an $n$-dimensional
vector whose $i$th entry is $1$ and all other entries are zero). Let
$\beta_{t}[i]$ and $\mathcal{H}_{t}^{[i]}$ be the $i$th entry of
$\boldsymbol{\beta}_{t}$ and $i$th column of $\mathcal{H}_{t}$, respectively,
for $i=1,\ldots,m$. Then,

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\gamma\kappa\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[1]}\Big{]}\,\mathcal{H}_{t}^{[1]}\,+\,S_{t}\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[1]}\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\quad\cdots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\gamma\kappa\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[m]}\Big{]}\,\mathcal{H}_{t}^{[1]}\,+\,S_{t}\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[{m}]}\,B_{t}^{[1]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\ddots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {\vdots}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\
\hline\cr\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\gamma\kappa\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[1]}\Big{]}\,\mathcal{H}_{t}^{[m]}\,+\,S_{t}\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[1]}\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\cdots}\\\ \vspace{-10pt}\hfil\\\
\end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\gamma\kappa\Big{[}\frac{d\,\boldsymbol{\alpha}_{t}}{d\,\beta_{t}[m]}\Big{]}\,\mathcal{H}_{t}^{[m]}\,+\,S_{t}\,\frac{\partial\,\sigma^{\prime}(\boldsymbol{\beta}_{t})}{\partial\,\beta_{t}[{m}]}\,B_{t}^{[m]}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right],$ (80)

and

$\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}=\gamma\,\left[\begin{array}[]{c|c|c|c}\begin{array}[]{c}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\\
\vspace{-6pt}\hfil\\\ \end{array}&0&0&0\\\ \hline\cr
0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\\ \vspace{-6pt}\hfil\\\
\end{array}&0&0\\\ \hline\cr 0&0&\begin{array}[]{c}\vspace{-4pt}\hfil\\\
\ddots\\\ \vspace{-4pt}\hfil\\\ \end{array}&0\\\ \hline\cr
0&0&0&\begin{array}[]{c}\vspace{-6pt}\hfil\\\
I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>1\textrm{st}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>2\textrm{nd}}\\\ \vspace{-6pt}\hfil\\\ \end{array}\\\
\begin{array}[]{c}\vspace{-4pt}\hfil\\\
\,\,{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>\vspace{-4pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-6pt}\hfil\\\
{\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@color<EMAIL_ADDRESS>m\textrm{th}}\end{array},\end{array}.$ (81)

It follows from (22), (73), and (78) that in the $G_{t}$ matrix,
$\frac{d\,\boldsymbol{m}_{t+1}}{d\,\boldsymbol{m}_{t}}$ is the only non-zero
block in its corresponding column of blocks. Consequently, it follows from
(15) that $X^{m}_{t}$, as defined in (74), has no impact on the update of
$\mathcal{H}_{t+1}$, $Y_{t+1}$, and $Q_{t+1}$. Therefore, the rows and columns
of $G^{\textrm{base}}$ that correspond to derivative of $\boldsymbol{m}$ can
be completely removed from $G^{\textrm{base}}$. By removing these rows and
columns from $G^{t}$, the matrix update (15) simplifies to

$\left[\begin{array}[]{c}Y_{t+1}\\\ \mathcal{H}_{t+1}\\\
Q_{t+1}\end{array}\right]=\gamma\,\left[\begin{array}[]{cc}\begin{array}[]{c}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{y}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\left[\begin{array}[]{cc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{-\big{[}\operatorname{Sign}\big{(}c\,\boldsymbol{m}_{t}+(1-c)\nabla
f_{t}\big{)}\big{]}\sigma^{\prime}(\boldsymbol{\beta}_{t})}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\,\,\,\,\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {0}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{\beta}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}&\,\,\,\,\begin{array}[]{c}\vspace{-10pt}\hfil\\\ {0}\\\
\vspace{-10pt}\hfil\\\ \end{array}\end{array}\right]}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}&\begin{array}[]{cc}\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{y}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{I-\kappa\left[\boldsymbol{\alpha}_{t}\right]}\\\ \vspace{-10pt}\hfil\\\
\end{array}&0\\\ \begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{w}_{t}}}\\\
\vspace{-10pt}\hfil\\\ \end{array}&\begin{array}[]{c}\vspace{-10pt}\hfil\\\
{\frac{d\,\boldsymbol{h}_{t+1}}{d\,\boldsymbol{h}_{t}}}\\\
\vspace{-10pt}\hfil\\\
\end{array}\end{array}\end{array}\right]\,\left(\left[\begin{array}[]{c}Y_{t}\\\
\mathcal{H}_{t}\\\
Q_{t}\end{array}\right]+(1-\gamma)\left[\begin{array}[]{c}\begin{array}[]{c}\vspace{-11pt}\hfil\\\
{\left[\begin{array}[]{c}I\\\ 0\end{array}\right]}\\\ \vspace{-11pt}\hfil\\\
\end{array}\\\ 0\\\ 0\end{array}\right]\right),$ (82)

where ${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{\beta}_{t}}$,
${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{w}_{t}}$, and
${d\,\boldsymbol{h}_{t+1}}/{d\,\boldsymbol{h}_{t}}$ are given in (80), (79),
and (81), respectively; and the blocks in the first row depend on the meta
update.

##  Appendix B Exiting Step-size Optimization Algorithms as Special Cases of
MetaOptimize

In this appendix we show that some of the existing step-size optimization
algorithms are special cases of the MetaOptimize framework. In particular, we
first consider the IDBD algorithm (Sutton, 1992) and its extension (Xu et al.,
2018), and then discuss about the HyperGradient algorithm (Baydin et al.,
2017).

###  B.1 IDBD and Its Extensions

(Sutton, 1992) proposed the IDBD algorithm for step-size optimization of a
class of quadratic loss functions. In particular, it considers loss functions
of the form

$f_{t}(\boldsymbol{w}_{t})=\frac{1}{2}\big{(}\boldsymbol{a}_{t}^{T}\boldsymbol{w}_{t}-b_{t}\big{)}^{2},$
(83)

for a given sequence of feature vectors $\boldsymbol{a}_{t}$ and target values
$b_{t}$, for $t=1,2,\ldots$. Moreover, Sutton (1992) assumes weight-wise step
sizes, in which case $\boldsymbol{\beta}_{t}$ has the same dimension as
$\boldsymbol{w}_{t}$. The update rule of IDBD is as follows:

$\displaystyle\boldsymbol{g}_{t}$
$\displaystyle\leftarrow(\boldsymbol{a}_{t}^{T}\boldsymbol{w}_{t}-b_{t})\,\boldsymbol{a}_{t},$
(84) $\displaystyle\boldsymbol{\beta}_{t+1}$
$\displaystyle\leftarrow\boldsymbol{\beta}_{t}-\eta\,\boldsymbol{h}_{t}\,\boldsymbol{g}_{t},$
(85) $\displaystyle\boldsymbol{\alpha}_{t+1}$
$\displaystyle\leftarrow\exp\big{(}\boldsymbol{\beta}_{t+1}\big{)},$ (86)
$\displaystyle\boldsymbol{w}_{t+1}$
$\displaystyle\leftarrow\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t+1}\,\boldsymbol{g}_{t},$
(87) $\displaystyle\boldsymbol{h}_{t+1}$
$\displaystyle\leftarrow\left(1-\boldsymbol{\alpha}_{t+1}\boldsymbol{a}_{t}^{2}\right)^{+}\boldsymbol{h}_{t}-\boldsymbol{\alpha}_{t+1}\boldsymbol{g}_{t},$
(88)

where $(\cdot)^{+}$ clips the entries at zero to make them non-negative, aimed
to improve stability. Here, $\boldsymbol{g}_{t}$ is the gradient of
$f_{t}(\boldsymbol{w}_{t})$ and $\boldsymbol{a}_{t}^{2}$ in the last line is a
vector that contains diagonal entries of the Hessian of $f_{t}$. The updated
values of $\boldsymbol{\beta}$ and $\boldsymbol{w}$ would remain unchanged, if
instead of the vector $\boldsymbol{h}_{t}$, we use a diagonal matrix
$\mathcal{H}_{t}$ and replace (85) and (88) by

$\begin{split}\boldsymbol{\beta}_{t+1}&\leftarrow\boldsymbol{\beta}_{t}-\eta\,\mathcal{H}_{t}\,\boldsymbol{g}_{t},\\\
\mathcal{H}_{t+1}&\leftarrow\left(1-\left[{\boldsymbol{\alpha}}_{t+1}\boldsymbol{a}^{2}\right]\right)^{+}\mathcal{H}_{t}-\left[\boldsymbol{\alpha}_{t+1}\boldsymbol{g}_{t}\right].\end{split}$
(89)

Note that $\left[\boldsymbol{a}^{2}\right]$ is a matrix that is obtained from
zeroing-out all non-diagonal entries of the Hessian matrix of $f_{t}$. It is
easy to see that the above formulation of IDBD, equals the L-approximation of
MetaOptimize framework when we use SGD for both base and meta updates, and
further use a diagonal approximation of the Hessian matrix along with a
rectifier in the update of $\mathcal{H}_{t}$.

An extension of IDBD beyond quadratic case has been derived in (Xu et al.,
2018). Similar to IDBD, they also consider weight-wise step sizes, i.e.,
$m=n$. The update of step sizes in this method is as follows:

$\begin{split}\boldsymbol{\beta}_{t+1}&\leftarrow\boldsymbol{\beta}_{t}-\eta\,\mathcal{H}_{t}^{\mathsf{T}}\,\nabla
f_{t}(\boldsymbol{w}_{t})\\\
\boldsymbol{\alpha}_{t+1}&\leftarrow\exp(\boldsymbol{\beta}_{t+1}),\\\
\boldsymbol{w}_{t+1}&\leftarrow\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t+1}\,\nabla
f_{t}(\boldsymbol{w}_{t}),\\\
\mathcal{H}_{t+1}&\leftarrow\big{(}I-\left[\boldsymbol{\alpha}_{t+1}\right]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})\,\big{)}\,\mathcal{H}_{t}-\big{[}\boldsymbol{\alpha}_{t+1}\,\nabla
f_{t}(\boldsymbol{w}_{t})\big{]}.\end{split}$

Similar to IDBD, it is straightforward to check that the above set of updates
is equivalent to the L-approximation of MetaOptimize framework that uses SGD
for both base and meta updates, except for the fact that the above algorithm
uses $\boldsymbol{\alpha}_{t+1}$ in $\boldsymbol{w}_{t+1}$ and
$\mathcal{H}_{t+1}$ updates whereas MetaOptimize uses
$\boldsymbol{\alpha}_{t}$. This however has no considerable impact since
$\boldsymbol{\alpha}_{t}$ varies slowly.

###  B.2 Hyper-gradient Descent

HyperGradient descent was proposed in (Baydin et al., 2017) as a step-size
optimization method. It considers scalar step size with straightforward
extensions to weight-wise step sizes, and at each time $t$, updates the step
size in a direction to minimize the immediate next loss function. In
particular, they propose the following additive update for step sizes, that
can wrap around an arbitrary base update:

$\begin{split}\boldsymbol{\alpha}_{t}&=\beta_{t}\,\boldsymbol{1}_{n\times
1},\\\
\beta_{t+1}&=\beta_{t}-\eta\,\frac{d\,f_{t}(\boldsymbol{w}_{t})}{d\,\beta_{t-1}}=\beta_{t}-\eta\,\nabla
f_{t}(\boldsymbol{w}_{t})^{T}\,\frac{d\,\boldsymbol{w}_{t}}{d\,\beta_{t-1}}.\end{split}$
(90)

The last update can be equivalently written as

$\begin{split}\beta_{t+1}&=\beta_{t}-\eta\,\mathcal{H}_{t}^{T}\,\nabla
f_{t}(\boldsymbol{w}_{t}),\\\
\mathcal{H}_{t+1}&=0\times\mathcal{H}_{t}+\frac{d\,\boldsymbol{w}_{t+1}}{d\,\beta_{t}}.\end{split}$
(91)

The step-size update in (91) can be perceived as a special case of
MetaOptimize in two different ways. First, as a MetaOptimize algorithm that
uses SGD as its meta update and approximate the $G_{t}$ matrix in (10) by
zeroing out all of its blocks except for the top two blocks in the first
column. From another perspective, the additive HyperGradient descent in (91)
is also equivalent to a MetaOptimize algorithm that uses SGD as its meta
update and sets $\gamma=0$. Note that setting $\gamma$ equal to zero would
eliminate the dependence of $\mathcal{H}_{t+1}$ on $X_{t}$ and $Q_{t}$, as can
be verified from (15). This would also render the $\beta$ updates ignorant
about the long-term impact of step size on future losses.

##  Appendix C Details of Experiments

In the appendix, we describe the details of experiments performed throughout
the paper. In our experiments on CIFAR10 and ImageNet dataset, we used a
machine with CPU of Intel Xeon Gold 5120 Skylake at 2.2GHz (16GB RAM) and GPU
of NVIDIA V100 Volta (16GB HBM2 memory). For TinyStories dataset, we used a
machine with CPU of AMD Milan 7413 @ 2.65 GHz 128M cache L3 and GPU of NVidia
A100SXM4 (40 GB memory). In all experiments, the meta step size $\eta$ is set
to $10^{-3}$. The meta-parameters used in the considered optimization
algorithm for CIFAR10, ImageNet, and TinyStories are given in Table 1, Table
2, and Table 3, respectively. In the experiments, we performed a grid search
for $\rho,\bar{\rho}\in\\{0.9,0.99,0.999\\}$,
$\lambda,\bar{\lambda}\in\\{0.99,0.999\\}$, and $c,\bar{c}\in\\{0.9,0.99\\}$.
Regarding baselines with fixed step sizes, we did a grid search for the
learning rate in the set $\\{10^{-5},10^{-4},10^{-3},10^{-2},10^{-1}\\}$. We
set $\gamma$ equal to one in all experiments. Moreover, in ImageNet
(respectively TinyStories) dataset, for AdamW with the learning rate
scheduler, we considered a cosine decay with 10k (respectively 1k) steps
warmup (according to extensive experimental studies in (Chen et al., 2023)