Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors introduce a learn-to-optimize (L20)-based approach for quasi-Newton algorithms. The main idea is to learn on-the-fly an approximation of the inverse Hessian matrix modeled as the product of random permutation and block diagonal matrices. The proposed architecture called LODO consists of a linear neural network whose depth affects the representation power of the Hessian approximate. The authors provide a theoretical representability theorem showing that LODO can exactly represent the Hessian matix with high probability that increases with the depth of the linear neural network. They also provide simulated and an MNIST image generation experiment showing the promising performance of the proposed approach.
strength_and_weaknesses: Strengths:

1) Learn-to-optimize (L2O) algorithms leverage the power of deep neural networks to achieve better convergence rates for several problems over classical optimization algorithms. 
2) LODO builds on these ideas to come up with a novel L2O approach for quasi-Newton algorithms. 
3) The whole idea is quite attractive since it can lead to algorithms that will take advantage of Newton-type methods using the strengths of the L2O framework.   

Main comments/ Weaknesses:
1) It is hard to follow several parts of the paper. Specifically, Section 4 is poorly written. In Sect. 4.1 the authors describe the Hessian learning dynamics without giving the full details of the setup they consider. Hence it is hard to follow the ideas given later. 
2) In Section 4.2, Definition 1, the definition of function $\epsilon$ is missing. Besides, it is hard to follow the text, which is densely written and not clear at all. 
3) The statement of Theorem 1 lacks clarity and important details are missing. How $G(\theta)$ is sampled ? What is M? Also $\epsilon()$ is not defined (see also above).
4) In Section 5, Section 5.1., it is not clear why the training loss of other methods .e.g. RMSprop, Momentum etc. remains so much higher than LODO. 
5) Section 6 could merge with Section 5. 



clarity,_quality,_novelty_and_reproducibility: The paper presents novel and interesting ideas. However, Section 4, which presents theoretical results, is not clearly written making it hard to follow the importance of the results. Also, the experimental section could be improved. It would be better to move some experiments to the appendix rather than keeping all of them in the main paper but leaving important details of them in the appendix due to space limitations.
summary_of_the_review: The  paper introduces a L2O-based algorithm for quasi-Newton methods. The idea of approximating the inverse Hessian with linear neural networks whose parameters are learned on-the-fly is interesting. However, theoretical results are not presented clearly. Hence, it is hard to assess their significance and value the importance of the specific parametrization of the inverse Hessian introduced in the paper.
Moreover, the organization of the experimental part could be improved.

-----------------------------------------------------
Post-Rebuttal Comment:
I would like to thank the authors for their time and effort to address my comments/concerns.
At this time, I will my score unchanged.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes LODO, an L2O that performs quasi-Newton optimization without any meta-training. Specifically, LODO has a hypergradient optimization structure while the parameterization of the approximated inverse Hessian is chosen to be a linear neural network. The authors prove that under certain simplified situation, LODO learns the true inverse Hessian, and that the linear neural network construction is expressive in that it can represent all linear neural networks smaller by a logarithmic factor. Experiments are provided to evaluate the effectiveness of LODO.
strength_and_weaknesses: Strength:
- The construction of LODO seems interesting, which could inspire future development on online L2O methods without any meta-training.
- The theoretical discussion on the inverse Hessian approximation and the expressiveness seems solid. 

Weaknesses:
- The empirical performance of LODO is not promising, and only limited experimental results are provided.
- I believe that the theoretic discussion in section 4.1 requires the Hessian $H$ to be at least PSD, since $G(\theta_t)$ is constructed to be PSD. But it is not clear to me which step of the proof relies on the PSDness. This needs to be clarified. 
- When the objective function is non-convex, such that $H$ is potentially not PSD, what will be learned by $G(\theta_t)$? Will it capture all the positive curvature of the loss landscape and neglect the negative curvature?
- I think more ablation study for the effect of each algorithmic component in LODO is necessary, such as comparing LODO without momentum, LODO, plain momentum, LODO using SGD to tune the model, etc.  

-----------------------------------
Post rebuttal: Thank the authors for the response and the additional experiments, which resolve some of my concerns. However, I still think the empirical performance of LODO is not strong enough, and I agree with reviewer oyKA that the comparison with other methods is underwhelming. Thus, I keep my assessment.
clarity,_quality,_novelty_and_reproducibility: The writing is generally good. Please specify the requirement for the Hessian matrix $H$ in section 4.1, and reflect it in the proof.
summary_of_the_review: This work can be seen as an initial attempt for developing online L2O methods without any meta-training. However, the discussion of LODO in the current version is insufficient, see the main review.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes to meta-learn an optimizer to approximate Newton's method, namely to learn a pre-conditioner for gradient descent to approximate the inverse Hessian.
It proves that the method learns the inverse Hessian for quadratic loss functions, and that the proposed parameterization of the pre-conditioner is expressive under some circumstances.
The method is tested on autoregressive image generation for MNIST.


strength_and_weaknesses: Strengths

- Meta-learning optimizers is a promising area of research.


Weaknesses

Some of the claims in this paper are wrong or obvious, and comparison with previous work is not appropriate.

- Section 4.1 is trivial. It is obvious that the method learns the inverse Hessian in the case of a quadratic loss, because it is known to be the best pre-conditioner in that case (it converges in one step from any initial condition).
However, for non-quadratic loss functions the best pre-conditioner is not the inverse Hessian, and the proposed method will not learn the inverse Hessian.
This is particularly obvious for non-convex loss functions, where the inverse Hessian is not even positive definite and Newton's method would not even converge to a minimum of the loss (see e.g. https://arxiv.org/abs/1406.2572)

- The statement "the true inverse Hessian is guaranteed to be symmetric positive-definite" is wrong, that is not true for non-convex losses. 
I assume that is the field of application of this method since the authors apply their method to non-convex losses in sections 5.2, 5.3.
If the authors refer to convex losses, then they should compare their method with other methods for convex optimization.

- Related to the last point, for autoregressive image generation the authors report that "we could not get any quasi-Newton methods to converge on this task."
It seems that authors are not aware that quasi-newton methods should not be expected to converge on non-convex problems, again because the Hessian is not positive definite.

- Comparison with other methods is underwhelming and other, more powerful methods are not even considered.
I do not even consider the quadratic problem because results in that case are trivial.
For the autoregressive image generation task, the proposed method does not perform significantly better than momentum.
Other, more powerful methods are not even compared with (see e.g. https://arxiv.org/abs/2006.08877).

- Even without all problems above, the method is not so novel. 
Many other studies have tried to learn pre-conditioner for neural networks, inclusing some that the authors do not cite (see e.g. https://arxiv.org/abs/1902.03356)


Minor:
- Even in the quadratic case, in Fig.3 (Left) it seems that the error does not converge to zero, meaning that the method fails to learn the inverse Hessian.

clarity,_quality,_novelty_and_reproducibility: The paper is clear.
Novelty is questionable given that many other methods meta-learn a pre-conditioner for gradient descent, some of which are not cited / compared with.

summary_of_the_review: The problem is interesting but some of the claims in this paper are wrong or obvious, and comparison with previous work is not appropriate.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes to learn a preconditioner that would approximate the inverse of the hessian thus resulting in faster training without having to explicitly compute the expensive hessian. This is achieved by jointly optimizing the objective in the iterates and preconditioner and performing a 1-step unrolled optimization. The paper then studies the convergence of the algorithm for a quadratic strongly convex objective and shows that the preconditioner converges towards the inverse of the Hessian. In addition, the authors propose a computationally cheap parameterization of the pre-conditioner which provably still retains good approximation capabilities. The method is tested on simulated and MNIST image generation experiments showing promising performance. 
Given that the paper was borderline, there have been long discussions going on between the reviewers and AC after which a consensus was reached that the paper is currently not ready for publication to ICLR and would benefit from additional work to improve its clarity and comparisons with existing methods in the literature. 


Here are some directions of improvement:

Reviewer oyKA raised concerns about the lack of empirical comparisons with methods such as natural gradient, etc which acts as pre-conditioners as well. Reviewer XFBK agrees that the comparisons are underwhelming. The paper could benefit from additional experiments to illustrate the gain of learning such pre-conditioners compared to developing faster approximations to better-understood conditioners. 

In addition, oyKA pointed to a limited novelty since one-step unrolling of the inner loop optimization has been previously used to learn pre-conditioners. It appears that the main effective novelty is the use of momentum along with unrolling. Currently, the theoretical analysis does not account for the effect of momentum, which seems to be a key component for the improved results. 

As pointed out by Reviewer w1wa, the paper lacks clarity, especially when presenting the theoretical contributions which make the reading hard to follow. Despite the improvements made by the authors during the rebuttal, the presentation of the approximation results is currently hard to parse and needs more context to introduce the required concepts.


justification_for_why_not_higher_score: The paper needs more work to improve the clarity and comparison with existing related work.
Decision: Reject