Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a novel adaptive second order method: ''OASIS'', for large scale optimization problems (convex and nonconvex). The search direction is obtained by preconditioning the gradient information with a matrix obtained by approximating the Hessian diagonal matrix (via Hutchinson's method with a momentum term). The learning rate is updated adaptively by approximating the Lipschitz smoothness parameter. On the theoretical front, convergence analysis is provided for the adaptive learning rate case, for the convex and strongly convex setups. Similar analysis is also provided for the fixed learning rate (LR) case, for the strongly convex and nonconvex settings. Finally, extensive empirical results are provided which show that the proposed method achieves comparable, and sometimes better results than other existing methods.
main_review: ------ Pros ------

The paper has the following strengths.

1) Very well written paper providing a clear motivation for the problem considered.

2) The theoretical results involving the convergence analysis of the method are rigorous, and cover both convex and nonconvex settings.

3) The empirical evaluation is extensive and provides a good indication of how the method performs in practice.

------ Cons ------ 

The paper has the following weaknesses. 

1) There is currently not much discussion on the interpretation of the bounds appearing in the convergence analysis. 
For instance, how do these results compare with those for existing second-order methods (e.g., AdaHessian)? 

2) It would have been helpful to have provided some kind of proof sketch of the theoretical results, or atleast an 
overview of the key steps which I believe might be common to more than one theorem. At the moment, no such explanation is 
provided for any of the theoretical results. 
 
------ Further remarks -------

1) The setup in Fig. 1 is really not clear to me. What is meant by number of samples (x axis of left plot)? Is there an underlying optimization problem considered here such as a quadratic function with matrix A? Some more detailed explanation on the experimental setup considered for the figure will be very helpful.
	
2) In Fig. 2, the parameter $\lambda$ is not clearly defined, I believe this occurs much later in the experiments section.
	
3) In eq. (6), is the matrix $D_k$ formed by just generating a Rademacher $z$ and forming $D_k = z \circ \nabla^2 F(w_k) z$? Because in the AdaHessian paper, they also consider a spatial averaging step for better estimation of the Hessian diagonal. Also, should $z$ be $z_k$ as in eq. (8) later?
	
4)  As mentioned on pg 4 in the discussion on literature for adaptive LR, the present paper draws upon ideas from the literature on first order methods for adaptive LR. So couldn't one do the same analysis for AdaHessian for adaptive LR? 
	
5) It wasn't clear to me why AdaHessian (eq. 6 and 7) doesn't approximate the diagonal well, while  OASIS (eq. 8 and 9) does a better job. 
Because we see a (temporal) average in eq. 7 as well, which means AdaHessian should also smooth out the Hessian noise over  iterations. Is there any conceptual reason behind this?
	
6) In Section 3.2, shouldn't the distribution from which the sets $\mathcal{I}_k, \mathcal{J}_k$ are sampled be specified (e.g., uniformly at random)? Or is it the case that the conditions on the distribution are subsumed by assumptions 4.14-4.16?. Also, in assumption 4.16: the sentence ''where the samples $\mathcal{I}$ are drawn independently'' should be removed since there is a single random variable $\mathcal{I}$. 
	
7) Since $z_k$ is random, one would imagine that this randomness is accounted for in the convergence analysis, which doesn't seem to be the case. For instance the theorems 4.6, 4.9 seem to be worst case bounds. Moreover, the bound in theorem 4.9 depends on $\hat{D}_k$ which is a random variable. This point needs further clarification.
	
8) In theorem 4.17, its better to write $\eta_k = \eta$ for consistency of notation.

9) Both theorems 4.17, 4.18 show convergence to neighborhoods of stationary points, and not to the stationary points themselves. There is a discussion after theorem 4.18 regarding this aspect, but it seems a bit strange why this (e.g. decaying learning rate) is not accounted for in the analysis to begin with?	
summary_of_the_review: The paper is written in a very clean manner, and is easy to follow. Sufficient background is provided in the introduction which gives the reader a good context to understand the problem setting and contributions. The preconditioning step is a modification of an existing method AdaHessian, and the adaptive LR part builds on techniques used for deriving adaptive LR rules for first order methods (Mishchenko and Malitsky 2020). So the novelty aspect is a bit limited in that respect. The theoretical results are outlined rigorously, although it is not clear what is the novelty of the theoretical results compared to those for other second order methods. The empirical evaluation is quite extensive and satisfactory in my view. I am giving it a 6 at the moment since I have other comments (in ''Further remarks'') which I hope can be addressed during the rebuttal phase.

------------- Post rebuttal ---------

As mentioned in the comments, I am satisfied with the author's response to my concerns and I am happy to increase my score to 8.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper designs and analyses an algorithm for minimizing a separable function. It provides deterministic as well as stochastic versions, which either fully compute the gradient or sample it. The algorithm estimates the diagonal elements of the Hessian via Hessian-vector products. The algorithm makes use of this information for finding a better search direction and the step length, eliminating the need for a line search. It provides convergence guarantees and a number of experiments on classical ML problems as well as on deep nets.
main_review: Strengths: 
- The paper considers a fundamental problem in ML, i.e., minimizing a separable function.
- The algorithm and its convergence are proven for many cases, i.e., deterministic, stochastic, convex, non-convex.
- Empirical evidence is given that the algorithm outperforms comparable approaches like AdaHessian, etc.
- No need to tune a learning rate since the step lengths are determined by the curvature of the function. This can be really a huge advantage in the stochastic setting, i.e., in deep learning.

Weakness:
- The empirical evidence/experiments are rather limited. 
  Deterministic case: Only two experiments are provided (logistic regression, non-linear least-squares) and only two data sets. Furthermore, a comparison to other minimization methods would be very beneficial in this case, and not only to AdaHessian and AdGD. (Yes, it is stated in the paper that comparison to only diagonal preconditioners is made but in general, there are many more methods to solve this case, e.g., quasi-Newton methods or trust region Newton-CG methods which are also used for computing the optimum in the provided code. These methods make use of the same information as the presented method and hence, a comparison to these methods would also be useful for a better global picture.) 

  Stochastic case: Again, only a very limited number of experiments is provided here. Having not to tune the learning rate is an enormous plus here and it would be nice to verify the algorithm's robustness on a number of different problems/nets. The experiments suggest that OASIS would be a viable replacement for SGD, Adam, etc. But for such a bold statement, more experiments are needed.
summary_of_the_review: I like the paper, the algorithm, and its versatility. Especially that one does not need to tune a learning rate can be very beneficial. I did not fully read the convergence proofs though they seem sound. According to theory and experiments, one should always use this algorithm. It would be nice to justify this claim by a more comprehensive study, e.g., more problems, datasets, and other algorithms in the deterministic case and more nets and data sets in the stochastic setting. Only then one can tell if it is superior to state-of-the-art approaches. If such experiments were provided in the paper I would have given a higher score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes OASIS, a second-order method which approximates the diagonal of Hessian matrix and uses the information to rescale the gradient vector. The main difference between OASIS and the existing method AdaHessian (Yao et al., 2020) is on the ways they approximate the diagonal of Hessian, that AdaHessian uses a formula similar to Adam and OASIS uses an exponential average. Moreover, OASIS also incorporates the adaptive stepsize in (Mishchenko & Malitsky, 2020). The authors established the convergence guarantees of OASIS under various settings including convex, strongly convex and nonconvex cases, using various learning rate schedulers such as the adaptive learning rate, fixed learning rate and line search. Empirical results on various machine learning tasks are provided to evaluate OASIS.
main_review: The paper is nicely written and easy-to-follow. The topic on how to effectively leverage the Hessian-vector oracle in large scale machine learning tasks is definitely important and interesting. 

For the main ideas, the authors show in Figure 1 that OASIS approximates the diagonal of Hessian much more accurate than the Hessian momentum in AdaHessian, which is the main point made in the paper (I have the feeling that the Hessian momentum is not solely for approximation? like the first-order momentum vector may not be an accurate approximation for the gradient vector, but is effective for acceleration). Another point is that OASIS incorporates the adaptive stepsize in (Mishchenko & Malitsky, 2020), which allows it to adapt to the local Lipschitz constant (wrt a weighted Euclidean norm) and thus reduces the tuning effort. However, it seems to me that these ideas are a bit straightforward and not particularly novel. From my perspective, AdaHessian is a ''diagonal-Hessian-variant'' of Adam and OASIS is the corresponding variant of RMSProp. It seems that the adaptive learning rate can also be incorporated into AdaHessian by choosing a different weighted norm.

For the theory part, I appreciate the thorough analysis of OASIS under various settings. However, I was hoping for more insightful discussion on these results, such as how the theorems would suggest a better parameter choice. Currently, they are only convergence guarantees, which could be far from the practical performance. The theorems in Section 4.1 generalize the results in (Mishchenko & Malitsky, 2020) in the deterministic setting while there seems to be no theoretical advantage of such generalization (BTW, is there any bound on the scale of $Q_k$ in Theorem 4.6? It seems that it can be of the order $O(k)$ which kills the convergence).  

For the empirical results, the authors considered various machine learning tasks and the deviation is also plotted in the figures, which are appreciated. However, the improvement in most of the results seems marginal to me, and thus may not be appealing to practitioners especially since the Hessian-vector oracle is around twice as expensive as the gradient oracle (for neural nets). Moreover, OASIS still requires a learning rate scheduler as shown in the CIFAR results, which makes the statement "Our methodology does not require the tedious task of learning rate tuning" not well-supported.

Minor comments:
- Equation (7) is not centered.
- Typo in the citation "Adaptive gradient descent without descent.  In 37th International Conference on Machine Learning (ICLM 2020), 2020"
- I think Lemma A.1 is covered by Theorem 2.1.5 in Nesterov's updated book "Nesterov, Y. (2018). Lectures on convex optimization (Vol. 137). Berlin, Germany: Springer International Publishing".
summary_of_the_review: I appreciate the authors' efforts on the comprehensive analysis and empirical evaluations of the proposed OASIS. The paper is also very well written. However, both the theoretical and practical results seem incremental to me. The construction in OASIS also seems a bit straightforward. Moreover, OASIS still requires parameter tuning in some of the experiments, and thus is not "fully adaptive".
review_title: null

Meta-review: The paper presents a novel approximate second order optimization method for convex and nonconvex optimization problems. The search direction is obtained by preconditioning the gradient information with a diagonal approximation of the Hessian via Hutchinson's method and exponential averaging. The learning rate is updated using an estimate of the smoothness parameter.

The merit of the paper has to be evaluated from the theoretical and empirical point of view.

From the internal discussion, the reviewers agreed that the new algorithm is a mix a known methods, mainly present in AdaHessian, with a small tweak on the exponential average. Moreover, the theoretical guarantees do not seem to capture the empirical performance of the algorithm nor they provide any hint on how to set the algorithm's hyperparameters. For example, in Theorem 4.6 the optimal setting of $\beta_2$ is 1. That said, the most important theoretical contribution seems to lie in the fact that AdaHessian did not have any formal guarantee. Hence, this paper is the first one to show a formal guarantee this type of algorithms.

From the empirical point of view, the empirical evidence is very limited for the today standards in empirical machine learning papers. The reviewers and me do not actually believe that the proposed algorithm dominates the state-of-the-art optimization algorithms used in machine learning. However, in the internal discussion we agreed that the algorithm has still potential and it should be added to the pool of optimization algorithms people can try.

Overall, considering the paper in a holistic way, there seems to be enough novelty and results to be accepted at this conference.

That said, I would urge the authors to take into account reviewers comments (and I also add some personal ones here). In particular, a frank discussion of current theoretical analysis and empirical evaluation is needed.

Some specific comments:
- AdaGrad was proposed by two different groups at COLT 2010, so both papers should be cited. So, please add a citation to: 
McMahan and Streeter. Adaptive bound optimization for online convex optimization. COLT 2010.
- Remark 4.7, second item: Neither Reddi et al.(2019) nor Duchi et al. (2011) *assume* bounded iterates, that must be proved not assumed. Instead, they explicitly project onto a domain that they assumed to be bounded.
- The convergence of the gradient to zero does not imply convergence to a critical point. To prove convergence to a critical point you should prove that the iterates converge, that in general is false even for lower bounded functions. Indeed, consider $f(x)=log(1+exp(-x))$, the iterates would actually diverge while the gradient still go to zero.
Decision: Accept (Poster)