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

Besides, it will be better to utilize existing theoretical analysis for bilevel programming (e.g. [1] and references therein) to derive specific theoretical results (e.g. the stability or generalization guarantees) for the proposed MetaOptimize framework in Algorithm 1.

Regarding the referenced paper [1], their analysis relies on unrolled differentiation (that unrolls the algorithm for several steps into future and approximates the derivative of future loss with respect to the current meta-paramaters), whereas MetaOptimize employs a causal algorithm where meta-updates depend only on past information. This fundamental difference makes it challenging to directly leverage their theoretical results for our framework.

We acknowledge that theoretical guarantees are important and provide valuable insights. However, incorporating a comprehensive theoretical analysis is beyond the scope of our current work for two reasons: 1- The field of meta-parameter optimization is still evolving, and both the community and we, as authors, are exploring its full potential. It may be premature to seek comprehensive theoretical performance guarantees at this stage. 2- Such analysis typically relies on strong assumptions, like convexity or smoothness, which do not align with our focus on developing scalable algorithm effective for large-scale networks.

We plan to explore analytical tools from bilevel optimization literature, including those in [1] and its references, in future work to develop theoretical results specific to MetaOptimize, such as stability and regret bounds.

Minor: (3) There exists too many blank spaces in the paper. For example, between Eq.(10) and Eq.(11), I would suggest use $\left( \frac{d y_{t+1}}{d \beta_{\tau}}, \frac{d x_{t+1}}{d \beta_{\tau}}, \frac{d h_{t+1}}{d \beta_{\tau}} \right)^T = G_t \left( \frac{d y_t}{d \beta_{\tau}}, \frac{d x_t}{d \beta_{\tau}}, \frac{d h_t}{d \beta_{\tau}} \right)^T$ to save space, and give more theoretical explanations. Similar problem also exists in Eqs.(12)-(16).

We have applied your suggested change in the revised version. This adjustment has resolved the blank spaces and improved the overall appearance of the paper.

(4-11) Typos:

We thank the reviewer for their meticulous reading. We corrected all the typos.

(1) Can you give more theoretical explanations for why gradient descent in Eq.(5) can minimize the future loss defined in Eq.(1) ? Or can you give more theoretical analysis for the benefits of introduction of eligibility traces into hyperparameter optimization?

We acknowledge that Equation (5) would benefit from additional intuition and theoretical support. Below, we provide further explanations and discuss potential alternatives.

Intuition Behind the Backward View Update (Equation 5): The backward view update in Equation (5) serves as an approximation of the forward view update in Equation (4). Due to causality constraints, a backward view update is necessary because it allows us to reorder terms in time and apply them as soon as they become available. Although the terms in the two sums are the same, they differ in timing, enabling real-time updates.

Theoretical Backing in a Simple Regime: The approximation becomes exact for sufficiently small meta-step sizes (i.e., when $\eta \to 0$). Specifically, consider some $T \geq 1$ and suppose that $f_t(\cdot) = 0$ for all $t < 0$ and all $t > T$. Then, as $\eta \to 0$, it can be shown that: $\frac{\beta^{(5)}_T-\beta_0}{\eta}\to \frac{\beta^{(4)}_T-\beta_0}{\eta}$, where $\beta^{(4)}_T$ and $\beta^{(5)}_T$ are the values of $\beta$ at time $T$ obtained from updates (4) and (5), respectively, starting from the same initial value $\beta_0$ at time $0$. Intuitively, this is because as $\eta\to0$, $\beta$ remains alomst constant over the intercal $[0,T]$, and the right hand side of (4) would be equal to the right hand side of (5) when summed over $[0,T]$, with accuracy $O(\eta^2)$. For larger values of $\eta$, the approximation may not be as accurate. This is on par with a similar result for eligibility traces in RL.

Alternative, More Accurate Solutions: We recognize that developing a more accurate trace, similar to the Dutch traces in RL (defined in Chapter 11 of Sutton and Barto 2018), could improve performance. Dutch traces however work only for the linear case and creating a more accurate trace for our context is a mathematically challenging problem that we have been working on since the submission. On the other hand, the simple eligibility trace is effective and widely used in RL algorithms like TD($\lambda$). On this grounds, we believe that the current simple trace serves as a good baseline, and we plan to explore more complex solutions in future work.

Modifications Applied to the Paper: To address your comment, we have made the following revisions to the manuscript (updated pdf):

1. Indcluded the discussion of the approximation quality in the paragraph following Equation (5).
2. Added a discussion of possible alternative, more accurate solutions in the future works, in Section 9.
3. Enhanced the intuition behind the backward view update in the paragraph following Equation (5).

(2) The introduction of the Jacobian matrix $\mathcal{H}_t$ in line 222 is novel, but the bilevel-optimization (i.e. base-meta algorithm optimization) framework in Algorithm 1 is not new for me.

While the base-meta optimization framework has roots in earlier works like IDBD (Sutton, 1982) and several base-meta optimization algorithms exist, we believe there is substantial room for improvement, especially when using blockwise step sizes. Algorithm 1 introduces significant differences from previous methods in the way we update the Jacobian matrix $\mathcal{H}_t$ based on Equations (10) and (15). It accounts for the dynamics of the meta-parameters $\beta$—specifically, how changes in the current $\beta$ affect future values of $\beta$. Please refer to Remark 4.1 of the paper for detailed discussion.

In addition, Equation 1 only contains the training information, the motivation for optimising the learning rate against this objective function is not clear and a follow-up question can be what benefits are achieved by optimising this.

Yes, optimizing the learning rate against this objective is beneficial, especially in the continual learning setting, which is more challenging and realistic than classical supervised learning, and which is emerging as a a standard paradigm for big-world learning. In continual learning, there are no fixed training or test sets; instead, data arrives as a potentially non-stationary stream. Minimizing the online loss (or regret) allows the model to adapt dynamically to new information.

Interestingly, although MetaOptimize is designed for continual learning, we have demonstrated that it also outperforms existing baselines on classical supervised learning tasks. We agree that additional performance gains would be possible in supervised learning, by integrating validation data into the algorithm (e.g., into regularizers, or by using validaion-gradients in $\beta$ updates, etc.). However, this is beyond the scope of current paper, and we do no want to limit the proposed algorithms to classical supervised learning.

5. I believe approximate Hessian with either diagonal matrix or block diagonal matrix is common in the precondition optimisation field, L-approximation is another special ly format which is parallel with the others. Stating it as containing existing algorithms as special cases may be overclaiming.

The L-approximation in our work is not merely a matrix approximation; it has a specific interpretation. By removing the upper-right block of the matrix G in the L-approximation, we effectively ignore the dynamics of the meta-parameter β. Therefore, algorithms that reduce to the L-approximation are indeed special cases of meta-parameter optimization methods that neglect the dynamics of β, as discussed in Section 5.

Regarding Hessian approximation techniques like diagonal and block-diagonal approximations, while they are common in precondition optimisation, none of these methods provide the exact diagonal of the Hessian. Furthermore, incorporating Hessian would introduce several complexities beyond approximation quality and computational efficiency, even if we assume oracle access to the sample Hessian or its diagonal, as outlined in the Limitations section. More specifically, Hessian impacts the trace $H_{t+1}$ multiplicatively, making the updates sensitive to sample noise, which necessitated approproate 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, necessitating appropriate landscape-smoothing techiques. Exploring the impact of different Hessian approximations on MetaOptimize is beyond the scope of this work and warrants further exploration in future.

Also, it could be interesting to know that with diagonal matrix approximation, the Meta-optimize works and it will definitely reduce computational cost.

While incorporating a diagonal matrix approximation could potentially reduce computational cost, our current version of MetaOptimize is Hessian-free and already exhibits very small computational overhead in both time and space, as reported in Table 1. We acknowledge that a low-complexity implementation of the Hessian might lead to performance improvements. However, implementing the Hessian—even in approximate form—introduces certain challenges beyond computational complexity, which we discussed in the Limitations section.

6. Suggestions: The reference format is a little mass, which does not affect my score for this paper. For example, DoG is published in ICML 2023 while in the reference it is the arXiv version.

Thank you for bringing this to our attention. We have updated the reference formats in the revised manuscript, ensuring that all citations reflect their official conference or journal publications. For example, the DoG reference now cites its ICML 2023 version instead of the arXiv preprint. Please refer to the revised PDF for the updated references.

Questions: In terms of time-space complexity comparison, MetaOptimize does not show a significant advantage on ImageNet but on TinyStoires. Can the authorise explain why?

The exact reason is not entirely clear, but it might be due to our sub-optimal implementation of MetaOptimize for the ImageNet experiments. We did not optimize our code for performance in this case, whereas for the baselines, we used the code provided by the original authors. As mentioned in the last paragraph of Appendix C, this could have affected the computational efficiency results.

We thank the reviewer for their feedback. We believe our revision has improved the paper and clarity of its presentation, as detailed below.

2. The experiment results do not cover the generalization performance of the trained models by different optimizations. For example, there is no direct comparison of the accuracy of the test set. The top 5 accuracy applied in the paper can reflect the performance of the optimizers but usually top 1 accuracy is more important.

Modifications Applied to the Paper: In the revised manuscript (updated pdf), we report generalization performance, including test accuracy (for ImageNet) and test loss (for Language Modeling), in Appendix D, specifically focusing on top-1 accuracy. The test accuracies exhibit similar trends to the training accuracy curves and maintain the same relative performance among different algorithms. In all experiments, MetaOptimize outperforms all baselines in both training and test accuracies. In addition to test accuracies, we continue to report training accuracies in the revised paper.

Relevance of Train vs. Test Accuracies for Continual Learning: Although our experiments involve stationary supervised learning benchmarks, we develop MetaOptimize within the increasingly popular continual learning framework, which is more challenging and more general compared to the classical supervised learning framework. In this continual setting, we handle a stream of potentially non-stationary loss functions rather than fixed train-test splits, and as a result the appropriate performance measure is the online loss (or regret) rather than test set performance. Furthermore, techniques for improving generalization under meta-parameter optimization—such as specific regularizations—may differ from conventional methods known to work well with fixed step sizes. This area warrants further research.

3 & 4. As learning rate learning is usually a special case of optimiser learning, some previous works are missing for comparison [1,2,3]. The proposed backward-view update is similar to the forward mode differentiation (FMD) in [1] and the follow-up study on learning rate learning paper [2].

Thank you for bringing these references to our attention. We have included them in the related works section of the revised manuscript and discussed their connections to MetaOptimize.

Regarding [1]: The setting in Khodak et al. (2019) differs significantly from ours. They consider a sequence of tasks, each of length m, whereas in our continual learning framework, we assume m = 1 with no prior knowledge about task changes. Their analysis relies on the assumption that all loss functions are convex. Under this strong assumption, even vanilla SGD with fixed step sizes achieves average regret bounds of order $1/\sqrt{m}$. They proposed meta-algorithms that attain regret bounds of the same order but with improved constants. In our context, assuming convex loss functions with m = 1 would result in constant average regret, possibly with small constant-improvements.

Regarding [2]: The algorithm in (Micaelli and Storkey 2021) is equivalent to the L-approximation, and is essentially similar to IDBD (Sutton 1992) and its extensions (Xu et al. 2018). Like IDBD, their approach ignores the impact of the dynamics of meta-parameters and considers only the dynamics of the base algorithms. We highlighted this difference in Remark 4.1 of our submitted manuscript. Additionally, we explicitly discuss the forward objective and its connection to the backward approximation, rather than treating them as two independent techniques.

Regarding [3]: Gao et al. (2022) addressed a different setting involving multitask learning. Specifically, they update meta-parameters after a complete training on one of the tasks. This approach does not align with our experiments, which involve concurrent learning of step sizes and network weights. Moreover, as their approach converges to a fixed stepsize, the resulting baseline would perform no better than the best-fixed-stepsize baseline that is already outperformed by MetaOptimize in our experiments.

Our Choice of Baselines: We have carefully selected state-of-the-art methods for comparison in our experiments. Including additional baselines would overcrowd the figures and make them difficult to interpret. However, we acknowledge the relevance of these works and have discussed their connections to MetaOptimize in the revised paper.

While the explanations provided are clear and easy to understand, some aspects are not thoroughly covered, e.g. Equation (5) would benefit from additional intuition or theoretical support.

We acknowledge that Equation (5) would benefit from additional intuition and theoretical support. Below, we provide further explanations and discuss potential alternatives.

Intuition Behind the Backward View Update (Equation 5): The backward view update in Equation (5) serves as an approximation of the forward view update in Equation (4). Due to causality constraints, a backward view update is necessary because it allows us to reorder terms in time and apply them as soon as they become available. Although the terms in the two sums are the same, they differ in timing, enabling real-time updates.

Approximation Quality: The approximation becomes exact for sufficiently small meta-step sizes (i.e., when $\eta \to 0$). Specifically, consider some $T \geq 1$ and suppose that $f_t(\cdot) = 0$ for all $t < 0$ and all $t > T$. Then, as $\eta \to 0$, it can be shown that: $\frac{\beta^{(5)}_T-\beta_0}{\eta}\to \frac{\beta^{(4)}_T-\beta_0}{\eta}$, where $\beta^{(4)}_T$ and $\beta^{(5)}_T$ are the values of $\beta$ at time $T$ obtained from updates (4) and (5), respectively, starting from the same initial value $\beta_0$ at time $0$. Intuitively, this is because as $\eta\to0$, $\beta$ remains alomst constant over the intercal $[0,T]$, and the right hand side of (4) would be equal to the right hand side of (5) when summed over $[0,T]$, with accuracy $O(\eta^2)$. For larger values of $\eta$, the approximation may not be as accurate. This is on par with a similar result for eligibility traces in RL.

Alternative, More Accurate Solutions: We recognize that developing a more accurate trace, similar to the Dutch traces in RL (defined in Chapter 11 of Sutton and Barto 2018), could improve performance. Dutch traces however work only for the linear case and creating a more accurate trace for our context is a mathematically challenging problem that we have been working on since the submission. On the other hand, the simple eligibility trace is effective and widely used in RL algorithms like TD($\lambda$). On this grounds, we believe that the current simple trace serves as a good baseline, and we plan to explore more complex solutions in future work.

Modifications Applied to the Paper: To address your comment, we have made the following revisions to the manuscript (updated pdf):

1. Indcluded the discussion of the approximation quality in the paragraph following Equation (5).
2. Added a discussion of possible alternative, more accurate solutions in the future works, in Section 9.
3. Enhanced the intuition behind the backward view update in the paragraph following Equation (5).

There are established lines of work on gradient-based hyperparameter optimization using bilevel optimization. Discussing the connection between the proposed method and these existing approaches would strengthen the paper.

Bilevel optimization and its distinctions from MetaOptimize: Bilevel optimization in supervised learning aims to tune hyperparameters to minimize validation loss, typically involving an outer loop that updates hyperparameters after a complete training run of the base algorithm. In contrast, our proposed MetaOptimize framework is designed for continual learning scenarios where meta-parameters are optimized on-the-fly concurrently with training in a single streaming run. Unlike bilevel optimization methods that rely on a validation set—which is absent in continual learning—MetaOptimize focuses on minimizing the online loss (or regret) over a stream of data without separate validation or test sets. This makes MetaOptimize more appropriate for the increasingly popular setting of continual learning. We however left experiments on continual learning benchmarks for future works partly because benchmarking for continual learning is an evolving area, and there is still no standard large-scale benchmark available. Another advantage of online optimization of meta-parameters (as in MetaOptimize) compared to bilevel optimization, is the automatical learning of time-varying stepsizes and good stepsize schedules, which has a potential advantage over the fixed stepsizes learned through bilevel optimization, as demonstraited in the experiments (i.e., MetaOptimize outperforms best fixed stepsize).

Modifications Applied to the Paper: In the revised manuscript, we have added a paragraph in the Related Works section to discuss bilevel optimization algorithms and clarify their connections and distinctions with MetaOptimize. This includes several works form the bilevel optimization literature, including the pioneering work of (Bengio 2000), and its extensions in (Maclaurin et al. 2015), (Pedregosa 2016), (Franceschi et al. 2018), and (Lorraine et al. 2020). Please refer to the updated PDF for details.

We sincerely appreciate the time and effort you have devoted to reviewing our work and for sharing your valuable insights. We have carefully addressed the concerns and suggestions you raised and have provided detailed responses to each point.

As the open discussion phase is nearing its conclusion, we would greatly appreciate any final feedback or thoughts you might have on our revisions and in light of our responses.

Thank you again for your time and contributions to this process.