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

###### Abstract

We address the challenge of optimizing meta-parameters (hyperparameters) in machine learning, a key factor for efficient training and high model performance. Rather than relying on expensive meta-parameter search methods, we introduce MetaOptimize: a dynamic approach that 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 considers the long-term impact of step sizes on training, through a discounted sum of future losses. We also introduce lower-complexity variants of MetaOptimize that, in conjunction with its adaptability to various optimization algorithms, achieve performance comparable to those of the best hand-crafted learning rate schedules across diverse machine learning tasks.

###### Keywords:

## 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 ) , where continually changing environments or evolving loss functions necessitate adaptation of meta-parameters, such as step sizes, to track time-varying optima rather than settling on a static value.

In this work, we propose MetaOptimize , a general framework for optimizing meta-parameters to minimize a form of regret that explicitly accounts for the long-term influence of step sizes on future loss. Although this framework can handle various meta-parameters, we concentrate on step sizes as they are ubiquitous and crucial in practice.

MetaOptimize offers additional advantages beyond reducing search overhead. First, it enables dynamic step-size updates during training, potentially speeding the learning process. Traditional methods typically rely on manually designed learning rate schedules (e.g., initial increase followed by decay ( Amid et al., 2022 ) ), whereas MetaOptimize automatically discovers similar patterns.

Second, adapting step sizes across different network blocks (e.g., layers or neurons) can improve performance ( Singh et al., 2015 ; Howard & Ruder, 2018 ) , yet manually tuning such blockwise step sizes is impractical for large networks. By design, MetaOptimize handles these blockwise adjustments.

The concept of meta step-size optimization dates back to ( Kesten, 1958 ) , Delta-bar-Delta ( Sutton, 1981 ; Jacobs, 1988 ) , and its incremental variant, IDBD ( Sutton, 1992 ) . Numerous methods have emerged over the years (Section 8 ). This work distinguishes itself from prior efforts through the following key aspects: • We introduce a formal approach to step-size optimization by minimizing a specific form of regret, essentially a discounted sum of future losses, and demonstrate how to do this causally via the MetaOptimize framework.

• MetaOptimize is general and can wrap around any first-order optimization algorithm (the base update ), such as SGD, RMSProp ( Hinton, 2012 ) , Adam ( Kingma & Ba, 2014 ) , or Lion ( Chen et al., 2023 ) , while optimizing step sizes via a separate first-order method (the meta update ), such as SGD, Adam, RMSProp, or Lion.

• We develop approximation methods (Section 6 ) that, when incorporated into MetaOptimize, yield computationally efficient algorithms outperforming state-of-the-art automatic hyperparameter optimization methods on various stationary and continual (non-stationary) benchmarks (see Section 7 ).

• We show that some existing methods (like IDBD and its extensions, and hypergradient descent ( Baydin et al., 2017 ) ) are specific instances or approximations within the MetaOptimize framework (Section 5 ).

## 2 Problem Setting

We introduce a general continual optimization setting that, for a given sequence of loss functions f t ​ ( ⋅ ) : ℝ n → ℝ f_{t}(\cdot):\mathbb{R}^{n}\to\mathbb{R} , t = 0 , 1 , 2 , … t=0,1,2,\ldots , aims to find a sequence of weight vectors 𝒘 1 , 𝒘 2 , 𝒘 3 , … \boldsymbol{w}_{1},\boldsymbol{w}_{2},\boldsymbol{w}_{3},\ldots that minimize a discounted sum of future losses: F t γ ​ = def ​ ( 1 − γ ) ​ ∑ τ > t γ τ − t − 1 ​ f τ ​ ( 𝒘 τ ) , F^{\gamma}_{t}\overset{\text{\tiny def}}{=}(1-\gamma)\,\sum_{\tau>t}\gamma^{\tau-t-1}f_{\tau}(\boldsymbol{w}_{\tau}), (1) where γ ∈ [ 0 , 1 ) \gamma\in[0,1) is a fixed discount factor, typically close to 1 1 , called the discount factor . For stationary supervised learning, f t f_{t} are i.i.d. samples from the same distribution, so minimizing F t γ F^{\gamma}_{t} promotes rapid reduction of the expected loss.

Consider an arbitrary first-order optimization algorithm (e.g., SGD, RMSProp, Adam, or Lion) for updating 𝒘 t \boldsymbol{w}_{t} . At time t t , it takes the gradient ∇ f t ​ ( 𝒘 t ) \nabla f_{t}(\boldsymbol{w}_{t}) of the current loss, along with an m m -dimensional meta-parameter vector 𝜷 t \boldsymbol{\beta}_{t} , to update 𝒘 t \boldsymbol{w}_{t} and possibly some internal variables 𝒙 ~ t \tilde{\boldsymbol{x}}_{t} (e.g., momentum in Adam). Denoting 𝒙 t ​ = def ​ Stack ⁡ ( 𝒘 t , 𝒙 ~ t ) \boldsymbol{x}_{t}\overset{\text{\tiny def}}{=}\operatorname{Stack}(\boldsymbol{w}_{t},\,\tilde{\boldsymbol{x}}_{t}) and calling this update rule Alg base \operatorname{Alg}_{\textrm{base}} , we have 𝒙 t + 1 = Alg base ⁡ ( 𝒙 t , ∇ f t ​ ( 𝒘 t ) , 𝜷 t ) . \boldsymbol{x}_{t+1}=\operatorname{Alg}_{\textrm{base}}(\boldsymbol{x}_{t},\nabla f_{t}(\boldsymbol{w}_{t}),\boldsymbol{\beta}_{t}). (2) The goal of MetaOptimize is to determine a sequence 𝜷 t \boldsymbol{\beta}_{t} such that plugging them into the above base update yields a trajectory { 𝒘 t } \{\boldsymbol{w}_{t}\} minimizing F t γ F^{\gamma}_{t} .

Step-size adaptation is a natural special case: at each step t t , the m m -dimensional 𝜷 t \boldsymbol{\beta}_{t} defines an n n -dimensional step-size vector 𝜶 t \boldsymbol{\alpha}_{t} via some fixed function σ : ℝ m → ℝ n \sigma:\mathbb{R}^{m}\to\mathbb{R}^{n} , i.e., 𝜶 t = σ ⁡ ( 𝜷 t ) . \boldsymbol{\alpha}_{t}=\sigma(\boldsymbol{\beta}_{t}). (3) A good choice for σ ⁡ ( ⋅ ) \sigma(\cdot) is exponential, ensuring 𝜶 t \boldsymbol{\alpha}_{t} is always positive and making multiplicative changes in 𝜶 t \boldsymbol{\alpha}_{t} correspond to additive changes in 𝜷 t \boldsymbol{\beta}_{t} ( Sutton, 1992 ) . By partitioning the network weights into blocks, we can learn a shared scalar step-size per block, or even a unique step-size per weight, all handled automatically by MetaOptimize.

## 3 Forward and Backward Views

Because F t γ F^{\gamma}_{t} depends on future losses, minimizing it causally requires an alternative view. Suppose hypothetically we had oracle access to future information (i.e., future loss values and weights). We could update 𝜷 t + 1 = 𝜷 t − η ​ d d ​ 𝜷 t ​ F t γ = 𝜷 t − η ⁡ ( 1 − γ ) ​ ∑ τ > t γ τ − t − 1 ​ d d ​ 𝜷 t ​ f τ ​ ( 𝒘 τ ) , \begin{split}\boldsymbol{\beta}_{t+1}&=\boldsymbol{\beta}_{t}-\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{t}}F^{\gamma}_{t}\\ &=\boldsymbol{\beta}_{t}-\eta\,(1-\gamma)\,\sum_{\tau>t}\gamma^{\tau-t-1}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}),\end{split} (4) where η \eta is a meta step-size. This forward-view update, however, is not causal because we do not have the required future information at time t t .

To address this, we adopt an eligibility-trace-style approach from reinforcement learning ( Sutton, 1988 ; Sutton & Barto, 2018 ) , introducing a backward-view update: 𝜷 τ + 1 ← 𝜷 τ − η ⁡ ( 1 − γ ) ​ ∑ t < τ γ τ − t − 1 ​ d d ​ 𝜷 t ​ f τ ​ ( 𝒘 τ ) , \boldsymbol{\beta}_{\tau+1}\leftarrow\boldsymbol{\beta}_{\tau}-\eta\,(1-\gamma)\,\sum_{t<\tau}\gamma^{\tau-t-1}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}), (5) so that terms involving f τ f_{\tau} (and 𝒘 τ \boldsymbol{w}_{\tau} ) appear at time τ \tau (instead of t t ), which is the earliest time that these quantities become available. In the small- η \eta limit, the backward view closely approximates the forward view. 1 1 1 Formally, assuming f t ​ ( ⋅ ) = 0 f_{t}(\cdot)=0 for t < 0 t<0 and for t > T t>T , the final updates under ( 5 ) and ( 4 ) become arbitrarily close as η → 0 \eta\to 0 . More specifically, ( β T ( 5 ) − β T ( 4 ) ) / η → 0 (\beta^{\textrm{\eqref{eq:backward}}}_{T}-\beta^{\textrm{\eqref{eq:forward}}}_{T})/{\eta}\to 0 , where β T ( 5 ) \beta^{\textrm{\eqref{eq:backward}}}_{T} and β T ( 4 ) \beta^{\textrm{\eqref{eq:forward}}}_{T} are the values of β \beta at time T T obtained from updates ( 5 ) and ( 4 ), respectively, starting from the same initial β 0 \beta_{0} . This is because as η → 0 \eta\to 0 , β \beta remains almost constant over [ 0 , T ] [0,T] interval, and the right hand sides of ( 5 ) and ( 4 ) match with accuracy O ⁡ ( η 2 ) O(\eta^{2}) , when summed over [ 0 , T ] [0,T] . See Section 9 for a discussion on more accurate approximations for large η \eta .

Accordingly, we define a causal gradient estimate ∇ 𝜷 F ^ τ ​ = def ​ ( 1 − γ ) ​ ∑ t = 0 τ − 1 γ τ − t − 1 ​ d d ​ 𝜷 t ​ f τ ​ ( 𝒘 τ ) . \widehat{\nabla_{\boldsymbol{\beta}}F}_{\tau}\overset{\text{\tiny def}}{=}(1-\gamma)\sum_{t=0}^{\tau-1}\gamma^{\tau-t-1}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{t}}f_{\tau}(\boldsymbol{w}_{\tau}). It follows from chain rule that ∇ 𝜷 F ^ τ = ℋ τ T ∇ f τ ( 𝒘 τ ) , \widehat{\nabla_{\boldsymbol{\beta}}F}_{\tau}=\mathcal{H}_{\tau}^{T}\nabla f_{\tau}(\boldsymbol{w}_{\tau}), (6) where ℋ τ ​ = def ​ ( 1 − γ ) ​ ∑ t = 0 τ − 1 γ τ − t − 1 ​ d ​ 𝒘 τ d ​ 𝜷 t . \mathcal{H}_{\tau}\overset{\text{\tiny def}}{=}(1-\gamma)\sum_{t=0}^{\tau-1}\gamma^{\tau-t-1}\frac{d\boldsymbol{w}_{\tau}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}. (7) Hence, ℋ τ \mathcal{H}_{\tau} encodes how past 𝜷 t \boldsymbol{\beta}_{t} values cumulatively affect 𝒘 τ \boldsymbol{w}_{\tau} under discounting by γ \gamma .

## 4 MetaOptimize

Algorithm 1 presents the general MetaOptimize framework for learning the meta-parameters 𝜷 t \boldsymbol{\beta}_{t} . At each step t t , we replace the intractable gradient ∇ 𝜷 F t γ \nabla_{\boldsymbol{\beta}}F^{\gamma}_{t} with the causal surrogate ∇ 𝜷 F ^ t \widehat{\nabla_{\boldsymbol{\beta}}F}_{t} to ensure the update is feasible in real time, as discussed in Section 3 . Specifically, we feed ∇ 𝜷 F ^ t = ℋ t T ∇ f t ( 𝒘 t ) \widehat{\nabla_{\boldsymbol{\beta}}F}_{t}=\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t}) (from ( 6 )) into any first-order meta-update rule Alg meta \operatorname{Alg}_{\textrm{meta}} , just like a conventional gradient.

Formally, define 𝒚 t ​ = def ​ Stack ⁡ ( 𝜷 t , 𝒚 ~ t ) \boldsymbol{y}_{t}\overset{\text{\tiny def}}{=}\operatorname{Stack}(\boldsymbol{\beta}_{t},\,\tilde{\boldsymbol{y}}_{t}) as the stack of meta-parameters 𝜷 t \boldsymbol{\beta}_{t} and any internal states 𝒚 ~ t \tilde{\boldsymbol{y}}_{t} of Alg meta \operatorname{Alg}_{\textrm{meta}} (e.g., momentum). The meta-update is then: 𝒚 t + 1 = Alg meta ( 𝒚 t , ℋ t T ∇ f t ( 𝒘 t ) ) . \boldsymbol{y}_{t+1}\;=\;\operatorname{Alg}_{\textrm{meta}}\!\Big(\boldsymbol{y}_{t},\,\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})\Big). (8) After applying the base update ( 2 ) to produce 𝒙 t + 1 \boldsymbol{x}_{t+1} , we compute ℋ t T ∇ f t ( 𝒘 t ) \mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t}) and plug it into ( 8 ) to update 𝒚 t + 1 \boldsymbol{y}_{t+1} (and thus 𝜷 t + 1 \boldsymbol{\beta}_{t+1} ). The remaining question is how to maintain ℋ t \mathcal{H}_{t} defined in ( 7 ), through application of the chain rule.

To compute ℋ t \mathcal{H}_{t} incrementally, let us stack the columns of the n × m n\times m matrix ℋ t \mathcal{H}_{t} into a single vector 𝒉 t \boldsymbol{h}_{t} , and let G t ​ = def ​ [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] . G_{t}\overset{\text{\tiny def}}{=}{\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]}. (9) Applying the chain rule then implies [ d ​ 𝒚 t + 1 d ​ 𝜷 τ d ​ 𝒙 t + 1 d ​ 𝜷 τ d ​ 𝒉 t + 1 d ​ 𝜷 τ ] = G t ​ [ d ​ 𝒚 t d ​ 𝜷 τ d ​ 𝒙 t d ​ 𝜷 τ d ​ 𝒉 t d ​ 𝜷 τ ] , \left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\end{array}\right]=G_{t}\left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\end{array}\right], which, when summed over τ \tau , turns into ∑ τ = 0 t γ t − τ ​ [ d ​ 𝒚 t + 1 d ​ 𝜷 τ d ​ 𝒙 t + 1 d ​ 𝜷 τ d ​ 𝒉 t + 1 d ​ 𝜷 τ ] = G t ​ [ d ​ 𝒚 t d ​ 𝜷 t d ​ 𝒙 t d ​ 𝜷 t d ​ 𝒉 t d ​ 𝜷 t ] + G t ​ ∑ τ = 0 t − 1 γ t − τ ​ [ d ​ 𝒚 t d ​ 𝜷 τ d ​ 𝒙 t d ​ 𝜷 τ d ​ 𝒉 t d ​ 𝜷 τ ] . \sum_{\tau=0}^{t}\gamma^{t-\tau}\left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\end{array}\right]=G_{t}\left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}\end{array}\right]+G_{t}\sum_{\tau=0}^{t-1}\gamma^{t-\tau}\left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\\ \hskip-10.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}}\\ \\ \end{array}\end{array}\right]. (10) Defining Y t \displaystyle Y_{t} = def ​ ( 1 − γ ) ​ ∑ τ = 0 t − 1 γ t − τ − 1 ​ d ​ 𝒚 t d ​ 𝜷 τ \displaystyle\overset{\text{\tiny def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{\mathrm{d}\,\boldsymbol{y}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}} (11) X t \displaystyle X_{t} = def ​ ( 1 − γ ) ​ ∑ τ = 0 t − 1 γ t − τ − 1 ​ d ​ 𝒙 t d ​ 𝜷 τ , \displaystyle\overset{\text{\tiny def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{\mathrm{d}\,\boldsymbol{x}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}, (12) Q t \displaystyle Q_{t} = def ​ ( 1 − γ ) ​ ∑ τ = 0 t − 1 γ t − τ − 1 ​ d ​ 𝒉 t d ​ 𝜷 τ , \displaystyle\overset{\text{\tiny def}}{=}(1-\gamma)\sum_{\tau=0}^{t-1}\gamma^{t-\tau-1}\frac{\mathrm{d}\,\boldsymbol{h}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}, (13) and noting that 𝒚 t = Stack ⁡ ( 𝜷 t , 𝒚 ~ t ) \boldsymbol{y}_{t}=\operatorname{Stack}(\boldsymbol{\beta}_{t},\,\tilde{\boldsymbol{y}}_{t}) , one obtains a compact update of the form [ Y t + 1 X t + 1 Q t + 1 ] = G t ​ ( γ ​ [ Y t X t Q t ] + ( 1 − γ ) ​ [ [ I 0 ] 0 0 ] ) , \left[\begin{array}[]{c}\!Y_{t+1}\\ \!X_{t+1}\\ \!Q_{t+1}\end{array}\right]=G_{t}\Bigg(\gamma\left[\begin{array}[]{c}\!Y_{t}\\ \!X_{t}\\ \!Q_{t}\end{array}\right]+(1-\gamma)\left[\begin{array}[]{c}\hskip-10.0pt\begin{array}[]{c}\\ {\left[\begin{array}[]{c}\!I\\ \!0\end{array}\right]}\\ \\ \end{array}\\ 0\\ 0\end{array}\right]\Bigg), (14) and then extract ℋ t \mathcal{H}_{t} by taking the top n n rows of X t X_{t} (since 𝒙 t = Stack ⁡ ( 𝒘 t , 𝒙 ~ t ) \boldsymbol{x}_{t}=\operatorname{Stack}(\boldsymbol{w}_{t},\tilde{\boldsymbol{x}}_{t}) ). The blocks of G t G_{t} can be found for standard algorithms (SGD, Adam, Lion, etc.) as detailed in Appendix A . Notably, the first row of G t G_{t} blocks depends only on Alg meta \operatorname{Alg}_{\textrm{meta}} , and the rest of G t G_{t} blocks depend only on Alg base \operatorname{Alg}_{\textrm{base}} . Algorithm 1 summarizes the procedure.

###### Remark 4.1 .

A distinction of MetaOptimize from existing meta-parameter optimization methods is that it explicitly captures dynamics of the meta-parameters 𝜷 \boldsymbol{\beta} , and how changes in the current 𝜷 \boldsymbol{\beta} affect 𝜷 \boldsymbol{\beta} in future. The term Y t Y_{t} in ( 11 ) links changes in past 𝜷 t \boldsymbol{\beta}_{t} to future 𝜷 \boldsymbol{\beta} values, which then influences ℋ t \mathcal{H}_{t} . Intuitively, if 𝜷 t \boldsymbol{\beta}_{t} has been changing consistently in one direction (e.g., steadily increasing), it amplifies Y t Y_{t} and thus ℋ t \mathcal{H}_{t} , accelerating ongoing updates. Conversely, if 𝜷 t \boldsymbol{\beta}_{t} stays nearly constant (indicating it may be close to optimal), Y t Y_{t} shrinks and so do the subsequent updates to 𝜷 t \boldsymbol{\beta}_{t} , stabilizing around the optimum.

## 5 Reducing Complexity

The matrix G t G_{t} can be large and may involve Hessian terms, increasing the computational burden. We discuss two practical approximations:

##### 2 × \times 2 approximation.

In ( 9 ), we zero out all blocks in the last row and column, effectively removing Q t Q_{t} . Empirically, this simplification often has negligible impact on performance. Intuitively, ℋ t \mathcal{H}_{t} does not affect the base update directly ( d ​ 𝒙 t + 1 / d ​ 𝒉 t = 0 \mathrm{d}\,\boldsymbol{x}_{t+1}/\mathrm{d}\,\boldsymbol{h}_{t}=0 ), so the extra blocks in G t G_{t} involving 𝒉 t \boldsymbol{h}_{t} often have minor influence on the final meta-parameter trajectory.

##### L-approximation.

We go one step further, also zeroing out the block in the first row and second column of G t G_{t} . Formally, G t L ​ = def ​ [ d ​ 𝒚 t + 1 d ​ 𝒚 t 0 d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t ] , G^{L}_{t}\overset{\text{\tiny def}}{=}{\left[\begin{array}[]{cc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}\end{array}\right]}, (15) and the update in ( 14 ) simplifies to [ Y t + 1 X t + 1 ] = G t L ​ ( γ ​ [ Y t X t ] + ( 1 − γ ) ​ [ I 0 0 ] ) . \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). (16) This again discards Q t Q_{t} , but also certain cross-terms in Y t Y_{t} ’s update. Empirically, L-approximation often matches the performance and sometimes improves the stability of the 2 × 2 2\times 2 approach.

##### Intuition.

Algorithm 2 illustrates the 2 × 2 2\times 2 approximation for the case of SGD base/meta updates with a single scalar step size. Observe how ℋ t \mathcal{H}_{t} effectively accumulates (decayed) past gradients to decide whether to increase or decrease α t \alpha_{t} . If current and past gradients align, α t \alpha_{t} is raised for faster learning; if they oppose each other, α t \alpha_{t} shrinks. The decay γ ⁡ ( I − [ 𝜶 ] ​ ∇ 2 f t ) \gamma(I-\left[\boldsymbol{\alpha}\right]\nabla^{2}f_{t}) of ℋ t \mathcal{H}_{t} ensures that if past gradients poorly approximate future ones due to large ∇ 2 f t \nabla^{2}f_{t} or 𝜶 \boldsymbol{\alpha} , their influence fades more rapidly. Meanwhile, Y t Y_{t} reflects how changing past 𝜷 \boldsymbol{\beta} influences the current 𝜷 \boldsymbol{\beta} ; large swings in 𝜷 \boldsymbol{\beta} amplify ℋ t + 1 \mathcal{H}_{t+1} , while near-constant 𝜷 \boldsymbol{\beta} dampens updates. Under the L-approximation, Y t Y_{t} becomes constant in this particular setup, further simplifying the algorithm.

##### Containing some prior methods as special cases.

Under L-approximation, and restricting both base and meta updates to plain SGD, MetaOptimize reduces to IDBD ( Sutton, 1982 ) and its extension ( Xu et al., 2018 ) ; see Appendix B.1 for derivations. Another notable special case is γ = 0 \gamma=0 , which recovers the Hypergradient-descent approach ( Baydin et al., 2017 ) , updating step sizes to minimize the immediate loss f t ​ ( 𝒘 t ) f_{t}(\boldsymbol{w}_{t}) rather than the discounted sum F t γ F^{\gamma}_{t} , ignoring long-term effects of step size on future loss.

## 6 Hessian-Free MetaOptimize

The G t G_{t} matrix typically involves Hessian, ∇ 2 f t ​ ( 𝒘 t ) \nabla^{2}f_{t}(\boldsymbol{w}_{t}) , of the loss function, e.g., in the d ​ 𝒘 t + 1 / d ​ 𝒘 t d\boldsymbol{w}_{t+1}/d\boldsymbol{w}_{t} block where 𝒘 t + 1 = 𝒘 t − 𝜶 t ∇ f t ( 𝒘 t ) \boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\nabla f_{t}(\boldsymbol{w}_{t}) . Including second-order information in G t G_{t} can be costly. Interestingly, for certain base and meta algorithms, we can eliminate the Hessian without much compromising the performance.

For example, Lion ( Chen et al., 2023 ) updates weights by taking the sign of the gradient (plus momentum). Since the derivative of the sign function is zero almost everywhere, d ​ 𝒘 t + 1 / d ​ 𝒘 t \mathrm{d}\,\boldsymbol{w}_{t+1}/\mathrm{d}\,\boldsymbol{w}_{t} and related partials do not involve ∇ 2 f t ​ ( 𝒘 t ) \nabla^{2}f_{t}(\boldsymbol{w}_{t}) . Hence, if both base and meta updates use Lion , G t G_{t} becomes Hessian-free throughout, avoiding second-order computations entirely (Appendix A.1.3 , A.3.2 ).

For other algorithms, we may consider their Hessian-free approximation by zeroing out any Hessian term in G t 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, 𝒗 t \boldsymbol{v}_{t} , as in RMSProp. Such normalizations typically result in two opposing Hessian-based terms in ℋ t \mathcal{H}_{t} ’s update (stemming from d ​ 𝒘 t + 1 d ​ 𝒘 t \frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}} and d ​ 𝒘 t + 1 d ​ 𝒗 t \frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}} blocks of matrix G t G_{t} ), aiming to cancel out, particularly when consecutive gradients are positively correlated.

When Hessian terms are removed in the 2 × 2 2\times 2 approximation, X t X_{t} and Y t Y_{t} become diagonal or simply vectorized, drastically reducing matrix-multiplication overhead. The overall complexity per step thus becomes similar to that of regular base and meta updates, requiring only a few extra vector operations. Algorithm 3 in Appendix A illustrates these Hessian-free variants (SGDm, AdamW, Lion) under 2 × 2 2\times 2 approximation.

In summary, Hessian-free and 2 × 2 2\times 2 or L-approximations yield a range of practical MetaOptimize instantiations that maintain strong performance at low additional cost.

## 7 Experiments

We evaluate MetaOptimize on image-classification and language-modeling benchmarks. Out of many possible base/meta-algorithm combinations and approximations (Algorithm 3 ), we showcase a few Hessian-free variants that performed well in practice. In the experiments, MetaOptimize starts with step-sizes set one or two orders of magnitude below typical good fixed step-sizes, with no specific tuning. We compare MetaOptimize against some popular baselines whose meta-parameters are well-tuned for each task separately. See Appendix C for more details. Codes are available at https://github.com/sabersalehk/MetaOptimize .

Base update

μ t = 1 − λ t / ( 1 − ρ t )

Meta update

μ ¯ t = 1 − λ ¯ t / ( 1 − ρ ¯ t )

### 7.1 CIFAR10 dataset

The first set of experiments involve training ResNet-18 with batch size of 100 on the CIFAR10 ( Krizhevsky et al., 2009 ) dataset. Fig. 2 depicts the learning curves of four combinations of (base, meta) algorithms for Hessian-free MetaOptimize, along with the corresponding baselines with well-tuned fixed step sizes. Besides using a single scalar step-size, we also test a blockwise variant that partitions the ResNet18 parameters into six blocks (one for each linear layer and four blocks for the ResNet modules). In every tested combination, MetaOptimize outperforms its corresponding fixed-step-size baseline.

Interestingly, as demonstrated in Fig. 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.

### 7.2 Non-stationary CIFAR100

We evaluated MetaOptimize in a non-stationary setting with 10 sequential tasks, each containing 10 classes from CIFAR100. After training for one epoch on a task, it abruptly switches without explicit notification to the optimizer, and without resetting weights. We use a batch size of one, meaning each data point is seen exactly once. The model is based on a simple CNN network consisting of two convolution (and max pooling) layers followed by a fully connected layer. Each curve is averaged over 5 random seeds.

Figure 4 presents cumulative top-1 accuracy—averaged over all past training times—for AdamW (with the best fixed step-size), MetaOptimize with a scalar step-size, and MetaOptimize with blockwise step-sizes (two blocks: one for the first three layers and one for the last layer). MetaOptimize consistently outperforms the baseline. See Appendix D for additional plots.

The learned step-sizes reveal an interesting pattern (Fig. 4 ): • Task adaptation: MetaOptimize increases step-sizes immediately after task switches to enhance adaptation.

• Layer-wise behavior: In blockwise case, early-layer step-sizes decrease over time, indicating convergence to globally useful features, while last-layer step-sizes increase, reflecting the need to adapt to changing labels.

### 7.3 ImageNet dataset

We trained ResNet-18 with batch-size 256 on ImageNet ( Deng et al., 2009 ) . We compared MetaOptimize with scalar step-size against four state-of-the-art hyperparamter optimization algorithms, namely DoG ( Ivgi et al., 2023 ) , gdtuo ( Chandra et al., 2022 ) , Prodigy ( Mishchenko & Defazio, 2023 ) , and mechanic ( Cutkosky et al., 2024 ) , as well as AdamW and Lion baselines with fixed step-sizes, and AdamW with a well-tuned cosine decay learning rate scheduler with a 10k iterations warmup. Learning curves and complexity overheads are shown respectively in Fig. 6 and Table 1 , showcasing the advantage of MetaOptimize algorithms (learning curve of DoG is not depicted due to its relatively poor performance). Unlike CIFAR10, here the blockwise versions of MetaOptimize showed no improvement over the scalar versions. Refer to Appendix D for further details.

### 7.4 Language modeling

For language model experiments, we used 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 on the TinyStories dataset. Two combinations of Hessian-free MetaOptimize with scalar step sizes were tested against Lion and AdamW with well-tuned fixed step sizes, AdamW with a well-tuned cosine decay learning rate scheduler with 1k warmup iterations, and the four state-of-the-art step-size adaptation algorithms mentioned in the previous subsection. According to the learning curves, shown in Fig. 6 , MetaOptimize outperforms all baselines (with an initial delay due to small initial step-sizes), except for the well-tuned learning rate scheduler within 30k iterations.

### 7.5 Sensitivity analysis

Here, we briefly discussion the sensitivity of MetaOptimize to its meta-meta-parameters.

For the meta-stepsize η \eta in MetaOptimize, there is generally no need for tuning, and the default value η = 10 − 3 \eta=10^{-3} works universally well in stationary supervised learning. All experiments in this section used this default value with no sweeping required. The rationale for this choice is that when using Adam, Lion, or RMSProp for meta-updates, the absolute change in β \beta per iteration is approximately η × O ⁡ ( 1 ) ≃ 10 − 3 \eta\times O(1)\simeq 10^{-3} . Unless the current stepsize α \alpha is already near its optimal value, most β \beta updates will consistently move toward the optimal β \beta . Within 1,000 steps, β \beta can change by O ⁡ ( 1 ) O(1) , nearly doubling or halving α = exp ⁡ ( β ) \alpha=\exp(\beta) . Over 10,000 iterations, α \alpha can adjust to stepsizes that are e 10 > 20,000 e^{10}>20,000 times larger or smaller, allowing η ≃ 10 − 3 \eta\simeq 10^{-3} to efficiently track optimal stepsizes while minimizing unnecessary fluctuations in α \alpha .

Regarding the discount factor γ \gamma , we used the γ = 1 \gamma=1 in all stationary experiments and observed minimal sensitivity to γ \gamma for values γ ≥ 0.999 \gamma\geq 0.999 in a series of preliminary tests. However, performance begins to degrade with smaller values of γ \gamma . In the non-stationary CIFAR100, γ = 0.999 \gamma=0.999 performed slightly better than 1 1 .

## 8 Related Works

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 ) , nested hyper-gradient descent ( Chandra et al., 2022 ) , distance to a solution adaptation ( Ivgi et al., 2023 ; Defazio & Mishchenko, 2023 ; Mishchenko & Defazio, 2023 ) , and online convex learning ( Cutkosky et al., 2024 ) . 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 ) . Moreover, 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 AdaGrad ( Duchi et al., 2011 ) , RMSProp, and Adam have significantly enhanced the training process. 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, introduced in ( Sutton, 1992 ) , which aimed to optimize the step-size vector to minimize a specific form of quadratic loss functions in a continual setting. This algorithm was later extended for neural networks in ( Xu et al., 2018 ; Donini et al., 2019 ) , and further adapted in ( Mahmood et al., 2012 ; Javed, 2020 ; Micaelli & Storkey, 2021 ) for different meta or base updates beyond 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. These extensions are, in essence, special cases of the L-approximation within the MetaOptimize framework. The current work 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 ) , and reinforcement learning ( Xu et al., 2018 ; Young et al., 2018 ; Javed et al., 2024 ) . Refer to ( Sutton, 2022 ) for a comprehensive history of step-size optimization.

Hypergradient Descent (HD) ( Baydin et al., 2017 ) adapts learning rates using immediate loss gradients. MADA ( Ozkara et al., 2024 ) extends HD by parameterizing a space of optimizers and navigating it via hypergradient descent. Both focus on short-term effects, whereas MetaOptimize introduces a discount factor γ \gamma to model long-term influences, generalizing HD as a special case when γ = 0 \gamma=0 .

A related line of work is gradient-based bilevel optimization, initially introduced by ( Bengio, 2000 ) and later expanded in ( Maclaurin et al., 2015 ; Pedregosa, 2016 ; Franceschi et al., 2018 ; Gao et al., 2022 ) . Recent advances, such as ( Lorraine et al., 2020 ) , enable the optimization of millions of hyperparameters. While bilevel optimization focuses on tuning hyperparameters to minimize validation loss through repeated full training runs of the base algorithm, MetaOptimize diverges significantly. Designed for continual learning, MetaOptimize optimizes meta-parameters on-the-fly during a single streaming run, without relying on validation loss. Instead, it minimizes online loss (or regret) directly, aligning with the continual learning framework where no validation or test sets exist, and data arrives sequentially.

Another relevant literature is learn to optimize (L2O), which aim to learn optimization strategies from data. Classical L2O methods such as ( Andrychowicz et al., 2016 ) train optimizers offline and deploy them unchanged. Later works, including ( Metz et al., 2020 ; Metz et al., 2022 ) , develop more effective or scalable architectures, often using neural networks to modulate optimizer behavior. While powerful, these methods typically lack the ability to adapt online. In contrast, MetaOptimize updates its meta-parameters continuously during training, which is advantageous in nonstationary or continual learning scenarios.

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 ℋ t + 1 \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.

More accurate traces: As discussed in Section 3 , accuracy of the backward approximation ( 5 ) may degrade for larger values of the meta-stepsize η \eta . Eligibility traces in RL suffer from a similar problem, to resolve which more-sophisticated traces (e.g., Dutch traces) have been developed (see Chapter 11 of ( Sutton & Barto, 2018 ) ). Developing more accurate backward approximations for meta-parameter optimization can result in considerable improvements in performance and stability.

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.

Automatic Differentiation: While certain versions of MetaOptimize, such as the L-Approximation, could be implemented using standard automatic differentiation software, its applicability to the general case of MetaOptimize remains unclear. Unlike updates for 𝒘 \boldsymbol{w} and 𝜷 \boldsymbol{\beta} (base and meta parameters), the H H matrix lacks an explicit incremental formula that can be easily handled by automatic differentiation. For some versions of MetaOptimize, including the Hessian-free approximations used in our experiments, automatic differentiation is unnecessary, as meta updates do not require additional differentiation. Exploring the scope and applicability of automatic differentiation across different MetaOptimize instances is an interesting direction for future research.

Discount factor γ = 𝟏 \boldsymbol{\gamma=1} : Our backward formulation (Eq. ( 14 )) formally assumes γ < 1 \gamma<1 due to a normalization factor used in the definition of the surrogate gradient. For γ = 1 \gamma=1 , a simple workaround is to remove this scaling factor, which makes the derivation fully valid and consistent—matching our actual implementation and experiments. That said, the case γ = 1 \gamma=1 presents subtle theoretical differences, much like in reinforcement learning and dynamic programming where additional centering is often helpful. Adapting similar techniques for meta-optimization may yield benefits and is a promising direction for future work.

## Impact Statement

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

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

In this appendix, we derive G t G_{t} defined in ( 9 ) 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_{t} , G t meta ​ = def ​ [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t ] , G^{\textrm{meta}}_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right], (17) G t base ​ = def ​ [ d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] . G^{\textrm{base}}_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]. (18) Then, G t = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ G t meta G t base ] . G_{t}={\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]}=\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {G^{\textrm{meta}}_{t}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {G^{\textrm{base}}_{t}}\\ \\ \end{array}\end{array}\right]. (19)

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

Notation conventions in all Appendices: 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 σ ′ ​ ( 𝜷 t ) \sigma^{\prime}(\boldsymbol{\beta}_{t}) the Jacobian of 𝜶 t \boldsymbol{\alpha}_{t} with respect to 𝜷 t \boldsymbol{\beta}_{t} .

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

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

We start by simplifying G meta 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, d ​ 𝒚 t + 1 d ​ 𝒙 ~ t = 0 . \frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{x}}_{t}}=0. (20) Then, G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t d ​ 𝒚 t + 1 d ​ 𝒙 ~ t d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] , G^{\textrm{meta}}_{t}=\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{x}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right], (21) where the third equality is due to ( 20 ). Let L t ​ = def ​ [ ∇ f t ( 𝒘 t ) T 0 0 0 0 ∇ f t ( 𝒘 t ) T 0 0 0 0 ⋱ 0 0 0 0 ∇ f t ( 𝒘 t ) T ] ​ ← 1 ← 2 ⋮ ← m 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}\\ \quad\nabla f_{t}(\boldsymbol{w}_{t})^{T}\end{array}&0&0\\ \hline\cr 0&0&\begin{array}[]{c}\\ \quad\ddots\\ \\ \end{array}&0\\ \hline\cr 0&0&0&\begin{array}[]{c}\\ \quad\nabla f_{t}(\boldsymbol{w}_{t})^{T}\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{0.75,0.75,0.75}\leftarrow 1}\end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow 2}\end{array}\\ \begin{array}[]{c}\\ \,\,{\color[rgb]{0.75,0.75,0.75}\vdots}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow m}\end{array}\end{array} (22) and recall that 𝒉 t \boldsymbol{h}_{t} is a vectorization of ℋ t \mathcal{H}_{t} . Then, ℋ t ∇ f t ( 𝒘 t ) = L t 𝒉 t . \mathcal{H}_{t}\nabla f_{t}(\boldsymbol{w}_{t})=L_{t}\boldsymbol{h}_{t}. (23)

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

#### A.1.1 Meta SGD

Here, we consider SGD for the meta update ( 8 ), 𝜷 t + 1 = 𝜷 t − η ∇ 𝜷 F ^ t = 𝜷 t − η ℋ t T ∇ f t ( 𝒘 t ) , \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}), (24) where η \eta is a scalar, called the meta step size . In this case, 𝒚 t = 𝜷 t \boldsymbol{y}_{t}=\boldsymbol{\beta}_{t} . It then follows from ( 24 ) that d ​ 𝜷 t + 1 d ​ 𝒉 t = − η d d ​ 𝒉 t ( ℋ t T ∇ f t ( 𝒘 t ) ) = − η d d ​ 𝒉 t ( L t 𝒉 t ) = − η L t , \frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}\,=\,-\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})\big)\,=\,-\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(L_{t}\boldsymbol{h}_{t}\big)\,=\,-\eta L_{t}, (25) where the second equality is due to ( 23 ). Consequently, from ( 21 ), we obtain G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝜷 t + 1 d ​ 𝜷 t d ​ 𝜷 t + 1 d ​ 𝒘 t 0 d ​ 𝜷 t + 1 d ​ 𝒉 t ] = [ I − η ​ ℋ t T ​ ∇ 2 f t ​ ( 𝒘 t ) 0 − η ​ L t ] , \begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {I}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {-\eta\mathcal{H}^{T}_{t}\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {-\eta L_{t}}\\ \\ \end{array}\end{array}\right],\end{split} (26) where the last equality follows from ( 25 ) and simple differentiations of ( 24 ). Here, ∇ 2 f t ​ ( 𝒘 t ) \nabla^{2}f_{t}(\boldsymbol{w}_{t}) denotes the Hessian of f t f_{t} at 𝒘 t \boldsymbol{w}_{t} .

#### A.1.2 Meta Adam

The meta update based on the Adam algorithm is as follows, 𝒎 ¯ t + 1 = ρ ¯ 𝒎 ¯ t + ℋ t T ∇ f t ( 𝒘 t ) , 𝒗 ¯ t + 1 = λ ¯ 𝒗 t + ( ℋ t T ∇ f t ( 𝒘 t ) ) 2 , μ ¯ t = ( 1 − ρ ¯ 1 − ρ ¯ t ) / 1 − λ ¯ 1 − λ ¯ t , 𝜷 t + 1 = 𝜷 t − η ​ μ ¯ t ​ 𝒎 ¯ t 𝒗 ¯ t \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]{0.75,0.75,0.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} (27) where 𝒎 ¯ t \bar{\boldsymbol{m}}_{t} is the momentum vector, 𝒗 ¯ t \vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t} is the trace of squared surrogate-meta-gradient. Since Adam algorithm needs to keep track of 𝜷 t \boldsymbol{\beta}_{t} , 𝒎 ¯ t \bar{\boldsymbol{m}}_{t} , and 𝒗 ¯ t \vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t} , we have 𝒚 t = [ 𝜷 t 𝒎 ¯ t 𝒗 ¯ t ] . \boldsymbol{y}_{t}=\left[\begin{array}[]{c}\boldsymbol{\beta}_{t}\\ \bar{\boldsymbol{m}}_{t}\\ \vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}\end{array}\right]. (28) Recall the following notation convention at the end of the Introduction section: for any k ≥ 1 k\geq 1 , and any k k -dimensional vector 𝒗 = [ v 1 , … , v k ] \boldsymbol{v}=[v_{1},\ldots,v_{k}] , we denote the the corresponding diagonal matrix by [ 𝒗 ] \left[\boldsymbol{v}\right] : [ 𝒗 ] ​ = def ​ [ v 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ v k ] . \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]. (29) Consequently, from ( 21 ), we obtain G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝜷 t + 1 d ​ 𝜷 t d ​ 𝜷 t + 1 d ​ 𝒎 ¯ t d ​ 𝜷 t + 1 d ​ 𝒗 ¯ t d ​ 𝜷 t + 1 d ​ 𝒘 t 0 d ​ 𝜷 t + 1 d ​ 𝒉 t d ​ 𝒎 ¯ t + 1 d ​ 𝜷 t d ​ 𝒎 ¯ t + 1 d ​ 𝒎 ¯ t d ​ 𝒎 ¯ t + 1 d ​ 𝒗 ¯ t d ​ 𝒎 ¯ t + 1 d ​ 𝒘 t 0 d ​ 𝒎 ¯ t + 1 d ​ 𝒉 t d ​ 𝒗 ¯ ​ t + 1 d ​ 𝜷 t d ​ 𝒗 ¯ ​ t + 1 d ​ 𝒎 ¯ t d ​ 𝒗 ¯ ​ t + 1 d ​ 𝒗 ¯ t d ​ 𝒗 ¯ ​ t + 1 d ​ 𝒘 t 0 d ​ 𝒗 ¯ ​ t + 1 d ​ 𝒉 t ] = [ I − η ​ μ ¯ t ​ [ 1 𝒗 ¯ t ] η ​ μ ¯ t 2 ​ [ 𝒎 ¯ t 𝒗 ¯ t 1.5 ] 0 0 0 0 ρ ¯ ​ I 0 ℋ t T ​ ∇ 2 f t 0 d ​ 𝒎 ¯ t + 1 d ​ 𝒉 t 0 0 λ ¯ ​ I 2 [ ℋ t T ∇ f t ] ℋ t T ∇ 2 f t 0 d ​ 𝒗 ¯ t + 1 d ​ 𝒉 t ] , \begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{c|cc|c}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{ccc|cc|c}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \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{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{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{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}\end{array}\right],\end{split} (30) where the last equality follows by calculating derivatives of ( 27 ). For the two remaining terms in the last column of G t G_{t} , we have d ​ 𝒎 ¯ t + 1 d ​ 𝒉 t = d d ​ 𝒉 t ( ℋ t T ∇ f t ( 𝒘 t ) ) = η d d ​ 𝒉 t ( L t 𝒉 t ) = η L t . \frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}\,=\,\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})\big)\,=\,\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(L_{t}\boldsymbol{h}_{t}\big)\,=\eta\,L_{t}. (31) where the first equality follows from the update of 𝒎 ¯ t + 1 \bar{\boldsymbol{m}}_{t+1} in ( 27 ), and the second equality is due to ( 23 ). In the same vein, d ​ 𝒗 ¯ t + 1 d ​ 𝒉 t = d d ​ 𝒉 t ( ℋ t T ∇ f t ( 𝒘 t ) ) 2 = d d ​ 𝒉 t ( L t 𝒉 t ) 2 = 2 [ L t 𝒉 t ] d d ​ 𝒉 t ( L t 𝒉 t ) = 2 [ L t 𝒉 t ] L t = 2 [ ℋ t T ∇ f t ( 𝒘 t ) ] L t , \frac{\mathrm{d}\,\vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}\,=\,\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})\big)^{2}\,=\,\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(L_{t}\boldsymbol{h}_{t}\big)^{2}\,=\,2\big[L_{t}\boldsymbol{h}_{t}\big]\frac{\mathrm{d}\,}{\mathrm{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}, (32) where the first equality follows from the update of 𝒗 ¯ t + 1 \vphantom{\tilde{\zeta}}\bar{\boldsymbol{v}}_{t+1} in ( 27 ), the second equality is due to ( 23 ), and the last equality is again from ( 23 ).

Plugging ( 31 ) and ( 32 ) into ( 30 ), we obtain G t meta = [ I − η ​ μ ¯ t ​ [ 1 𝒗 ¯ t ] η ​ μ ¯ t 2 ​ [ 𝒎 ¯ t 𝒗 ¯ t 1.5 ] 0 0 0 0 ρ ¯ ​ I 0 ℋ t T ​ ∇ 2 f t 0 η ​ L t 0 0 λ ¯ ​ I 2 [ ℋ t T ∇ f t ] ℋ t T ∇ 2 f t 0 2 [ ℋ t T ∇ f t ] L t ] . 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]. (33)

#### A.1.3 Meta Lion

The meta update based on the lion algorithm is as follows 𝒎 ¯ t + 1 = ρ ​ 𝒎 ¯ t + ( 1 − ρ ) ​ ∇ 𝜷 F ^ t , \displaystyle\bar{\boldsymbol{m}}_{t+1}=\rho\,\bar{\boldsymbol{m}}_{t}+(1-\rho)\,\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}, (34) 𝜷 t + 1 = 𝜷 t − η ​ Sign ⁡ ( c ​ 𝒎 ¯ t + ( 1 − c ) ​ ∇ 𝜷 F ^ t ) , \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), (35) where η \eta is a scalar, called the meta step size , and ρ , c ∈ [ 0 , 1 ) \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 ∇ 𝜷 F ^ t \widehat{\nabla_{\boldsymbol{\beta}}F}_{t} with ℋ t T ∇ f t ( 𝒘 t ) \mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t}) we obtain the following meta updates 𝒎 ¯ t + 1 = ρ 𝒎 ¯ t + ( 1 − ρ ) ℋ t T ∇ f t ( 𝒘 t ) , \displaystyle\bar{\boldsymbol{m}}_{t+1}=\rho\,\bar{\boldsymbol{m}}_{t}+(1-\rho)\,\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t}), (36) 𝜷 t + 1 = 𝜷 t − η Sign ( c 𝒎 ¯ t + ( 1 − c ) ℋ t T ∇ f t ( 𝒘 t ) ) . \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). (37) In this case, 𝒚 t = [ 𝜷 t 𝒎 ¯ t ] , \boldsymbol{y}_{t}=\left[\begin{array}[]{c}\boldsymbol{\beta}_{t}\\ \bar{\boldsymbol{m}}_{t}\end{array}\right], and G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝜷 t + 1 d ​ 𝜷 t d ​ 𝜷 t + 1 d ​ 𝒎 ¯ t d ​ 𝜷 t + 1 d ​ 𝒘 t 0 d ​ 𝜷 t + 1 d ​ 𝒉 t d ​ 𝒎 ¯ t + 1 d ​ 𝜷 t d ​ 𝒎 ¯ t + 1 d ​ 𝒎 ¯ t d ​ 𝒎 ¯ t + 1 d ​ 𝒘 t 0 d ​ 𝒎 ¯ t + 1 d ​ 𝒉 t ] = [ I 0 0 0 0 d ​ 𝒎 ¯ t + 1 d ​ 𝜷 t d ​ 𝒎 ¯ t + 1 d ​ 𝒎 ¯ t d ​ 𝒎 ¯ t + 1 d ​ 𝒘 t 0 d ​ 𝒎 ¯ t + 1 d ​ 𝒉 t ] , \begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{ccccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{ccccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{ccccc}\hskip-7.0pt\begin{array}[]{c}\\ {I}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right],\end{split} (38) where the last equality follows from ( 37 ). Consider the following block representation of Y t Y_{t} : Y t = [ B t Y t m ¯ ] . Y_{t}=\left[\begin{array}[]{c}B_{t}\\ Y^{\bar{m}}_{t}\end{array}\right]. (39) Since the base algorithm, does not take 𝒎 ¯ \bar{\boldsymbol{m}} as input, as we will see in ( 41 ) and ( 42 ) of next subsection (Appendix A.2 ), d ​ 𝒎 ¯ t + 1 d ​ 𝒎 ¯ t \frac{\mathrm{d}\,\bar{\boldsymbol{m}}_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}} is the only non-zero block of G t G_{t} in its column of blocks (i.e., d ​ s t + 1 d ​ 𝒎 ¯ t = 0 \frac{\mathrm{d}\,s_{t+1}}{\mathrm{d}\,\bar{\boldsymbol{m}}_{t}}=0 for every variable s s other than 𝒎 ¯ \bar{\boldsymbol{m}} ). Consequently, it follows from ( 14 ) that Y t m ¯ Y^{\bar{m}}_{t} as defined in ( 39 ), has no impact on the update of X t + 1 X_{t+1} , B t + 1 B_{t+1} , and Q t + 1 Q_{t+1} . Therefore, we can zero-out the rows and columns of G meta G^{\textrm{meta}} that correspond to derivative of 𝒎 ¯ \bar{\boldsymbol{m}} . As such we obtain the following equivalent of G meta G^{\textrm{meta}} in ( 38 ) from an algorithmic perspective: G t meta ≡ [ I m × m 0 0 0 ] . \begin{split}G^{\textrm{meta}}_{t}\equiv\left[\begin{array}[]{cc}\hskip-7.0pt\begin{array}[]{c}\\ {I_{m\times m}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\end{array}\right].\end{split} (40) As a result, we get B t = I B_{t}=I for all times t t .

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

We now turn our focus to computation of G base G^{\textrm{base}} . Let us start by simplifying G base 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, d ​ 𝒙 t + 1 d ​ 𝒚 ~ t = 0 . \frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}=0. (41) Moreover, it follows from the definition of ℋ t \mathcal{H}_{t} in ( 7 ) that d ​ ℋ t + 1 d ​ 𝒚 ~ t = ( 1 − γ ) ​ ∑ t = 0 t γ t − τ ​ d d ​ 𝒚 ~ t ​ ( d ​ 𝒘 t + 1 d ​ 𝜷 τ ) = ( 1 − γ ) ​ ∑ t = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( d ​ 𝒘 t + 1 d ​ 𝒚 ~ t ) = ( 1 − γ ) ​ ∑ t = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( 0 ) = 0 , \frac{\mathrm{d}\,\mathcal{H}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{d\tilde{\boldsymbol{y}}_{t}}\,\left(\frac{d\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\right)=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{d\boldsymbol{\beta}_{\tau}}\,\left(\frac{d\boldsymbol{w}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}\right)=(1-\gamma)\sum_{t=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{d\boldsymbol{\beta}_{\tau}}\,\left(0\right)=0, where the third equality follows from ( 41 ). Therefore, d ​ 𝒉 t + 1 d ​ 𝒚 ~ t = 0 . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}=0. (42) Note also that Alg base \operatorname{Alg}_{\textrm{base}} does not take ℋ t \mathcal{H}_{t} as input, and therefore, d ​ 𝒙 t + 1 d ​ 𝒉 t = 0 . \frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}=0. (43) Consequently, we can simplify G t base G^{\textrm{base}}_{t} as follows, G t base = [ d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒙 t + 1 d ​ 𝜷 t d ​ 𝒙 t + 1 d ​ 𝒚 ~ t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝜷 t d ​ 𝒉 t + 1 d ​ 𝒚 ~ t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒙 t + 1 d ​ 𝜷 t 0 d ​ 𝒙 t + 1 d ​ 𝒙 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] , G^{\textrm{base}}_{t}=\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{y}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right], (44) where the last equality is due to ( 41 ), ( 42 ), and ( 43 ).

On an independent note, consider the following block representation of Y t Y_{t} , Y t = [ B t − 1 − γ γ ​ I Y ~ t ] , Y_{t}=\left[\begin{array}[]{c}B_{t}-\frac{1-\gamma}{\gamma}I\\ \tilde{Y}_{t}\end{array}\right], (45) Therefore, γ ​ Y t + ( 1 − γ ) ​ [ I 0 ] = γ ​ [ B t Y ~ t ] \gamma Y_{t}+(1-\gamma)\left[\begin{array}[]{c}I\\ 0\end{array}\right]=\gamma\,\left[\begin{array}[]{c}B_{t}\\ \tilde{Y}_{t}\end{array}\right] It then follows from ( 19 ) and ( 14 ) that [ X t + 1 Q t + 1 ] = γ ​ G t base ​ [ [ B t Y ~ t ] X t Q t ] . \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]. (46) Moreover, from the definition of Y t Y_{t} in ( 11 ), we have d ​ B t d ​ 𝒙 t = ( 1 − γ ) ​ d d ​ 𝒙 t ​ ∑ τ = 0 t γ t − τ ​ d ​ 𝜷 t d ​ 𝜷 τ = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( d ​ 𝜷 t d ​ 𝒙 t ) = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( 0 ) = 0 , d ​ B t d ​ 𝜷 t = ( 1 − γ ) ​ d d ​ 𝜷 t ​ ∑ τ = 0 t γ t − τ ​ d ​ 𝜷 t d ​ 𝜷 τ = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( d ​ 𝜷 t d ​ 𝜷 t ) = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( I ) = 0 , d ​ B t d ​ 𝒉 t = ( 1 − γ ) ​ d d ​ 𝒉 t ​ ∑ τ = 0 t γ t − τ ​ d ​ 𝜷 t d ​ 𝜷 τ = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( d ​ 𝜷 t d ​ 𝒉 t ) = ( 1 − γ ) ​ ∑ τ = 0 t γ t − τ ​ d d ​ 𝜷 τ ​ ( 0 ) = 0 . \begin{split}\frac{\mathrm{d}\,B_{t}}{\mathrm{d}\,\boldsymbol{x}_{t}}&=(1-\gamma)\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{x}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\left(\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{x}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\big(0\big)=0,\\ \frac{\mathrm{d}\,B_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}&=(1-\gamma)\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\left(\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\big(I\big)=0,\\ \frac{\mathrm{d}\,B_{t}}{\mathrm{d}\,\boldsymbol{h}_{t}}&=(1-\gamma)\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\left(\frac{\mathrm{d}\,\boldsymbol{\beta}_{t}}{\mathrm{d}\,\boldsymbol{h}_{t}}\right)=(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{\beta}_{\tau}}\big(0\big)=0.\end{split} (47)

Finally, recall the definition σ ′ ​ ( 𝜷 t ) ​ = def ​ d ​ 𝜶 t d ​ 𝜷 t \sigma^{\prime}(\boldsymbol{\beta}_{t})\overset{\text{\tiny def}}{=}\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}} (48) as the Jacobian of 𝜶 t \boldsymbol{\alpha}_{t} with respect to 𝜷 t \boldsymbol{\beta}_{t} .

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

### A.3 Base SGD

Base SGD algorithm makes the following base update in each iteration: 𝒘 t + 1 = 𝒘 t − 𝜶 t ∇ f t ( 𝒘 t ) . \boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t}\nabla f_{t}(\boldsymbol{w}_{t}). (49) In this case, 𝒙 t = 𝒘 t \boldsymbol{x}_{t}=\boldsymbol{w}_{t} and X t = ℋ t X_{t}=\mathcal{H}_{t} . Then, G t base G^{\textrm{base}}_{t} in ( 44 ) can be simplified to G t base = [ d ​ 𝒙 t + 1 d ​ 𝜷 t 0 d ​ 𝒙 t + 1 d ​ 𝒙 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒘 t + 1 d ​ 𝜷 t 0 d ​ 𝒘 t + 1 d ​ 𝒘 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ − [ ∇ f t ​ ( 𝒘 t ) ] ​ σ ′ ​ ( 𝜷 t ) 0 I − [ 𝜶 t ] ​ ∇ 2 f t ​ ( 𝒘 t ) 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] , \begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \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\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right],\end{split} (50) where the last equality follows by computing simple derivatives of 𝒘 t + 1 \boldsymbol{w}_{t+1} in ( 49 ).

We proceed to compute the three remaining entries of G t base G^{\textrm{base}}_{t} , i.e., d ​ 𝒉 t + 1 / d ​ 𝜷 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{\beta}_{t}} , d ​ 𝒉 t + 1 / d ​ 𝒘 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{w}_{t}} , and d ​ 𝒉 t + 1 / d ​ 𝒉 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{h}_{t}} . Note that by plugging the first row of G t base G^{\textrm{base}}_{t} , given in ( 50 ), into ( 46 ), and noting that ℋ t = X t \mathcal{H}_{t}=X_{t} , we obtain ℋ t + 1 = γ ⁡ ( I − [ 𝜶 t ] ​ ∇ 2 f t ​ ( 𝒘 t ) ) ​ ℋ t − γ ⁡ [ ∇ f t ​ ( 𝒘 t ) ] ​ σ ′ ​ ( 𝜷 t ) ​ B t , \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}, (51) for all t ≥ 0 t\geq 0 . By vectorizing both sides of ( 51 ) we obtain 𝒉 t + 1 = γ ⁡ [ ( I − [ 𝜶 t ] ​ ∇ 2 f t ) ​ ℋ t [ 1 ] − [ ∇ f t ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ( I − [ 𝜶 t ] ​ ∇ 2 f t ) ​ ℋ t [ 2 ] − [ ∇ f t ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ 2 ] ⋮ ( I − [ 𝜶 t ] ​ ∇ 2 f t ) ​ ℋ t [ m ] − [ ∇ f t ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ] . \boldsymbol{h}_{t+1}\,=\,\gamma\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\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]}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\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]}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\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]}}\\ \\ \end{array}\end{array}\right]. (52) 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, ( 52 ) can be equivalently written in the following form 𝒉 t + 1 = γ ⁡ [ ( I − [ 𝜶 t ] ∇ 2 f t ) ℋ t [ 1 ] − [ σ ′ ( 𝜷 t ) B t [ 1 ] ] ∇ f t ⋮ ( I − [ 𝜶 t ] ∇ 2 f t ) ℋ t [ m ] − [ σ ′ ( 𝜷 t ) B t [ m ] ] ∇ f t ] . \boldsymbol{h}_{t+1}\,=\,\gamma\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\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}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\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}}\\ \\ \end{array}\end{array}\right]. (53)

By taking the derivative of ( 52 ) with respect to 𝒉 t \boldsymbol{h}_{t} , we obtain d ​ 𝒉 t + 1 d ​ 𝒉 t = γ ⁡ [ I − [ 𝜶 t ] ​ ∇ 2 f t ​ ( 𝒘 t ) 0 0 0 0 I − [ 𝜶 t ] ​ ∇ 2 f t ​ ( 𝒘 t ) 0 0 0 0 ⋱ 0 0 0 0 I − [ 𝜶 t ] ​ ∇ 2 f t ​ ( 𝒘 t ) ] ​ ← 1 ​ st ← 2 ​ nd ⋮ ← m ​ th . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{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})\\ \\ \end{array}&0&0&0\\ \hline\cr 0&\begin{array}[]{c}\\ I-\left[\boldsymbol{\alpha}_{t}\right]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})\\ \\ \end{array}&0&0\\ \hline\cr 0&0&\begin{array}[]{c}\\ \ddots\\ \\ \end{array}&0\\ \hline\cr 0&0&0&\begin{array}[]{c}\\ 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]{0.75,0.75,0.75}\leftarrow 1\textrm{st}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow 2\textrm{nd}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ \,\,{\color[rgb]{0.75,0.75,0.75}\vdots}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow m\textrm{th}}\end{array}\end{array}. (54) In the above equation, note that d ​ B t / d ​ 𝒉 t = 0 \mathrm{d}\,B_{t}/\mathrm{d}\,\boldsymbol{h}_{t}=0 due to ( 47 ). Let β t ​ [ i ] \beta_{t}[i] and w t ​ [ j ] w_{t}[j] denote the i i th and j j th entries of 𝜷 t \boldsymbol{\beta}_{t} and 𝒘 t \boldsymbol{w}_{t} , for i = 1 , … , m i=1,\ldots,m and j = 1 , … , n j=1,\ldots,n , respectively. It then follows from ( 52 ) and ( 47 ) that d ​ 𝒉 t + 1 d ​ 𝜷 t = − γ ⁡ [ [ d ​ 𝜶 t d ​ β t ​ [ 1 ] ] ​ ∇ 2 f t ​ ℋ t [ 1 ] + [ ∇ f t ] ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ 1 ] ​ B t [ 1 ] ⋯ [ d ​ 𝜶 t d ​ β t ​ [ m ] ] ​ ∇ 2 f t ​ ℋ t [ 1 ] + [ ∇ f t ] ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ m ] ​ B t [ 1 ] ⋮ ⋱ ⋮ [ d ​ 𝜶 t d ​ β t ​ [ 1 ] ] ​ ∇ 2 f t ​ ℋ t [ m ] + [ ∇ f t ] ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ 1 ] ​ B t [ m ] ⋯ [ d ​ 𝜶 t d ​ β t ​ [ m ] ] ​ ∇ 2 f t ​ ℋ t [ m ] + [ ∇ f t ] ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ m ] ​ B t [ m ] ] , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\cdots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\ddots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\cdots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}\end{array}\right], (55) 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, ( 53 ) and ( 47 ) imply that d ​ 𝒉 t + 1 d ​ 𝒘 t = − γ ⁡ [ [ 𝜶 t ] ​ d ⁡ ( ∇ 2 f t ​ ( 𝒘 t ) ​ ℋ t [ 1 ] ) d ​ 𝒘 t + [ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ] ​ ∇ 2 f t ​ ( 𝒘 t ) ⋮ [ 𝜶 t ] ​ d ⁡ ( ∇ 2 f t ​ ( 𝒘 t ) ​ ℋ t [ m ] ) d ​ 𝒘 t + [ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ] ​ ∇ 2 f t ​ ( 𝒘 t ) ] . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}=-\gamma\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{\alpha}_{t}\right]\frac{\mathrm{d}\,(\nabla^{2}f_{t}(\boldsymbol{w}_{t})\,\mathcal{H}_{t}^{[1]})}{\mathrm{d}\,\boldsymbol{w}_{t}}\,+\,\big[\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}\big]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{\alpha}_{t}\right]\frac{\mathrm{d}\,(\nabla^{2}f_{t}(\boldsymbol{w}_{t})\,\mathcal{H}_{t}^{[{m}]})}{\mathrm{d}\,\boldsymbol{w}_{t}}\,+\,\big[\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}\big]\,\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\ \\ \end{array}\end{array}\right]. (56) Finally, G t base G^{\textrm{base}}_{t} is obtained by plugging ( 54 ), ( 55 ), and ( 56 ) into ( 50 ).

In the special case that β \boldsymbol{\beta} is a scalar (equivalently m = 1 m=1 ), and furthermore α = σ ⁡ ( β ) = e β \alpha=\sigma(\beta)=e^{\beta} , matrix G t base G^{\textrm{base}}_{t} would be simplified to G t base (scalar) = [ 1 − η ​ 𝒉 t T ​ ∇ 2 f t ​ ( 𝒘 t ) − η ∇ f t ( 𝒘 t ) T − α ∇ f t ( 𝒘 t ) I − α ​ ∇ 2 f t ​ ( 𝒘 t ) 0 − γ α ∇ 2 f t ( 𝒘 t ) 𝒉 t − B t α ∇ f t ( 𝒘 t ) − γ ​ α ​ d ⁡ ( ∇ 2 f t ​ ( 𝒘 t ) ​ 𝒉 t ) d ​ 𝒘 t − B t ​ α ​ ∇ 2 f t ​ ( 𝒘 t ) γ ⁡ ( I − α ​ ∇ 2 f t ​ ( 𝒘 t ) ) ] . G_{t}^{\textrm{base (scalar)}}=\left[\begin{array}[]{cccc}\vskip 6.0pt1&-\eta\,\boldsymbol{h}_{t}^{T}\nabla^{2}f_{t}(\boldsymbol{w}_{t})&-\eta\,\nabla f_{t}(\boldsymbol{w}_{t})^{T}\\ \vskip 6.0pt-\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{\mathrm{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, 𝒎 t + 1 = ρ ​ 𝒎 t + ∇ f t ​ ( 𝒘 t ) , 𝒗 t + 1 = λ 𝒗 t + ∇ f t ( 𝒘 t ) 2 , μ t = ( 1 − ρ 1 − ρ t ) / 1 − λ 1 − λ t , 𝒘 t + 1 = 𝒘 t − 𝜶 t ​ μ t ​ 𝒎 t 𝒗 t − κ ​ 𝜶 t ​ 𝒘 t , \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]{0.75,0.75,0.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} (57) where 𝒎 t \boldsymbol{m}_{t} is the momentum vector, 𝒗 t \boldsymbol{v}_{t} is the trace of gradient square used for normalization, and κ > 0 \kappa>0 is a weight-decay parameter. Therefore the base algorithm needs to keep track of 𝒘 t , 𝒎 t , 𝒗 t \boldsymbol{w}_{t},\boldsymbol{m}_{t},\boldsymbol{v}_{t} , i.e., 𝒙 t = [ 𝒘 t 𝒎 t 𝒗 t ] . \boldsymbol{x}_{t}=\left[\begin{array}[]{c}\boldsymbol{w}_{t}\\ \hfill\boldsymbol{m}_{t}\\ \boldsymbol{v}_{t}\end{array}\right]. (58) It then follows from ( 44 ) that G t base = [ d ​ 𝒙 t + 1 d ​ 𝜷 t 0 d ​ 𝒙 t + 1 d ​ 𝒙 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒘 t + 1 d ​ 𝜷 t 0 d ​ 𝒘 t + 1 d ​ 𝒘 t d ​ 𝒘 t + 1 d ​ 𝒎 t d ​ 𝒘 t + 1 d ​ 𝒗 t 0 d ​ 𝒎 t + 1 d ​ 𝜷 t 0 d ​ 𝒎 t + 1 d ​ 𝒘 t d ​ 𝒎 t + 1 d ​ 𝒎 t d ​ 𝒎 t + 1 d ​ 𝒗 t 0 d ​ 𝒗 t + 1 d ​ 𝜷 t 0 d ​ 𝒗 t + 1 d ​ 𝒘 t d ​ 𝒗 t + 1 d ​ 𝒎 t d ​ 𝒗 t + 1 d ​ 𝒗 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒎 t d ​ 𝒉 t + 1 d ​ 𝒗 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ − μ t ​ [ 𝒎 t 𝒗 t + κ ​ 𝒘 t ] ​ σ ′ ​ ( 𝜷 t ) 0 I − κ ⁡ [ 𝜶 t ] − μ t ​ [ 𝜶 t 𝒗 t ] μ t 2 ​ [ 𝜶 t ​ 𝒎 t 𝒗 t 1.5 ] 0 0 0 ∇ 2 f t ρ ​ I 0 0 0 0 2 ​ [ ∇ f t ] ​ ∇ 2 f t 0 λ ​ I 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒎 t d ​ 𝒉 t + 1 d ​ 𝒗 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] \begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cc|ccc|c}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}&0\\ \frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}&0&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}&0\\ \frac{\mathrm{d}\,\boldsymbol{v}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}&0&\frac{\mathrm{d}\,\boldsymbol{v}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}&\frac{\mathrm{d}\,\boldsymbol{v}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&\frac{\mathrm{d}\,\boldsymbol{v}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}&0\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \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\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\end{split} (59) where the last equality follows from simple derivative computations in ( 57 ).

We proceed to compute the terms in the last row of the G t base G^{\textrm{base}}_{t} above. Consider the following block representation of X t X_{t} , X t = [ ℋ t X t m X t v ] , X_{t}=\left[\begin{array}[]{c}\mathcal{H}_{t}\\ \hfill X^{m}_{t}\\ X^{v}_{t}\end{array}\right], (60) Plugging the first row of G t base G^{\textrm{base}}_{t} , given in ( 59 ), into ( 46 ), implies that ℋ t + 1 = − γ ​ μ t ​ [ 𝒎 t 𝒗 t + κ ​ 𝒘 t ] ​ σ ′ ​ ( 𝜷 t ) ​ B t + γ ⁡ ( I − κ ⁡ [ 𝜶 t ] ) ​ ℋ t − γ ​ μ t ​ [ 𝜶 t 𝒗 t ] ​ X t m + γ ​ μ t 2 ​ [ 𝜶 t ​ 𝒎 t 𝒗 t 1.5 ] ​ X t v . \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}. (61) for all t ≥ 0 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 i th column in the matrix equation ( 61 ) can be equivalently written as ℋ t + 1 [ i ] = − γ ​ μ t ​ [ σ ′ ​ ( 𝜷 t ) ​ B t [ i ] ] ​ 𝒎 t 𝒗 t + κ ​ 𝒘 t + γ ⁡ ( I − κ ⁡ [ 𝜶 t ] ) ​ ℋ t [ i ] − γ ​ μ t ​ [ X t m ⁡ [ i ] ] ​ 𝜶 t 𝒗 t + γ ​ μ t 2 ​ [ X t v ⁡ [ i ] ] ​ 𝜶 t ​ 𝒎 t 𝒗 t 1.5 , \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}}, (62) where B t [ i ] B^{[i]}_{t} , ℋ t [ i ] \mathcal{H}^{[i]}_{t} , X t m ⁡ [ i ] X^{m\,[i]}_{t} , and X t v ⁡ [ i ] X^{v\,[i]}_{t} stand for the i i th columns of B t B_{t} , ℋ t \mathcal{H}_{t} , X t m X^{m}_{t} , and X t v X^{v}_{t} , respectively. Following similar arguments as in ( 47 ), it is easy to show that d ​ X t m d ​ 𝜷 t = d ​ X t v d ​ 𝜷 t = 0 , d ​ X t m d ​ 𝒘 t = d ​ X t v d ​ 𝒘 t = 0 , d ​ X t m d ​ 𝒎 t = d ​ X t v d ​ 𝒎 t = 0 , d ​ X t m d ​ 𝒗 t = d ​ X t v d ​ 𝒗 t = 0 , d ​ X t m d ​ 𝒉 t = d ​ X t v d ​ 𝒉 t = 0 . \begin{split}&\frac{\mathrm{d}\,X^{m}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}=\frac{\mathrm{d}\,X^{v}_{t}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}=0,\\ &\frac{\mathrm{d}\,X^{m}_{t}}{\mathrm{d}\,\boldsymbol{w}_{t}}=\frac{\mathrm{d}\,X^{v}_{t}}{\mathrm{d}\,\boldsymbol{w}_{t}}=0,\\ &\frac{\mathrm{d}\,X^{m}_{t}}{\mathrm{d}\,\boldsymbol{m}_{t}}=\frac{\mathrm{d}\,X^{v}_{t}}{\mathrm{d}\,\boldsymbol{m}_{t}}=0,\\ &\frac{\mathrm{d}\,X^{m}_{t}}{\mathrm{d}\,\boldsymbol{v}_{t}}=\frac{\mathrm{d}\,X^{v}_{t}}{\mathrm{d}\,\boldsymbol{v}_{t}}=0,\\ &\frac{\mathrm{d}\,X^{m}_{t}}{\mathrm{d}\,\boldsymbol{h}_{t}}=\frac{\mathrm{d}\,X^{v}_{t}}{\mathrm{d}\,\boldsymbol{h}_{t}}=0.\end{split} (63) Note that 𝒉 t \boldsymbol{h}_{t} is an n ​ m nm -dimensional vector derived from stacking the columns of ℋ t \mathcal{H}_{t} . Therefore, we consider a block representation of 𝒉 t \boldsymbol{h}_{t} consisting of m m blocks, each of which corresponds to a column of ℋ t \mathcal{H}_{t} . By taking the derivative of ( 61 ) with respect to 𝒉 t \boldsymbol{h}_{t} , and using ( 63 ), we obtain d ​ 𝒉 t + 1 d ​ 𝒉 t = γ ⁡ [ I − κ ⁡ [ 𝜶 t ] 0 0 0 0 I − κ ⁡ [ 𝜶 t ] 0 0 0 0 ⋱ 0 0 0 0 I − κ ⁡ [ 𝜶 t ] ] ​ ← 1 ​ st ← 2 ​ nd ⋮ ← m ​ th . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}=\gamma\,\left[\begin{array}[]{c|c|c|c}\begin{array}[]{c}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\ \\ \end{array}&0&0&0\\ \hline\cr 0&\begin{array}[]{c}\\ I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\ \\ \end{array}&0&0\\ \hline\cr 0&0&\begin{array}[]{c}\\ \ddots\\ \\ \end{array}&0\\ \hline\cr 0&0&0&\begin{array}[]{c}\\ I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{0.75,0.75,0.75}\leftarrow 1\textrm{st}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow 2\textrm{nd}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ \,\,{\color[rgb]{0.75,0.75,0.75}\vdots}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow m\textrm{th}}\end{array}\end{array}. (64) Let β t ​ [ i ] \beta_{t}[i] and w t ​ [ j ] w_{t}[j] denote the i i th and j j th entries of 𝜷 t \boldsymbol{\beta}_{t} and 𝒘 t \boldsymbol{w}_{t} , for i = 1 , … , m i=1,\ldots,m and j = 1 , … , n j=1,\ldots,n , respectively. Note that d ​ 𝒉 t + 1 / d ​ 𝜷 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{\beta}_{t}} is a block matrix, in the form of an m × m m\times m array of n × 1 n\times 1 blocks, d ​ 𝒉 t + 1 d ​ 𝜷 t ​ [ i , j ] ​ = def ​ d ​ ℋ t + 1 [ i ] d ​ β t ​ [ j ] \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}[i,j]\overset{\text{\tiny def}}{=}\frac{\mathrm{d}\,\mathcal{H}_{t+1}^{[i]}}{\mathrm{d}\,\beta_{t}[j]} , for i , j = 1 , … , m i,j=1,\ldots,m . It then follows from ( 61 ) and ( 63 ) that, for i , j = 1 , … , m i,j=1,\ldots,m , d ​ 𝒉 t + 1 d ​ 𝜷 t ​ [ i , j ] = d ​ ℋ t + 1 [ i ] d ​ β t ​ [ j ] = − γ ​ μ t ​ [ 𝒎 t 𝒗 t + κ ​ 𝒘 t ] ​ ( ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ j ] ) ​ B t [ i ] + γ ⁡ ( I − κ ⁡ [ d ​ 𝜶 t d ​ β t ​ [ j ] ] ) ​ ℋ t [ i ] − γ ​ μ t ​ [ 1 𝒗 t ] ​ [ d ​ 𝜶 t d ​ β t ​ [ j ] ] ​ X t m ⁡ [ i ] + γ ​ μ t 2 ​ [ 𝒎 t 𝒗 t 1.5 ] ​ [ d ​ 𝜶 t d ​ β t ​ [ j ] ] ​ X t v ⁡ [ i ] , \begin{split}\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}[i,j]=&\frac{\mathrm{d}\,\mathcal{H}_{t+1}^{[i]}}{\mathrm{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{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{d}\,\beta_{t}[j]}\Big]\right)\mathcal{H}^{[i]}_{t}\\ \,&-\,\gamma\mu_{t}\Big[\frac{1}{\sqrt{\boldsymbol{v}_{t}}}\Big]\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{d}\,\beta_{t}[j]}\Big]\,X^{v\,[i]}_{t},\end{split} (65) 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 ( 62 ) and ( 63 ) that d ​ 𝒉 t + 1 d ​ 𝒘 t = − γ ​ μ t ​ κ ​ [ [ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ] ⋮ [ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ] ] , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}=-\gamma\mu_{t}\kappa\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[1]}_{t}\Big]}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\Big[\sigma^{\prime}(\boldsymbol{\beta}_{t})B^{[m]}_{t}\Big]}\\ \\ \end{array}\end{array}\right], (66) d ​ 𝒉 t + 1 d ​ 𝒎 t = γ ​ μ t ​ [ [ 𝜶 t ​ X t v ⁡ [ 1 ] 2 ​ 𝒗 t 1.5 − σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] 𝒗 t ] ⋮ [ 𝜶 t ​ X t v ⁡ [ m ] 2 ​ 𝒗 t 1.5 − σ ′ ​ ( 𝜷 t ) ​ B t [ m ] 𝒗 t ] ] , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}=\gamma\mu_{t}\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\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]}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\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]}\\ \\ \end{array}\end{array}\right], (67) d ​ 𝒉 t + 1 d ​ 𝒗 t = γ ​ μ t 2 ​ [ [ 1 𝒗 t 1.5 ] ​ [ ( σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ) ​ 𝒎 t + 𝜶 t ​ X t m ⁡ [ 1 ] − 3 ​ 𝜶 t ​ 𝒎 t ​ X t v ⁡ [ 1 ] 2 ​ 𝒗 t ] ⋮ [ 1 𝒗 t 1.5 ] ​ [ ( σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ) ​ 𝒎 t + 𝜶 t ​ X t m ⁡ [ m ] − 3 ​ 𝜶 t ​ 𝒎 t ​ X t v ⁡ [ m ] 2 ​ 𝒗 t ] ] . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{v}_{t}}=\frac{\gamma\mu_{t}}{2}\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {\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]}\\ \\ \end{array}\par\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\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]}\\ \\ \end{array}\end{array}\right]. (68)

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

#### A.3.2 Base Lion

The lion algorithm, when used for base update, is as follows 𝒎 t + 1 = ρ 𝒎 t + ( 1 − ρ ) ∇ f t ( 𝒘 t ) , \displaystyle\boldsymbol{m}_{t+1}=\rho\,\boldsymbol{m}_{t}+(1-\rho)\,\nabla f_{t}(\boldsymbol{w}_{t}), (69) 𝒘 t + 1 = 𝒘 t − 𝜶 t Sign ( c 𝒎 t + ( 1 − c ) ∇ f t ) − κ 𝜶 t 𝒘 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}, (70) where 𝒎 t \boldsymbol{m}_{t} is called the momentum, κ > 0 \kappa>0 is the weight-decay parameter, ρ , c ∈ [ 0 , 1 ) \rho,c\in[0,1) are constants, and Sign ⁡ ( ⋅ ) \operatorname{Sign}(\cdot) is a function that computes entry-wise sign of a vector. Let 𝒙 t = [ 𝒘 t 𝒎 t ] . \boldsymbol{x}_{t}=\left[\begin{array}[]{c}\boldsymbol{w}_{t}\\ \hfill\boldsymbol{m}_{t}\end{array}\right]. (71) It then follows from ( 44 ) that G t base = [ d ​ 𝒙 t + 1 d ​ 𝜷 t 0 d ​ 𝒙 t + 1 d ​ 𝒙 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒘 t + 1 d ​ 𝜷 t 0 d ​ 𝒘 t + 1 d ​ 𝒘 t d ​ 𝒘 t + 1 d ​ 𝒎 t 0 d ​ 𝒎 t + 1 d ​ 𝜷 t 0 d ​ 𝒎 t + 1 d ​ 𝒘 t d ​ 𝒎 t + 1 d ​ 𝒎 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒎 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ − [ Sign ( c 𝒎 t + ( 1 − c ) ∇ f t ) + κ 𝒘 t ] σ ′ ( 𝜷 t ) 0 I − κ ⁡ [ 𝜶 t ] 0 0 d ​ 𝒎 t + 1 d ​ 𝜷 t 0 d ​ 𝒎 t + 1 d ​ 𝒘 t d ​ 𝒎 t + 1 d ​ 𝒎 t 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒎 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] \begin{split}G^{\textrm{base}}_{t}&=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{ccccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\frac{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&0\\ \frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}&0&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{ccccc}-\hskip-7.0pt\begin{array}[]{c}\\ {\big[\operatorname{Sign}\big(c\,\boldsymbol{m}_{t}+(1-c)\nabla f_{t}\big)+\kappa\boldsymbol{w}_{t}\big]\sigma^{\prime}(\boldsymbol{\beta}_{t})}\\ \\ \end{array}&\,0&\hskip-7.0pt\begin{array}[]{c}\\ {I-\kappa\left[\boldsymbol{\alpha}_{t}\right]}\\ \\ \end{array}&0&0\\ \frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}&0&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}&\frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\end{split} (72) where the second equality is due to ( 71 ) and the last equality follows from ( 70 ). Consider the following block representation of X t X_{t} , X t = [ ℋ t X t m ] . X_{t}=\left[\begin{array}[]{c}\mathcal{H}_{t}\\ \hfill X^{m}_{t}\end{array}\right]. (73) Plugging the first row of G t base G^{\textrm{base}}_{t} , given in ( 72 ), into ( 46 ), implies that ℋ t + 1 = − γ [ Sign ( c 𝒎 t + ( 1 − c ) ∇ f t ) + κ 𝒘 t ] σ ′ ( 𝜷 t ) B t + γ ( I − κ [ 𝜶 t ] ) ℋ t \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} (74) For simplicity of notation, we define the diagonal matrix S t S_{t} as S t = def [ Sign ( c 𝒎 t + ( 1 − c ) ∇ f t ) + κ 𝒘 t ] . 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]. (75) Then, 𝒉 t + 1 = γ ⁡ [ − S t ​ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] + γ ⁡ ( I − κ ⁡ [ 𝜶 t ] ) ​ ℋ t [ 1 ] ⋮ − S t ​ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] + γ ⁡ ( I − κ ⁡ [ 𝜶 t ] ) ​ ℋ t [ m ] . ] \boldsymbol{h}_{t+1}=\gamma\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {-S_{t}\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}\,+\,\gamma\big(I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big)\mathcal{H}_{t}^{[1]}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {-S_{t}\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}\,+\,\gamma\big(I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\big)\mathcal{H}_{t}^{[m]}}\\ \\ \end{array}\hskip-15.0pt\phantom{a}.\end{array}\right] (76) It follows that d ​ 𝒉 t + 1 d ​ 𝒎 t = 0 , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}}=0, (77) and d ​ 𝒉 t + 1 d ​ 𝒘 t = − γ ⁡ [ [ 𝒆 1 ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ⋯ [ 𝒆 n ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ 1 ] ⋮ ⋱ ⋮ [ 𝒆 1 ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ⋯ [ 𝒆 n ] ​ σ ′ ​ ( 𝜷 t ) ​ B t [ m ] ] , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{e}_{1}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}}\\ \\ \end{array}&\cdots&\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{e}_{n}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[1]}}\\ \\ \end{array}\\ \hline\cr\vdots&\hskip-7.0pt\begin{array}[]{c}\\ {\ddots}\\ \\ \end{array}&\vdots\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{e}_{1}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}}\\ \\ \end{array}&\cdots&\hskip-7.0pt\begin{array}[]{c}\\ {\left[\boldsymbol{e}_{n}\right]\,\sigma^{\prime}(\boldsymbol{\beta}_{t})\,B_{t}^{[m]}}\\ \\ \end{array}\end{array}\right], (78) where 𝒆 i \boldsymbol{e}_{i} is the i i th unit vector (i.e., an n n -dimensional vector whose i i th entry is 1 1 and all other entries are zero). Let β t ​ [ i ] \beta_{t}[i] and ℋ t [ i ] \mathcal{H}_{t}^{[i]} be the i i th entry of 𝜷 t \boldsymbol{\beta}_{t} and i i th column of ℋ t \mathcal{H}_{t} , respectively, for i = 1 , … , m i=1,\ldots,m . Then, d ​ 𝒉 t + 1 d ​ 𝜷 t = − γ ⁡ [ γ ​ κ ​ [ d ​ 𝜶 t d ​ β t ​ [ 1 ] ] ​ ℋ t [ 1 ] + S t ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ 1 ] ​ B t [ 1 ] ⋯ γ ​ κ ​ [ d ​ 𝜶 t d ​ β t ​ [ m ] ] ​ ℋ t [ 1 ] + S t ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ m ] ​ B t [ 1 ] ⋮ ⋱ ⋮ γ ​ κ ​ [ d ​ 𝜶 t d ​ β t ​ [ 1 ] ] ​ ℋ t [ m ] + S t ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ 1 ] ​ B t [ m ] ⋯ γ ​ κ ​ [ d ​ 𝜶 t d ​ β t ​ [ m ] ] ​ ℋ t [ m ] + S t ​ ∂ σ ′ ​ ( 𝜷 t ) ∂ β t ​ [ m ] ​ B t [ m ] ] , \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}=-\gamma\left[\begin{array}[]{c|c|c}\hskip-7.0pt\begin{array}[]{c}\\ {\gamma\kappa\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\quad\cdots\quad}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\gamma\kappa\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\ddots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\vdots}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {\gamma\kappa\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\cdots}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\gamma\kappa\Big[\frac{\mathrm{d}\,\boldsymbol{\alpha}_{t}}{\mathrm{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]}}\\ \\ \end{array}\end{array}\right], (79) and d ​ 𝒉 t + 1 d ​ 𝒉 t = γ ⁡ [ I − κ ⁡ [ 𝜶 t ] 0 0 0 0 I − κ ⁡ [ 𝜶 t ] 0 0 0 0 ⋱ 0 0 0 0 I − κ ⁡ [ 𝜶 t ] ] ​ ← 1 ​ st ← 2 ​ nd ⋮ ← m ​ th , . \frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}=\gamma\,\left[\begin{array}[]{c|c|c|c}\begin{array}[]{c}I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\ \\ \end{array}&0&0&0\\ \hline\cr 0&\begin{array}[]{c}\\ I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\\ \\ \end{array}&0&0\\ \hline\cr 0&0&\begin{array}[]{c}\\ \ddots\\ \\ \end{array}&0\\ \hline\cr 0&0&0&\begin{array}[]{c}\\ I-\kappa\left[\boldsymbol{\alpha}_{t}\right]\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{0.75,0.75,0.75}\leftarrow 1\textrm{st}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow 2\textrm{nd}}\\ \\ \end{array}\\ \begin{array}[]{c}\\ \,\,{\color[rgb]{0.75,0.75,0.75}\vdots}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow m\textrm{th}}\end{array},\end{array}. (80)

It follows from ( 21 ), ( 72 ), and ( 77 ) that in the G t G_{t} matrix, d ​ 𝒎 t + 1 d ​ 𝒎 t \frac{\mathrm{d}\,\boldsymbol{m}_{t+1}}{\mathrm{d}\,\boldsymbol{m}_{t}} is the only non-zero block in its corresponding column of blocks. Consequently, it follows from ( 14 ) that X t m X^{m}_{t} , as defined in ( 73 ), has no impact on the update of ℋ t + 1 \mathcal{H}_{t+1} , Y t + 1 Y_{t+1} , and Q t + 1 Q_{t+1} . Therefore, the rows and columns of G base G^{\textrm{base}} that correspond to derivative of 𝒎 \boldsymbol{m} can be completely removed from G base G^{\textrm{base}} . By removing these rows and columns from G t G^{t} , the matrix update ( 14 ) simplifies to [ Y t + 1 ℋ t + 1 Q t + 1 ] = γ ​ [ d ​ 𝒚 t + 1 d ​ 𝒚 t [ − [ Sign ( c 𝒎 t + ( 1 − c ) ∇ f t ) ] σ ′ ( 𝜷 t ) 0 d ​ 𝒉 t + 1 d ​ 𝜷 t 0 ] d ​ 𝒚 t + 1 d ​ 𝒘 t d ​ 𝒚 t + 1 d ​ 𝒉 t I − κ ⁡ [ 𝜶 t ] 0 d ​ 𝒉 t + 1 d ​ 𝒘 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] ​ ( [ Y t ℋ t Q t ] + ( 1 − γ ) ​ [ [ I 0 ] 0 0 ] ) , \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}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\left[\begin{array}[]{cc}\hskip-7.0pt\begin{array}[]{c}\\ {-\big[\operatorname{Sign}\big(c\,\boldsymbol{m}_{t}+(1-c)\nabla f_{t}\big)\big]\sigma^{\prime}(\boldsymbol{\beta}_{t})}\\ \\ \end{array}&\,\,\,\,\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\,\,\,\,\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}\end{array}\right]}\\ \\ \end{array}\end{array}&\begin{array}[]{cc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {I-\kappa\left[\boldsymbol{\alpha}_{t}\right]}\\ \\ \end{array}&0\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \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}\hskip-10.0pt\begin{array}[]{c}\\ {\left[\begin{array}[]{c}I\\ 0\end{array}\right]}\\ \\ \end{array}\\ 0\\ 0\end{array}\right]\right), (81) where d ​ 𝒉 t + 1 / d ​ 𝜷 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{\beta}_{t}} , d ​ 𝒉 t + 1 / d ​ 𝒘 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{w}_{t}} , and d ​ 𝒉 t + 1 / d ​ 𝒉 t {\mathrm{d}\,\boldsymbol{h}_{t+1}}/{\mathrm{d}\,\boldsymbol{h}_{t}} are given in ( 79 ), ( 78 ), and ( 80 ), 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 ​ ( 𝒘 t ) = 1 2 ​ ( 𝒂 t T ​ 𝒘 t − b t ) 2 , f_{t}(\boldsymbol{w}_{t})=\frac{1}{2}\big(\boldsymbol{a}_{t}^{T}\boldsymbol{w}_{t}-b_{t}\big)^{2}, (82) for a given sequence of feature vectors 𝒂 t \boldsymbol{a}_{t} and target values b t b_{t} , for t = 1 , 2 , … t=1,2,\ldots . Moreover, Sutton (1992) assumes weight-wise step sizes, in which case 𝜷 t \boldsymbol{\beta}_{t} has the same dimension as 𝒘 t \boldsymbol{w}_{t} . The update rule of IDBD is as follows: 𝒈 t \displaystyle\boldsymbol{g}_{t} ← ( 𝒂 t T ​ 𝒘 t − b t ) ​ 𝒂 t , \displaystyle\leftarrow(\boldsymbol{a}_{t}^{T}\boldsymbol{w}_{t}-b_{t})\,\boldsymbol{a}_{t}, (83) 𝜷 t + 1 \displaystyle\boldsymbol{\beta}_{t+1} ← 𝜷 t − η ​ 𝒉 t ​ 𝒈 t , \displaystyle\leftarrow\boldsymbol{\beta}_{t}-\eta\,\boldsymbol{h}_{t}\,\boldsymbol{g}_{t}, (84) 𝜶 t + 1 \displaystyle\boldsymbol{\alpha}_{t+1} ← exp ⁡ ( 𝜷 t + 1 ) , \displaystyle\leftarrow\exp\big(\boldsymbol{\beta}_{t+1}\big), (85) 𝒘 t + 1 \displaystyle\boldsymbol{w}_{t+1} ← 𝒘 t − 𝜶 t + 1 ​ 𝒈 t , \displaystyle\leftarrow\boldsymbol{w}_{t}-\boldsymbol{\alpha}_{t+1}\,\boldsymbol{g}_{t}, (86) 𝒉 t + 1 \displaystyle\boldsymbol{h}_{t+1} ← ( 1 − 𝜶 t + 1 ​ 𝒂 t 2 ) + ​ 𝒉 t − 𝜶 t + 1 ​ 𝒈 t , \displaystyle\leftarrow\left(1-\boldsymbol{\alpha}_{t+1}\boldsymbol{a}_{t}^{2}\right)^{+}\boldsymbol{h}_{t}-\boldsymbol{\alpha}_{t+1}\boldsymbol{g}_{t}, (87) where ( ⋅ ) + (\cdot)^{+} clips the entries at zero to make them non-negative, aimed to improve stability. Here, 𝒈 t \boldsymbol{g}_{t} is the gradient of f t ​ ( 𝒘 t ) f_{t}(\boldsymbol{w}_{t}) and 𝒂 t 2 \boldsymbol{a}_{t}^{2} in the last line is a vector that contains diagonal entries of the Hessian of f t f_{t} . The updated values of 𝜷 \boldsymbol{\beta} and 𝒘 \boldsymbol{w} would remain unchanged, if instead of the vector 𝒉 t \boldsymbol{h}_{t} , we use a diagonal matrix ℋ t \mathcal{H}_{t} and replace ( 84 ) and ( 87 ) by 𝜷 t + 1 ← 𝜷 t − η ​ ℋ t ​ 𝒈 t , ℋ t + 1 ← ( 1 − [ 𝜶 t + 1 ​ 𝒂 2 ] ) + ​ ℋ t − [ 𝜶 t + 1 ​ 𝒈 t ] . \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} (88) Note that [ 𝒂 2 ] \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 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 ℋ t \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 m=n . The update of step sizes in this method is as follows: 𝜷 t + 1 ← 𝜷 t − η ℋ t 𝖳 ∇ f t ( 𝒘 t ) 𝜶 t + 1 ← exp ⁡ ( 𝜷 t + 1 ) , 𝒘 t + 1 ← 𝒘 t − 𝜶 t + 1 ∇ f t ( 𝒘 t ) , ℋ t + 1 ← ( I − [ 𝜶 t + 1 ] ∇ 2 f t ( 𝒘 t ) ) ℋ t − [ 𝜶 t + 1 ∇ f t ( 𝒘 t ) ] . \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 𝜶 t + 1 \boldsymbol{\alpha}_{t+1} in 𝒘 t + 1 \boldsymbol{w}_{t+1} and ℋ t + 1 \mathcal{H}_{t+1} updates whereas MetaOptimize uses 𝜶 t \boldsymbol{\alpha}_{t} . This however has no considerable impact since 𝜶 t \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 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: 𝜶 t = β t ​ 1 n × 1 , β t + 1 = β t − η d ​ f t ​ ( 𝒘 t ) d ​ β t − 1 = β t − η ∇ f t ( 𝒘 t ) T d ​ 𝒘 t d ​ β t − 1 . \begin{split}\boldsymbol{\alpha}_{t}&=\beta_{t}\,\boldsymbol{1}_{n\times 1},\\ \beta_{t+1}&=\beta_{t}-\eta\,\frac{\mathrm{d}\,f_{t}(\boldsymbol{w}_{t})}{\mathrm{d}\,\beta_{t-1}}=\beta_{t}-\eta\,\nabla f_{t}(\boldsymbol{w}_{t})^{T}\,\frac{\mathrm{d}\,\boldsymbol{w}_{t}}{\mathrm{d}\,\beta_{t-1}}.\end{split} (89) The last update can be equivalently written as β t + 1 = β t − η ℋ t T ∇ f t ( 𝒘 t ) , ℋ t + 1 = 0 × ℋ t + d ​ 𝒘 t + 1 d ​ β t . \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{\mathrm{d}\,\boldsymbol{w}_{t+1}}{\mathrm{d}\,\beta_{t}}.\end{split} (90) The step-size update in ( 90 ) 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 G_{t} matrix in ( 9 ) 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 ( 90 ) is also equivalent to a MetaOptimize algorithm that uses SGD as its meta update and sets γ = 0 \gamma=0 . Note that setting γ \gamma equal to zero would eliminate the dependence of ℋ t + 1 \mathcal{H}_{t+1} on X t X_{t} and Q t Q_{t} , as can be verified from ( 14 ). This would also render the β \beta updates ignorant about the long-term impact of step size on future losses.

## Appendix C Experiment Details

In the appendix, we describe the details of experiments performed throughout the paper. In our experiments on CIFAR10, non-stationary CIFAR100, and ImageNet dataset, we used a machine with four Intel Xeon Gold 5120 Skylake @ 2.2GHz CPUs and a single NVIDIA V100 Volta (16GB HBM2 memory) GPU. For TinyStories dataset, we used a machine with four AMD Milan 7413 @ 2.65 GHz 128M cache L3 CPUs and a single NVIDIA A100SXM4 (40 GB memory) GPU. In all experiments, the meta step size η \eta is set to 10 − 3 10^{-3} . The meta-parameters used in the considered optimization algorithm for CIFAR10, non-stationary CIFAR100, ImageNet, and TinyStories are given in Table 2 , Table 4 , and Table 5 , respectively. In the experiments, we performed a grid search for ρ , ρ ¯ ∈ { 0.9 , 0.99 , 0.999 } \rho,\bar{\rho}\in\{0.9,0.99,0.999\} , λ , λ ¯ ∈ { 0.99 , 0.999 } \lambda,\bar{\lambda}\in\{0.99,0.999\} , and c , c ¯ ∈ { 0.9 , 0.99 } 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 } \{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 ) (respectively ( Karpathy, 2024 ) )) and did a grid search for the maximum learning rate in the set { 10 − 5 , 10 − 4 , 10 − 3 } \{10^{-5},10^{-4},10^{-3}\} .

Regarding other baseline algorithms, for DoG, although it is a parameter-free algorithm, its performance is still sensitive to the initial step movement. We did a grid search for the initial step movement in the set { 10 − 9 , 10 − 8 , 10 − 7 , 10 − 6 } \{10^{-9},10^{-8},10^{-7},10^{-6}\} and reported the performance for the best value. In all experiments of DoG, we considered the polynomial decay averaging. For Prodigy, we used the default values of parameters as suggested by the authors in github repository. For gdtuo, we considered the following (base, meta) combinations: (RMSprop, Adam), (Adam, Adam), and (SGD with momentum, Adam) and chose the best combination. For mechanic, we did experiments for the base updates of SGDm, Lion, and Adam and considered the best update. In order to have a fair comparison, in mechanic and gdtuo, we used the same initial step size as MetaOptimize.

Regarding the complexity overheads reported in Table 1 , for AdamW with fixed step-size we used the Pytroch implementation of AdamW. For all other baselines, we used the implementation from the Github repository provided along with (and cited in) the corresponding paper. For MetaOptimize, we used the implementation in ( Salehkaleybar, 2025 ) . Note that the implementation of MetaOptimize in ( Salehkaleybar, 2025 ) is not optimized for time or space efficiency, and smaller complexity overheads might be achieved with more efficient codes. For each algorithm, the wall-clock time overhead and GPU space overhead are computed by ( T Alg − T AdamW ) / T AdamW (T_{\mathrm{Alg}}-T_{\mathrm{AdamW}})/T_{\mathrm{AdamW}} and ( B AdamW max / B Alg max ) − 1 \big(B^{\max}_{\mathrm{AdamW}}/B^{\max}_{\mathrm{Alg}}\big)-1 , respectively; where T Alg T_{\mathrm{Alg}} and T AdamW T_{\mathrm{AdamW}} are per-iteration runtimes of the algorithm and AdamW, and B Alg max B^{\max}_{\mathrm{Alg}} and B AdamW max B^{\max}_{\mathrm{AdamW}} are the maximum batch-sizes that did not cause GPU-memory outage for the algorithm and AdamW.

## Appendix D Further Experimental Results

Continual CIFAR100 experiment: In Figure 4 , we plotted the average top-1 accuracy—averaged over all past training times. This metric is used in continual learning mainly because it summarizes algorithmic performance across multiple tasks, avoiding difficult/misleading interpretations from task-specific accuracy variations. Here, we also include the accuracy curves to reveal such variations. Figure 7 depicts test accuracy at the end of each task.

Moreover, Fig. 8 presents block-wise step sizes similar to those in Fig. 4 , but displayed in separate subfigures for each block to enhance the visibility of step-size ranges. Note that step size of both blocks start at 10 − 4 10^{-4} .

.

ImageNet dataset: In Figure 9 , we depict the train accuracy (top 1) and test accuracy (top 1) of the considered algorithms in ImageNet dataset. As can be seen, in the train accuracy (top 1), MetaOptimize (SGDm, Lion) and MetaOptimize (AdamW, Lion) have the best performance. Moreover, in the test accuracy (top1), these two combinations of MetaOptimze outperform other hyperparameter optimization methods and only AdamW with a handcrafted learning rate scheduler has a slightly better performance at the end of the training process.

(a) Train Accuracy (Top 1)

(b) Test Accuracy (Top 1)

Figure 10 shows the results for the blockwise version of MetaOptimize for two combinations of (AdamW, Lion) and (Lion, Lion). As can be seen, they showed no improvement over the scalar version.

TinyStories experiment: In Figure 11 , we provide the test loss of considered algorithms for the TinyStories datasets. As can be seen, the learning curves have the same trends as the training loss in Figure 6 .

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .