Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents the optimization method Apollo, a quasi-Newton method that relies on a parameter-wise version of the weak secant condition to allow for a diagonal approximation of the Hessian. Additionally, the issue of a potentially non-PSD approximation is addressed by replacing the approximation with a rectified absolute value. While the combination of techniques is interesting, my main hesitation comes from the limited discussion concerning other quasi-Newton methods for the same problem setting.

To begin, a much more significant overview of the distinctions between this work and those of AdaQN and SdLBFGS is certainly warranted, as few details are provided to explain how they differ from the methods in this paper. For example, the comment made about AdaQN is that it "shares a similar idea but specifically designed for RNNs." First, I am unsure why the implication is that this somehow weakens the merit of AdaQN as compared to the Apollo method, especially since the authors themselves evaluate their Apollo method on RNNs for language modeling in Section 4.2. In fact, the authors do not even compare with AdaQN in the RNN experiments, choosing instead only to run against Adam and RAdam. This brings us to a key issue with the paper: why are there no comparisons to any other quasi-Newton methods, for any setting (RNN or otherwise)? Since AdaQN is designed for RNNs, it is perfectly suited as a method to compare with in the language modeling tasks, which exhibit the most notable claimed improvement for Apollo over the adaptive first-order methods.

As for other related methods such as AdaHessian, I agree that there is a distinction between quasi-Newton methods and second-order Hessian-free methods in terms of the information that is accessed. However, just because second-order information is invoked (through Hessian vector products) does not mean by default that the method is "significantly more costly" than these quasi-Newton methods, as is claimed in the paper. Hessian vector product-based methods are desirable precisely because the computational cost is comparable to first-order methods, and here too additional comparison is needed.

Overall, the previous works on quasi-Newton methods for stochastic non-convex optimization have not been sufficiently addressed or compared to, particularly given how those works may also handle the issue of preserving positive-definiteness of B_t.

Small comments:
.- "we demonstrate that Apollo significantly outperforms SGD and variants of Adam"
This is overstated, as the only notable improvement claimed by the paper is for language modeling (the others, particularly for image classification tasks, are modest improvements at best).

.- "Newton's method usually employs the following updates to solve (1)"
It should be clarified that convexity is important when trying to use (plain) Newton's method to solve problems such as (1).

.- "unnecessarily" -> "not necessarily"

.- Related work on Hessian-free methods that consider absolute value-based transformations of the Hessian:

Dauphin, Yann N., Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization." In Advances in Neural Information Processing Systems, pp. 2933-2941. 2014.

.- Related works, in addition to Gupta et al. (2018), in terms of memory-efficient adaptive first-order methods:

Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. "Efficient full-matrix adaptive regularization." In International Conference on Machine Learning, pp. 102-110. 2019.

Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. "Memory Efficient Adaptive Optimization." In Advances in Neural Information Processing Systems, pp. 9749-9758. 2019.

Xinyi Chen, Naman Agarwal, Elad Hazan, Cyril Zhang, and Yi Zhang. "Extreme Tensoring for Low-Memory Preconditioning." In International Conference on Learning Representations. 2020.
review_title: Review for Paper88

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work considers a layer-wise weak secant equation to update the Hessian approximation and  train deep learning models through a stochastic quasi-Newton-like update. The major idea is to construct diagonal approximations so the computational cost is low, and the idea is to some extent similar to adagrad in modifying each coordinate individually with different weights.

The idea itself is interesting, but to fully demonstrate the effectiveness of the proposed algorithm, there should be at least some comparisons with methods of similar flavor.
More specifically, the experiment (section 4) only considered first-order baselines (SGD and Adam-type methods), while later in literature review (section 5), the authors mentioned that there are actually existing stochastic Quasi-Newton methods and adaptive first-order methods that can all be seen as using a sort of diagonal approximation of the Hessian. State of the art in those directions should have been included in the comparison to demonstrate that the proposed work is indeed desirable.
Moreover, Adam/RAdam are shown to be the worst baseline in the first experiment, while in the later 2 experiments those are not excluded, but instead are the only baselines kept for comparison. This is quite suspicious to me and the authors didn't explain why other baselines are discarded at all.

There are also discrepancy  in the text description and the algorithm presentation.
Especially, the update of alpha in Algorithm 1 is different from (8). Although the motivation is understandable, there should be some text explanation of this change in the algorithm.

Note that Section 3.2 totally doesn't make sense, as the normal Newton method also needs a step size to ensure convergence. There are plenty of examples showing that Newton without line search could fail to converge, even for convex problems. Therefore, the motivation is quite weak. Also note that the update of y'_t is wrong, as g'_{t+1} and g'_t use different eta, so y'_t is not a simple scaling of y_t, although in Algorithm 1 it is anyway not calculated in this manner.

Some minor issues:
- Johnson & Zhang 2013 didn't use the kind of moving average of  gradient described in (9), thus this citation is not quite correct.
- The learning rate warmup strategy in the end  of section 3  is not quite satisfactory. The text only mentioned that some heuristic is applied, but didn't describe it there nor in the experiment. Relevant information is only available in the appendix.
- There are many minor typos. The authors should have proofread the manuscript once more before submision. 

=====Post Rebuttal======

I appreciate the authors' responses and the revision of the manuscript. My point about Section 3.2 is not that the correction doesn't make sense, but that the reasoning is not quite convincing from an optimization point of view. I would suggest the authors to simply say what they have replied me instead of trying to link this part to Newton's method.
I wonder why the warm up strategy is only applied to the proposed method but not others if that is effective. Isn't it an unfair comparison?
I also appreciate the new experiments, but decided to retain the score unchanged. My major concern is that if the additional cost of other solvers is the main issue, then probably it would be better for the authors to directly show the training time as well so that the comparison can be straightforward.

review_title: An interesting idea but the numerical support is insufficient.

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary**:

The paper proposes a Quasi-Newton inspired optimization algorithm for Stochastic Optimization named APOLLO. It adjusts a previously known update formula to better suit Deep Learning by using 1) a layer-wise diagonal approximation to the Hessian, 2) an exponential average of gradients to address the noise. Overall the algorithm shows promising results on the assigned experiments.


**Reasons for score**:

I believe the paper has a lot of potential but requires some additional discussion and therefore weakly reject the paper in its current form. My main concern lies in the (mostly lack off) comparison to SGD with momentum followed by the choice of matrix norm used for the update. 


**Pros**:

+ The authors identify the main problems of QN methods in the DL setting and provides a good argument for using a diagonal approximation instead. 

+ The presentation of the theory and algorithm is straightforward and easy to follow with references acknowledging preceding work.

+ I am positively surprised by the efficacy of the presented algorithm given that the diagonal approximation is only chosen to satisfy the weak secant equation. It seems to strike a good trade-off between a light constraint but a restrictive model for the Hessian.


**Concerns**:

- In my opinion, the most important optimizer to compare to is SGD with momentum since there we would see the effect of the proposed preconditioning vs none. It is also the second best in the image classification (sometimes surpassing APOLLO). Can you explain why iti is not present in the other experiments?  

- Eq. 5 and 6 should preferably highlight the usage of matrix norm by changing $|| B - B_t || $->$ || B - B_t ||_W$ (for example) and clarify W=I is used.

- The authors mention that the solution to the constrained optimization in Eq. 5 can result in different popular QN algorithms depending on the matrix norm, which often plays an important role in traditional unconstrained optimization. APOLLO uses the Frobenius norm (W=I) which I would like some further comments on. Did you consider using other norms like $W=B_{t-1}$ or instead estimating the inverse Hessian like BFGS (s <-> y)? 

- How does the momentum influence the performance of APOLLO? Is a high beta required or does it also work for beta=0 so the batch gradient is used? Given that all the gradients in the update are replaced with the momentum term the algorithm becomes reminiscent of an Adagrad update (with gradient replaced by momentum), but with additional "forgetting" (the lack of which has plagued Adagrad in non-sparse settings and lead to the development of several new optimizers). 

- How sensitive is the algorithm to the warmup? This parameter is not mentioned in the language modeling experiment. Could not all of the algorithms benefit from a warmup strategy? 

- The experiments are varied and overall look good but with a relatively small margin in the case of image classification. Given the matter of weight-decay it is difficult to interpret if the improvement over (R)Adam is due to the algorithm or ill-tuned regularization. I think this is handled in a suitable way as outlined in the appendix but it makes the comparison more difficult. 


--------------

**Post rebuttal**

I have considered the revised paper, rebuttal and feedback+rebuttal of fellow reviewers and in the end decided to leave my score unchanged. Below is a summary of my reasoning.

----

The Rebuttal has addressed many concerns and the revised edition has further strengthened the paper in many ways but unfortunately lack in the empirical evaluation. 
It seems like the warmup of Apollo requires a [start, end] learning rate as well as the increase rate compared to the single learning rate of say SGD. It is not clear that the additional overhead of tuning these parameters could not be used to further improve the training schedule of the baseline for better performance (particularly in the CV). At the provided [[link]](https://github.com/bearpaw/pytorch-classification/blob/master/TRAINING.md) for the CV task it looks like the weight decay for CIFAR-10 with the Resnet-110 architecture is set to $10^{-4}$ (not $5\cdot 10^{-4}$) for which $\eta=0.1$ (SGD+M) was good, meaning that the used $\eta$ is not necessarily optimal for the higher weight decay. 

The results on the language modeling task are impressive but for the algorithm to be accepted as a particularly good algorithm for RNNs it should compare to the more elaborate SotA algorithms for this particular task (AdaQN was proposed). 



----
Some points that would be good to address regardless of outcome (no influence on my decision):
- Does the algorithm work in the $\beta=0$ setting? SGD with momentum reverts to SGD and Adam reverts to RMSProp which both are competitive optimizers. Does that also hold for Apollo?
- How are the values in Table 5 (D.3) calculated? Depending on the implementation of Apollo it looks like 3-4 parameter-sized vectors are required per update ($g$,$m$,$B$,$d$) which in the case of 4 is twice the amount of SGD with momentum, yet the memory is only a few % larger.
- In algorithm 2 you should replace $\lambda$ with $\gamma$ to be consistent with the rest of the paper.

review_title: Official Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper is clearly written and easy to understand. The authors give a clear introduction to Newton and quasi-Newton methods, and summarize three main drawbacks of quasi-Newton methods for nonconvex stochastic optimization which is the real case for many practical problems. The three main challenges are stochastic variance, nonconvexity and inefficiency.

As far as I known, there is no quasi-Newton methods that could solve the above challenges simultaneously, and this paper give a solution that considering all the three aspects.

For efficiency, the computational and memory efficiency are both considered. Instead of depending on first order informations from m previous iterations, the proposed method approximates the Hessian matrix by  considering  the diagonal parameters of B_t which is more memory and computational efficient. 

To solve the stochastic variance, the authors propose stepsize bias correction to work better in stochastic gradient descent framework. And exponential moving average to g_t is adopted to make the gradient more stable.

And to better support nonconvexity, a rectified trick is used in the constraint B_t. What’s more, in order to produce a better Hessian approximation, a parameter-wise weak secant condition is used.

All the above ideas look reasonable, and this give a full workable solution to train networks in variance domains.

The authors conduct several experiments in Image Classification, Language Modeling and Neural Machine Translation, and experiments show the effectiveness of the proposed method. The proposed method has advantage in all tasks, and for Language Modeling, the improvements seem to be very large.

Questions:
(1) What are the effects of different factors such as “stepsize bias correction”, “rectified trick” and “a parameter-wise weak secant”.
(2) Why the improvements for Language Modeling are larger than for Neural Machine Translation and Image Classification?

The authors are strongly suggested to test more network structures on challenging tasks and try to achieve new state of the art results which could make the method more convincing. And more theoretical analysis is suggested to better understand the proposed method.

==========

I would like to change my rating from 9 to 5. The paper proposes an interesting idea and does achieve good results on several datasets. However,  after reading all the comments and feedbacks, I notice that the comparisons are not convincing enough, and I have some concerns about the performance of the proposed method on more general and challenging tasks.
review_title: This paper proposes a new quasi-newton optimization method for nonconvex stochastic optimization which is widely used in training deep learning models. This paper solves several drawbacks of existing quasi-newton optimization methods and achieves good results in various deep learning problems.

Meta-review: Dear authors,

I took your concerns into account, and I also understand the whole crazy situation around the COVID-19. Many of the reviewers have families (e.g., in US, many kids are now homeschooled, and there are no good daycare solutions as well). I do not plan to list all the good parts of the paper and list weaknesses that are already mentioned and visible to you. Hence, let me focus on my concerns about this paper (and I hope you could find them interesting and they will help you to improve your paper).

+ I personally find the use of 2nd order method in DNN a way to improve many inefficiencies of ADAM/SGD, .... and using diagonal scaling is one way to do it. 

-- I personally find some sections not very motivated and explanatory. E.g. Section 3.2 is just telling half of the story and is missing some details to give the reader the full understanding.

-- The fact that B_t  is not necessary >0, it makes intermediate sense to use some kind of \max\{B_i, \sigma\}  to have the "scaling" to be $\succ 0$.
Note that there are also SR1 methods that would guarantee the matrix to be not necessary pd.

-- Your main motivation was non-convex problems, but the only theorem in the main paper was for convex loss only, right? In this case, I guess there is no issue with B_t to have some coordinates <0, right?

Overall, I find the topic interesting and would like to see an updated paper in some of the top ML venues, but right now I cannot recommend it for acceptance!


Decision: Reject