Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a Hessian-free bi-level optimizer called partial zeroth-order-like bilevel optimizer (PZOBO). The method uses a zeroth-order-like Jacobian estimator, which provides accurate hypergradient estimates and a computationally effective way of solving bi-level optimization problems. The paper presents a thorough theoretical analysis and experimental validation on various bi-level problems. 
strengths_and_weaknesses: + The paper addresses the important bi-level optimization problem by providing an efficient and accurate solution.

+ The paper shows the convergence guarantee of the proposed approach. 

+ Experimental results and comparisons with various baseline bi-level optimizers are provided over various bi-level problems. The proposed method generally outperforms baseline methods, especially in high-dimensional problems. 

questions: + Covariances should be added to the curves to better illustrate the performance variation. For example, Figures 3(a) and 3(b) shows the covariances but other figures do not. 

+ In related work, an analysis of the limitations of previous solvers and a discuss of how the proposed method can address those limitations can be helpful to evaluate the novelty and impact of the proposed method.

+ The text refers to Figure 4(a), (b) and (c), but Figure 4 does not have subfigure labels.

+ The consistency of figure formatting can be improved. For example, the shadows at the bottom of some figures such as Figures 2(d) and Figures 2(f).

limitations: This work does not have negative society impacts. A further discussion of the limitations of the proposed bi-level optimizer will be helpful. For example, the paper assumes the inner-level function to be strongly convex. How the proposed approach can be extended to address problems without this assumption?
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: ## Further Update

Not all my concerns are fairly treated and addressed in the discussion period (as the authors have promised). I lower the overall rating from 6 to 5 and the presentation rating from 3 to 2. This is my final decision.

## Update

I changed my rating from 4 to 6 due to the fair rebuttal from the authors.

---

This paper proposes a zeroth-order based solver for bi-level optimization problem. In order to avoid the heavy computation of Hessian matrix and its inversion, the paper proposes to directly approximate the Jacobian matrix (implicit gradient) through function value difference and develops a Hessian-free bi-level algorithm. For the proposed method, the authors provide convergence analysis for the proposed zeroth-order algorithm and reach a non-asymptotic performance guarantee.
strengths_and_weaknesses: Strengths:

1. Theoretical: The theoretical contributions are the main strength of this paper. To analyze the zeroth-order approximation, the authors must take into consideration the bias, variance, smoothness, and boundedness of the proposed optimizer, and this procedure is even more difficult when the commonly adopted Lipschitz-smooth assumption does not apply. The authors make very detailed discussion on different application scenarios of the proposed method and obtain meaningful result. This is difficult and remarkable.

2.  Various experiments were conducted on different deep learning tasks to show the effectiveness of the proposed methods. The results generally look good and do outperform baselines.

Weaknesses:

1. Novelty: My main concern lies in the novelty of the paper. As is all known, that zeroth-order is a common technique even in the context of bi-level optimization. For example, DARTS [34] also used the zeroth-order method to solve the Jacobian-involved term without calculating Hessian matrix. I wonder what is the difference between this paper and DARTS in terms of theory as well as performance. In general, zeroth-order approach is not a novel ingredients in bi-level optimization and this greatly constrains the novelty of the proposed method.

2. Experiments: I strongly suggest the authors to add some experiments on neural architecture search (NAS) for bi-level tasks. As I mentioned above, DARTS [34] used very similar approaches and I am curious which one performs better.

3. Multiple trials: The authors do not report any results on the variance of any of the experiments. It is significance to report the variance to show the stability of each algorithm as well as the significance of the improvement.

4. Minor issues: In all the plots/figures, the authors are suggested to use similar font sizes in ticks, axis labels, and legends. It is difficult to read the labels of all the figures in this paper. 

In general, I believe the theoretical part of the paper is excellent, but the method proposed lacks major innovation and significance.
questions: Please see the comments in the weaknesses above.
limitations: The authors have adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents an algorithm and its stochastic extension to finite sums for solving smooth bilevel optimization problems which avoid computing the hessian associated to the lower level problem by instead using zeroth order oracles. Rather than approximate the entire gradient of the entire loss function in the upper level problem using zeroth order methods, the proposed algorithms only approximate the gradient of the solution mapping for the lower level problem with zeroth order methods, reducing variance and improving the method. Convergence guarantees are proven and four numerical experiments are performed that suggest the method is competitive with some contemporary methods.
strengths_and_weaknesses: Overall, I found the paper to be well written and of high quality. The main idea, to use zeroth approximations of the Jacobian of the solution mapping for the lower level problem with respect to the hyperparameters appears to be original and significant, to the best of my knowledge. Some parts of the paper could be clearer, as touched on in the questions and limitations sections, but otherwise the main ideas are well-communicated. Regarding the experiments, they are limited to comparing to baselines and I think it's a weakness not to compare against other first-order optimization methods like AmIGO [Arbel, Mairal 2022] or single loops algorithms like SABA [Dagréou et al 2022].

"Amortized Implicit Differentiation for Stochastic Bilevel Optimization" - Michael Arbel, Julien Mairal, 2022

"A framework for bilevel optimization that enables stochastic and global variance reduction algorithms" - Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, Thomas Moreau, 2022
questions: It's not clear what is the dimension of the hyperparameter vector in the various experiments; is p=1 in 4.1, for example? Even after searching the appendix I couldn't find it written what is the dimension of the hyperparameter vector for the applications.

On line 265 a bilevel optimization problem for an application is given - is the lower level problem really strongly convex and smooth here? 

On line 131 you use that g is twice differentiable but you have only assumed it's C1?
limitations: One limitation is that there are many assumptions to apply the results. The assumptions are clearly stated which help alleviate this issue but the authors should address the limitations imposed by the assumptions in the numerical experiments because not made clear that the assumptions needed to apply the theorems are met. I think you should be explicit when/if the assumptions are being broken and whether or not the theorems that were proved actually apply to these practical examples. In the appendix it's sometimes mentioned when the lower level problem is strongly convex but I think for the neural network examples it could be nonsmooth and this should be mentioned as a limitation.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work focuses on the Hessian-free bilevel optimization, which is a timely topic in machine learning, and has been widely used in many important applications such as neural architecture search, hyperparameter optimization, reinforcement learning, etc. In particular, the authors study the convergence performance and efficiency of Hessian-free bilevel algorithms via zeroth-order estimation, which have shown promise in many deep learning applications such as ES-MAML in meta-reinforcement learning, HOZOG in hyperparameter optimization. The authors first address an important variance and convergence issue of existing zeroth-order method, and propose to estimate only the response Jacobian of the hypergradient using direct forward propagation without any backpropagation. They further provide a convergence rate analysis for the resulting Hessian-free PZOBO method with partial hypergradient estimation and its stochastic version PZOBO-S. Extensive experiments support the convergence theories and justify the effectiveness of the designs in various applications. 
strengths_and_weaknesses: This work is generally written and motivated well. The finding that partial zeroth-order hypergradient estimation can improve the variance and convergence is a good contribution to Hessian-free bilevel optimization, in particular for the supervised scenarios. The proposed zeroth-order-like response Jacobian estimator enables a simple implementation in practice, in particular admitting a very easy extension to the stochastic case. This is kind of important because for conventional AID or ITD types of methods, more involved procedures such as Taylor expansion types of stochastic estimation are needed for hypergradient computations. 

The analysis developed in this paper seems to be the first convergence rate analysis for zeroth-order bilevel optimization. Although the high-level idea comes from the zeroth-order optimization, there are indeed some differences under this bilevel structure. For example, from my reading, the smoothness property of the N-step output of the lower-level gradient-based algorithm established in Proposition 1 needs to conduct a recursive analysis on the entire gradient path, and the error characterization of stochastic Jacobian estimator needs to take the randomness of points in the path into consideration. Such analysis seems nontrivial to me. 

Experiments seem to be comprehensive, on different applications such as representation learning, meta-learning, hyperparameter optimization. The proposed method indeed outperforms other bilevel optimizers quite a lot, in particular when the network size is large as in the meta-learning experiments.

questions: This method uses the gradient descent for both the inner and outer updates. It would be good to know if the accelerated gradient methods such as Nesterov’s momentum can be used to further improve the convergence and complexity performance.  

The algorithm allows multiple random smoothing vectors, i.e., Q>1, which may be useful for reducing the estimation variance. I see that all experiments adopts the choice Q=1. Can the authors provide an explanation on why this choice is good? Furthermore, an experiment  on comparison of different Q should be provided.

Please add the units to x-axis of Figure 2(a), 2(b), and 2(c). For (a) and (b), the running time scales with 5, 10, 15, 20, but (c) scales with 0.5, 1, 1.5, 2. Please make the consistence accordingly.

limitations: authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

Meta-review: metareview: The paper introduces a Hessian-free bi-level optimizer called partial zeroth-order-like bilevel optimizer (PZOBO). PZOBO uses a zeroth-order-like Jacobian estimator, which provides accurate hypergradient estimates and a computationally effective way of solving bi-level optimization problems. The paper presents a thorough theoretical analysis and experimental validation on various bi-level problems.

Strengths:

1 - The authors address a relevant problem and provide an efficient and accurate solution.
2 - Convergence guarantees are provided for the proposed approach.
3 - Experimental results and comparisons with baselines over various bi-level problems. 
4 - PZOBO generally outperforms baseline methods, especially in high-dimensional problems.
5 - The main idea, to use zeroth approximations of the Jacobian of the solution mapping for the lower level problem with respect to the hyperparameters appears to be original and significant.

Weaknesses:

1 - One limitation is that there are many assumptions to apply. The assumptions are clearly stated which help alleviate this issue but the authors should address the limitations imposed by the assumptions in the numerical experiments because not made clear that the assumptions needed to apply the theorems are met. 

Decision:

Overall, all the reviewers vote for acceptance. This is a strong paper with very few limitations and with a significant contribution to the field. Because of this, I recommend acceptance. I encourage the authors to follow the reviewers' comments in order to improve the paper for the camera-ready version.


confidence: Certain
Decision: Accept