MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters — part 2/10

Cleaned-text code points [12223, 28204). Bibliography omitted here; source.md includes it.

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.