Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Authors propose a new perspective on adaptive gradient methods. Main contribution is a trust region based algorithm they call "Stochastic Ellipsoidal Trust Region Method" thats flexible to include both full, and diagonal matrix as the preconditioning matrix.  Authors also mention that the preconditioners are generally diagonally dominant in practice, and may only require diagonal matrix (leaves full matrix for future work).

Reason to score:

Weak emperical results, small models, on small datasets without normalizing for batch sizes between experiments.

I have listed my concerns below and hopefully authors can address my concern during the rebuttal period.

I think the authors could substantially improve the emperical results in the paper by including commonly used adaptive methods as baseline (such as Adam), and providing results on stronger baselines, and break down on computational effeciency of the proposed approach in more details.

Questions/comments:

a) There is Appendix C that states that batch size used first order method is 32, vs for this method authors use 128/512 and then compare backprops. This extremely problematic when using # backprop as a way to measure efficiency, as this gives ~4-16x improvement from just larger batch sizes.  I would suggest redoing experiments with exact same batch sizes?

b) Authors indicate using diagonal preconditioner; Could authors consider previous work on kronecker factored preconditioners such as KFAC, or Shampoo that is computationally cheaper in their experiments?

c) Could authors also include walltime comparisons, to split time spent in forward, backward,  hessian-vector product, cg iterations (including details on these as layer sizes increases, for say upto 4k which are common in deep networks trained today?)

d) Could you run a comparison against baselines and settings in: http://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf 


review_title: A different lens to look at second order methods

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper analyzes adaptive methods like Adam and AMSProp, and shows that they can be re-interpreted as first order trust region methods with an ellipsoidal trust region (Lemma 1).  The authors then propose a second order trust region method with similar ellipsoidal trust regions induced by the RMSProp matrices (Eq 7). Under some assumptions, they show that this algorithm will converge in a finite number of steps (depending upon the accuracy desired). They also show some experiments to demonstrate their algorithm.

The approach proposed in the paper is interesting, but the significance of the paper is not clear. The application of ellipsoidal trust region to Newton algorithms can certainly help with the development of new optimizers, but the presented algorithm was not very clear to me: I assume approximate g_t is the minibatch gradient, but how is the approximate B_t computed. How is m_t(s_t) computed approximately? Could you say a little more about Assumptions 1 and 2 - when do they hold? Finally, the experimental results were not very clear - it seems like ellipsoidal TR methods are often outperformed by first order methods. Also no generalization results on test sets were shown.
review_title: A bridge between adaptive optimization and second order trust region methods

final_score: rating: 4: Ok but not good enough - rejection
review_content: -In section 3.2, the authors use the ratio of the diagonal to the overall mass of a matrix to "measure" the quality of diagonal vs full preconditioning. Why this a good measure? motivation and comments about this measure are needed. I think the most important thing to check here is the "difference" between A^{-1}g and diag(A)^{-1}g. I think an interesting question that one may investigate here is to link this ratio to the  "difference" between A^{-1}g and diag(A)^{-1}g....Or to link this ratio to the complexity...

-In proposition 1, define sigma_1 & 2. I understand that they are defined in the appendix. Just move eq (42) to prop 1. The same about the relation between H & X in proposition 2.

- Rewrite proposition 2, it is a bit misleading, the limit when n goes to infinite should be independent of n ! you may write proportional instead of limit... 

-Figure D.2 shows that sqrt(n)/(sqrt(n)+...) decreases to zero with n going to infinite. However, this quantity is non-decreasing as a function of n and it converges to 1 when n diverges!!

-Page 6 after lemma 2, the authors stated that Thm 1 shows the first convergence rate for ellipsoidal TR methods. I disagree about this. The authors may check for instance 
the work of Conn et al. (this work is cited in the paper) section 6.7  and Bergou et al.: https://link.springer.com/article/10.1007/s10589-017-9929-2  

-  Assumption1: the authors stated that "For finite-sum objectives such as Eq. (1), the above condition can be met by random sub-sampling due to classical concentration results for sums of random variables" this is incorrect! take for instance the case where in the finite sum only one term is not zero and all the other are equal to zero. If the non-zero term is not in the sub-sampling for all t the bounds you mentioned may not be satisfied. You can have these bounds but only in a probabilistic manner as in the Blanchet et al. work (this work is cited in the paper)...

review_title: The paper investigates the use of scaled norms in the constraint of the trust region method.  

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes novel stochastic ellipsoidal trust-region methods  inspired by adaptive gradient methods and studies the application of them with adaptive diagonal preconditioners. Theoretical convergence analysis is provided for TR with RMSProp ellipsoid, and numerical results demonstrates the superiority of ellipsoided TR over uniform TR. Interestingly, the paper shows for the first time that, adaptive gradient methods can be view as first-order TR with ellipsoidal constraints. The negative comparative results with state-of-the-art adaptive methods are appreciated, showing that the TR-type methods may not be great choices for deep network training, since the Hessians are often diagonal-dominant in deep-learning practice, and hence the benefit of second-order methods are limited.

As said, the paper is mostly well-written and present an insightful investigation of stochastic ellipsoidal TR which could be potentially an alternative to state-of-the-art adaptive gradient methods for modern deep network training, and the paper gives a negative answer. On the other hand, the reviewer feels that the potential impact for the deep learning practitioners may be a bit limited and is not very sure about whether the contribution of this work is that significant.

The experimental details seem unclear. In the experiments, how were the approximate hessian B_t calculated? Are they computed on the same sampled minibatch of gradient or on a new/bigger minibatch? Meanwhile, only training accuracies are reported, which seems inadequate -- should also include the test accuracy plots.
review_title: first work studying systematically the practicality of stochatsic ellipsoidal TR method in deep learning

Meta-review: The paper considers adaptive stochastic optimization methods and shows that they can be re-interpreted as first order trust region methods with an ellipsoidal trust region, they consider a related second order method, and they show convergence properties and empirical results.

The results are of interest, but the significance of some of the results is not clear.  Part of this has to do with substance, and part of this has to do with presentation that can be improved.  Empirical results are weak, including appropriate baselines and details of the empirical results.
Decision: Reject