Optimistic Meta-Gradients

Summary

This paper studies a connection between optimization and meta-learning. For the case of a single task, it shows an equivalence between GD with momentum and GBML, and another equivalence between GD with Nesterov acceleration and the recent Bootstrapped Meta-Gradient algorithm. Theoretical analyses are done for these algorithm, showing that GBML speeds up convergence by a constant factor but is not able to improve on the $O(1/T)$ rate, while BMG is able to improve the rate to $O(1/T^2)$. Experiments are done on quadratic minimization and ImageNet image classification that confirm the theory.

Strengths

1. The mathematical argument in the paper is very clearly presented, e.g. the authors roughly outline proof techniques. 2. Overall the paper appears to be sound, although I did not check the math. Experiments were done on both "toy" examples and a more realistic ImageNet problem. 3. As far as I know, the connection between BMG and GD with Nesterov acceleration is novel.

Weaknesses

In my opinion, the major weakness of the paper is the fact that it only considers the single task setting. However, one of the major motivations behind meta-learning is that information may be shared between tasks in order to improve convergence speeds for all tasks, and the multi-task setting is arguably more popular in the literature. It would greatly strengthen the work to consider the theory for a multi-task setting, although I understand that it might be more appropriate for future work. Minor: 1. The objective function is convex is a fairly strong assumption.

Questions

Is it fair to search over the range of hyperparameters in the experiments in Section 7.1? Usually when this is done the final results are provided for a held-out test set (a new quadratic function in this case), but this does not seem to be the case here.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors do not have a broader impact section, and I agree since this work discusses optimization methods. However, they do not discuss the limitations/weaknesses of their work, which I think should be added to the final draft.

Summary

This paper shed an interesting perspective on meta-learning by studying the connection between gradient-based meta-learning and convex optimisation in the single task setting. It shows that meta-gradients contain gradient descent with momentum and Nesterov Acceleration as special cases. Furthermore, gradient-based meta-learning can be understood as a non-linear transformation of an underlying optimisation method. The authors establish the rates of convergence for meta-gradients in convex settings. For meta-learning to achieve acceleration of convergence, some form of optimization is needed. Specifically, it provides the first rigorous proof of BMG with acceleration rate of convergence, and highlights the underlying mechanics that enable faster learning with BMG.

Strengths

This paper provides us a novel view on meta-learning by studying the connection between gradient-based meta-learning and convex optimisation. It reveals that gradient descent with momentum and Nesterov Acceleration are special cases of gradient-based meta-learning with different update rules. This paper is of high technical quality. Based on the new understanding for meta-learning as a non-linear transformation of an underlying optimisation method, it establishes theoretical analysis and proof of the convergence rates of meta-gradients in convex settings. The theoretical analysis has insightful implications that we are able to further accelerate the rate of convergence with some form of optimization. As a result, the recently proposed BMG method is proven to achieve an accelerating convergence rate. These results are important and significant, providing us with new deep understanding about gradient-based meta-learning, and theoretical guidance to design fast meta-learning algorithms with update rules. Last, the paper is well organized and clearly written.

Weaknesses

This is a theory paper, it could be more impactful if the authors may add more experiment results for large scale problems either in convex optimization or deep learning settings besides ImageNet.

Questions

Curious to know what is the computational cost of Optimistic meta-learning compared to SGD in the ImageNet experiment.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

1. There is no code provided to reproduce the results. 2. The authors do not describe limitations of their work.

Summary

This work discovers the connection between gradient-based meta-learning and convex optimization of the meta parameters. From there, the authors observe that common gradient descent and its variants with momentum are special cases. To match the conventional $O(1 / T^2)$ convergence rate, the authors propose the optimistic version.

Strengths

1. The observation that common accelerated methods can be viewed as meta-learning is interesting. The online convex optimization view presents a new perspective for showing the convergence of the accelerated methods, which could be itself interesting. 2. The proposed optimistic gradient-based meta-learning method is simple, but shows performance gain over vanilla baseline methods.

Weaknesses

The major weakness of the analysis comes from the restrictive form of the meta-learner. This makes the analysis not applicable to all neural network based learn-to-optimize methods, while the meta-learning methods applied on learning rate or pre-conditioning matrix are well studied already in the literature.

Questions

The figure 1 shows the result of top-1 accuracy of sgd and standard meta learning on resnet50 on imagenet. But to my knowledge SGD can achieve >75% top-1 accuracy on imagenet, can the author elaborate more on what codebase they use and the details of experimental setting for that experiment (e.g., how do you tune learning rate, what is the scheduling etc)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations.

Summary

The submission studies connections between recent advances in convex optimisation and heuristic meta-learning update rules. The provided framework contains standard methods such as heavy ball and Nesterov's momentum as special cases, while also containing rules that correspond to online meta-learning. Bootstrapped meta-gradients are also formalised within this framework. Some of the theoretical results are corroborated by empirical investigations.

Strengths

* The submission is well-written and interesting. I can see myself referring back to this paper in future when developing new meta-learning or bi-level optimisation methods. * Framework provides a useful tool for conceptualising and analysing meta-learning algorithms, as well as comparing them with existing (or novel) convex optimisation approaches. * The analysis shows how one can obtain optimal $O(1/T^2)$ rates of convergence by using optimism. E.g., by predicting that the current gradient will be similar to the previous gradient. * Experiments are provided that empirically corroborate the predictions of the theoretical analysis. In particular, the meta-learning variants of momentum and adagrad converge substantially faster than the conventional approaches.

Weaknesses

* The analysis is limited to the convex case, which is understandable. However, it would be interesting to at least empirically investigate the non-convex case as well.

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

There is no substantial discussion of the limitations of the work.

Response to Authors' Rebuttal

Thanks for your rebuttal and my concerns are addressed. I hope that the implementations will be made publicly available for reproducibility.

Thanks to the authors for the rebuttal

After reading the other reviews and rebuttals, I feel that the authors have adequately addressed my concerns and I have decided to raise my score from 5 to 6.

Thanks to the authors for the rebuttal

I’ve read comments from all the other reviewers. Thank you for your rebuttal, and I appreciate that my concerns have been addressed.