MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters β€” part 10/10

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

( 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 .