We investigate the use of ellipsoidal trust region constraints for second-order optimization of neural networks. This approach can be seen as a higher-order counterpart of adaptive gradient methods, which we here show to be interpretable as first-order trust region methods with ellipsoidal constraints. In particular, we show that the preconditioning matrix used in RMSProp and Adam satisfies the necessary conditions for provable convergence of second-order trust region methods with standard worst-case complexities. Furthermore, we run experiments across different neural architectures and datasets to find that the ellipsoidal constraints constantly outperform their spherical counterpart both in terms of number of backpropagations and asymptotic loss value. Finally, we find comparable performance to state-ofthe-art first-order methods in terms of backpropagations, but further advances in hardware are needed to render Newton methods competitive in terms of time.
In this paper, the authors investigate the use of ellipsoidal trust region constraints for second order optimization. The authors first show that adaptive gradient methods can be viewed as first-order trust region methods with ellipsoid constraints. The authors then show that the preconditioning matrix of RMSProp and Adam can be used as norm inducing matrices for second order trust region methods. This ellipsoidal trust region method is empirically compared with first order gradient methods and spherical second order trust region methods.
Overall the paper is nicely written and very easy to read. The ideas are interesting. However, I have a number of concerns/questions about the work, that I list below.
1. Why is the preconditioning matrix of RMSProp/Adam a reasonable norm inducing matrix? One can show that the empirical Fisher is not an accurate curvature matrix in general, and so there is no reason to believe this would in fact enforce the proper ellipsoidal trust region for the method? See for example: https://arxiv.org/pdf/1905.12558.pdf.
2. I am also not convinced that Figure 2 actually shows that the curvature matrix is diagonally dominant. How do I interpret a value of 40 or 50 for this metric, and why does it imply that it is diagonally dominant?
3. The experiments also do not look very convincing to me. How sensitive is the algorithm to the hyperparameters like lambda1 and lambda2? I am also a bit confused about why different batch sizes were used for the first order gradient methods and the second order TR methods? The method overall doesn't seem to be able to match first order gradient methods, and it is not clear whether this is because of using the RMSProp/Adam preconditioner as a curvature matrix.
Given these concerns, I consider this paper to be borderline. I am happy to have a discussion with the authors and the other reviewers and change my score however.
=========================================
Edit after rebuttal:
I thank the reviewers for their response. While the updated paper has certainly improved, I think the paper still requires a much more thorough experimental evaluation. I am sticking to my score.