Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In various machine learning problems which can be formulated as a bilevel optimization problem and solved using gradient-based methods, the computation of hypergradients is necessary. However, the involved inverse Jacobian matrix in the hypergradient has been a computational bottleneck in high-dimensional settings. This paper proposes to use quasi-Newton matrices from the forward pass to approximate this inverse Jacobian matrix in the direction needed for the gradient computation which appears in the computation of hypergradients. The proposed algorithm is applied to both hyperparameter optimization and deep equilibrium models for CIFAR-10 and ImageNet, showing that it reduces the computational cost of the backward pass by up to two orders of magnitude. 
main_review: I believe that this paper is studying a crucial problem. Both deep implicit/equilibrium models and hyperparameter optimization, which can be formulated as bilevel optimization problems, are important applications in machine learning. In particular, the computational bottleneck in hypergradient computation has long been a stumbling block for their applications in high dimensional settings. The proposed method of this paper borrows ideas from L-BFGS and Broyden’s method, which appears to be natural choices to consider. The authors establish various convergence results showing that the approximate hypergradients converge to the true hypergradients, under different sets of assumptions. Experimentally, the proposed method is comparable to or outperforms the Jacobian-Free method by Fung et al. (2021) in hyperparameter optimization for logistic regression and DEQs. The proposed method is interesting and can be viewed as a complementary method to the recent Jacobian-Free method. 

Typos: 
- Add punctuation whenever necessary in display style equations, like (1), Theorem 2, (4) and (6)
- page 8, Figure 2 caption: “wihtout” to “without”
summary_of_the_review: This paper studies the problem of approximating the inverse Jacobian matrix in hypergradient computation for bilevel optimization problems solved with gradient-based methods, in an attempt to reduce the computational bottleneck of computing the exact inverse Jacobian matrix in high dimensions. The proposed method leverages quasi-Newton methods for such approximations. Experimental results have demonstrated the effectiveness of the proposed approach.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a way to improve on the computational cost of bi-level optimization problems. These often come up in recently proposed Deep Equilibrium models and in hyperparameter optimization settings in ML.
main_review: Strengths:
- The theoretical aspects of the paper especially Theorems 3 and 4 are novel and good ideas. 
- The theoretical part of the paper is written very well for someone unfamiliar with the literature. 

Questions:
- Figure 1: On the 20 news dataset, the variance around the convergence of SHINE methods is a little concerning. Especially if one wishes to make the claim of "An acceptable level of performance is reached twice faster for the SHINE method compared to any other competitor".
- Again in Figure 2 left: The variance in the convergence curves of SHINE methods requires further comment by the authors. Perhaps it will be a good idea of having N runs and reporting average runtime improvement benefits over other methods along with a standard deviation.
- Figure 3: it seems that the Jacobian-free method and SHINE are almost equally performant in terms of top-1 accuracy while SHINE takes longer due to additional updates? While this is discussed briefly, I would like the authors to dig a bit deeper on why that is the case. As I understand right now, the authors claims are that the Jacobian free method is working outside the assumptions used to prove its convergence but it seems that even their method is well outside the scope of its assumptions? I am unsure what the claims are here. Why would one use SHINE over the Jacobian-free method for the DEQ models?

summary_of_the_review: Overall, I like the core idea and theoretical insights of the paper but have questions regarding the experiments as indicated in my main review. I am willing to update my scores based on author responses.

Update:

I would like to thank the authors for thoroughly engaging with reviewers on the platform. After reading the author responses to my review and other discussions on this forum, I am convinced that the improved draft should be presented at the conference and vote to accept the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In implicit deep learning such as deep equilibrium models, computing the inverse Jacobian for the forward pass is computationally expensive. This paper propose an interesting approach to combine the information from the forward and backward pass to make an efficient estimate of the Jacobian inverse. In one approach, they propose to replace the Jacobian in the backward update with the quasi-Newton matrix, which is being already used/estimated in the forward pass solved by quasi-Newton method. Additionally, they propose an iterative update to the quasi-Newton matrix such that to helps its estimate toward the direction useful in the backward pass (they call this outer problem awareness).

They provide theoretical analysis of their proposed method and show that under certain conditions/assumptions, the forward pass still converges to the desired solution and the sequences of backward estimates converges to the loss gradient of needed to parameter updates. They provide numerical results in bi-level optimization (regularized logistic regression) and training DEQ for classification. In certain settings (bi-level optimization), they show that they outperform Jacobian-free and have similar performance to the state-of-the-arts but it is faster than all. For DEQ, they show similar performance to Jacobian-free.
main_review: Strong points:

The paper starts with a clear motivation and proposes an interesting approach to combine the computations from the forward and backward pass to accelerate the backward pass. The simplicity of their approach is an strength. Given the method, the paper provides theoretical analysis on the convergence of their forward and backward estimate to the desired computation. The theory is written well, seems correct, and states clear assumptions. The authors discuss the assumptions well (in case of whether they are used in any other works and if they are common). They provide detailed numerical results and experiments. In certain settings, they show faster performance than the original with similar performance.

Weak points:

Some of the experimental results are not convincing. For example, although they outperform Jacobian free method in the regularized logistic regression, they show similar performance to the Jacobian free in the case of classification with DEQ. So, why one may use SHINE which is slower than Jacobian free but have similar accuracy?

- An extensive experimental study is needed to compare the two (SHINE and Jacobian-free). For the proposed method to make practical sense, the author should show the wide settings at which SHINE is better than Jacobian free. For example, is SHINE better in any other bi-level optimization in addition to the regularized logistic regression?

- A discussion in the MAIN paper is needed for experimental studies on the relation between the quality of the inversion and the performance. I recommend to move Figure E.2 to the main text for this matter. Please explain why the quality of the inversion and performance are not correlated.

- Fallback strategy is of concern. Please provide more intuition of this instability and why it is not seen in other methods. How much is "barely" in the statement "we verified that the fallback is barely used?"

- The bullet points of contributions need to be more precise.

- Figure 1. Fix typo "Freee".


Post dicussion opinion: see the discussion. Given the additional HO experiment and elaborations in the abstract, I have revised my rating and I recommend acceptance of this paper.
summary_of_the_review: The paper's main motivation is to computationally improve the backward pass. They show speed improvement compared to the other methods involving inversion of the Jacobian and minimal decrease in performance. However, they do not show performance improvement compared to the Jacobian free which is faster than the method in DEQ experiment. Given this, why one may SHINE that approximates the inverse Jacobian when their method does not outperform the Jacobian-free method? More experimental results is needed to highlight the advantage of their method against Jacobian-free. This advantage is already shown once in the regularized logistic regression.
review_title: null

Meta-review: The paper considers the setting of bi-level optimization and proposes a quasi-Newton scheme to reduce the cost of Jacobian inversion, which is the main bottleneck of bi-level optimization methods. The paper proves that the proposed scheme correctly estimates the true implicit gradient. The theoretical results are supported by numerical experiments, which are encouraging and show that the proposed method is either competitive with or outperforms the Jacobian Free method recently proposed in the literature.

Even though the reviews expressed some initial concerns regarding the empirical performance of the proposed method, the authors adequately addressed those concerns and provided additional experiments. Thus, a consensus was reached that the paper should be accepted.
Decision: Accept (Spotlight)