Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: My understanding is that the paper does not claim to deliver some great results here and now but instead suggest a promising direction ("that ellipsoidal constraints prove to be a very effective
modification of the trust region method in the sense that they constantly outperform the spherical TR
method, both in terms of number of backpropagations and asymptotic loss value on a variety of tasks"). 

I should say that I am not confident about my review. I believe that the authors were careful in phrasing their contribution and provided some supporting material but the wall-clock time results on resnets are too bad to envision any practical application ("advances in hardware will be needed"). It would not be a problem if the paper were the first to deal with second-order methods. However, the niche of second-order methods attempting to beat first order methods is not empty and one of the main exit plans consists in showing better wall-clock time convergence, something which is  obviously very hard.

Minor notes:
backprogations -> backpropagations

--- 
Update: I didn't change my score. 
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes ellipsoidal trust region methods for optimization on neural networks. This approach is motivated by the adaptive gradient methods and classical trust region methods. The idea of the design is reasonable, but the theoretical and empirical results are not strong. I can not support acceptance for current version.

Major comments:

1. Section 4.2 says “Algorithm 1 with A_rms ellipsoids converges with the classical rate O(\epsilon^{-2}, \epsilon^{-3}) thanks to Proposition 2 above and Theorem 6.6.8 in Conn et al.  (2000).” I have two questions about this statement.

a) What is (\epsilon^{-2}, \epsilon^{-3})? Some subscript or min/max notation looks missing.

b) I have checked Theorem 6.6.8 in Conn et al. (2000). It only shows the limit point of the sequence of iterates is a second order critical point. How to obtain the convergence rate of Algorithm 1 seems not directly. I hope the authors provide detailed derivation and present Theorem 6.6.8 here (Maybe the version of the book I have seen is not identical to yours).

2. Is there any stop criterion of the sub-problem solver? How the precision of the sub-problem affects the global convergence rate?

3. The experimental section only reports “log-loss”, which is not enough to deep learning applications. It would be interesting to validate weather the proposed method achieves lower test error than baselines.


Minor comments:

1. The values of kappa in the second and the third sub-figures of Figure 1 should be different.

2. The box of Proposition 3 is spited into page 14 and 15.

3. Equation (37) is too long and does not fit within the margins.

===================================

The authors have provided detailed derivation of the key theorem. I decide to raise my rating to 3. 

review_title: Official Blind Review #3

Meta-review: This paper interprets adaptive gradient methods as trust region methods, and then extends the trust regions to axis-aligned ellipsoids determined by the approximate curvature. It's fairly natural to try to extend the algorithms in this way, but the paper doesn't show much evidence that this is actually effective. (The experiments show an improvement only in terms of iterations, which doesn't account for the computational cost or the increased batch size; there doesn't seem to be an improvement in terms of epochs.) I suspect the second-order version might also lose some of the online convex optimization guarantees of the original methods, raising the question of whether the trust-region interpretation really captures the benefits of the original methods. The reviewers recommend rejection (even after discussion) because they are unsatisfied with the experiments; I agree with their assessment.

Decision: Reject