Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 

The paper propose two algorithms for solving bilevel optimization problem where the inner objective is assumed to be strongly convex. The main idea is to use an iterative scheme to approximate the inner level solution, and apply to chain rule to compute the upper level gradient à la back-propagation. Similar techniques is used on a stochastic version in case where the objective function are written as an expectation. The authors also provide a nice complexity analysis (under relatively restrictive but common assumptions) and numerical experiments which confirm an improvement upon some others previous methods eg (Ghadimi and Wang, 2018). The paper is reasonably well written.

I have only one concern on the novelty:

- the paper (Franceschi etal, 2017, 2018) computes hypergradient by backpropagation (the reverse-mode) as well and the actual paper does not clearly describe the relation with these works (while claiming efficiency superiority). More there is no comparisons, neither theoretical nor practical. Note that its iteration complexity was recently provided in ICML (Grazzi etal, 2020). It should be interesting that the authors precisely comment on the differences and add this competitor in the numerical experiments. Specially clarification on the differences (if any) between hypergradient formula would be helpful, as well as the time and space complexity of the proposed algorithms.

I am willing to raise my score after precise clarification of this point.

- Also, it would be interesting to provide an easy to use open source implementation for the conference venue and futur comparisons.

Typos:
"and and" on page 1.
"fist" on page 2.
review_title: The paper propose algorithm for solving bilevel opt. with gradient descent (computed with back-propagation). It provides a clear complexity analysis. However, its novelty wrt previously introduced hypergradient computation is a bit fuzzy to me.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents two algorithms - one for the deterministic and one for stochastic bilevel optimization. The paper claims the methods are lower cost in computational complexity for various terms and easy to implement. A finite-time convergence proof is provided for the algorithms.  Empirical results are presented for meta-learning, and (in the appendix) hyperparameter optimization.
 

Strengths:
 
The deterministic bilevel algorithm is easy to implement and has a convergence proof given standard assumptions.

The stochastic bilevel algorithm has a convergence proof given standard assumptions.

They investigate in-depth how the complexity of their algorithms scales with various terms (GC, Hxy, Hyy, etc) showing benefits on some.
 
 
Weaknesses:
 
The experiments presented in the paper are limited, and difficult to assess even after looking through the appendix.  What do the low-alpha parts of Figure 1 represent?  Why is CG used for the inverse with BA?  The algorithm you investigate (a Neumann Hessian inverse) was shown to work better in these kinds of problems by [1], [2], [3].

Algorithm 3 is not useful for practitioners to implement.  It seems like it does not use hessian-vector products, so I doubt the current incarnation would scale to any reasonably sized problem. See [1] or [2] for papers that provide memory-efficient Hessian Inverse estimators with the Neumann series and Hessian-vector products. Does Table 2 rely on storing the full Hessians in memory?  If so, this is infeasible in most applications and the complexity comparisons are not useful.
 
[1] Lorraine, Jonathan, Paul Vicol, and David Duvenaud. "Optimizing millions of hyperparameters by implicit differentiation." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
[2] Liao, Renjie, et al. "Reviving and improving recurrent back-propagation." arXiv preprint arXiv:1803.06396 (2018).
[3] Shaban, Amirreza, et al. "Truncated back-propagation for bilevel optimization." The 22nd International Conference on Artificial Intelligence and Statistics. 2019.
 
 
My recommendation is to reject this work with a 4. The paper presents convergence proofs for variants of two common algorithms in bi-level optimization. If a version of algorithm 3 that uses Hessian-vector products is presented with similar convergence results I would change my score to a 6.  I would also increase the score if (quite a bit) stronger experimental results are presented -- the meta-learning results seem mediocre and all hyperparameter results are similar and in the appendix.  I am very familiar with this area, however, I worry I may have misunderstood some notation about the implementation, so I will put my confidence as lower than otherwise until author feedback.
 
 
The following points did not affect my score, but may help improve the paper:
 
The level of formality in the writing seems different than other submissions to ICLR.  For example, saying “etc.” or “and/or” in the abstract.
 
I am not familiar with the term “order-level lower” complexity.
 
“Inlcude” to “include” and “trails” to “trials”
 
I think “hyperparameter” may be a more common spelling than “hyper-parameter.”
Also, “backpropagation” may be more common than “back-propagation”

Passing the paper through a grammar checker might help catch a few other simple grammar typos.
review_title: Reviewer 1

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes two novel algorithms, named deterBio and stocBio, for the nonconvex-strongly-convex bilevel optimization problems, and presents a comparison with several existing algorithms to demonstrate their superiority by experiments. Besides, propositions and theorems are well proved in the supplementary materials.
 
+ The idea of the proposal for reliable bilevel optimizers with better gradient complexities is meaningful.
+ The paper is well organized attached with sufficient supplementary materials for different propositions, and give analysis about the gradient complexities of proposed algorithms and related methods.
+ It gives a detailed description of the connection between conventional bilevel optimization and meta-learning problems and applications of respective fields.
 


Concerns: 
- Duplicate ‘and’ appears in the last line of the 1st Page.
- The involved batch size and parameters are significant and sensitive to different problems, and the comparison between stocBio and other algorithms maybe not enough, perhaps more analyses are recommended.
- Seems that the experiments are not enough to prove the flexible applications in relative deep learning fields, such as reinforcement learning.
review_title: This is a paper that maybe cannot meet the acceptance criteria.

final_score: rating: 3: Clear rejection
review_content: Overall, I vote for rejecting. While most of the related literature focuses on computing the hypergradient, this paper tackles the full optimization problem, which is much harder and more interesting. In particular I really like the idea of taking advantage of the (finite sum) structure of the bilevel optimization problem (algorithm 2). The problem tackled is very important but I have a lot of concerns regarding the novelty of the 'proposed' algorithm 1. Moreover I do not understand the focus on avoiding to compute the inverse of the Hessian, since in such application the Hessian is never inverted, only linear systems are solved, which is much cheaper. 

##########################################################################

Advantages of the paper:
- The paper is overall well written.
- The idea of algorithm 2 is elegant.

##########################################################################

Concerns 
1- Authors may have missed an important reference [1], which is a seminal paper on bilevel optimization for hyperparameter optimization.

2- Authors claim novelty on algorithm 1 'design a new bilevel optimization algorithm'. 
I may have missed something important, but it seems to me that algorithm 1 not new: it is exactly the algorithm in [1], Section 4.

3- Moreover how do the authors chose the stepsize of the gradient descent $\beta$? IMO this is a strong bottelneck in practice, that is why [2] uses LBFGS once the hypergradient is computed, and [3] uses a line-search procedure.
Do authors have heuristics to choose the stepsizes $\beta$ in practice?
This is paramount in practice, and the value of the stepsize is hidden in appendix, set to '0.001'. This seems very custom, and not general. How do authors know that the proposed algorithms converged for this choice of stepsize?

4- 'proposition shows that the differentiation involves computations of second order derivatives'
I do not understand. To my knowledge, the hypergradient $\partial f$ can be computed in 3 differents ways: implicit[3], forward or backward [4].
To my knowledge there is not Hessian inversion, neither in the implicit nor in the backward: algorithm 1 in [3] solves a linear system to compute the gradient, and no Hessian are inverted in [1], Section 4. 
I am very confused with this Hessian inversion problem. Since I did not understand it, I lost a lot of the motivation for the introduction of algorithm 2.

5- At the beginning of section 2.1 it seems that the end of an old sentence remains in the text.

6- Part 4 is very technical and felt to me like an arid succession of theoretical results. IMO more insights and comments on the theoretical results would be very helpful for the reader.

7- Part 5 proposes experiments using algorithm 1, which is already known (unless I missed something). Experiments on algorithm 2 are only in appendix.
A comparison with  the approximated procedure of [3] would strength the paper: from my experience, approximated gradient like in [3] drastically improves the convergence time.


[1]  Domke, J. Generic methods for optimization-based modeling, AISTAST 2012
[2] Deledalle, C. A., Vaiter, S., Fadili, J., & Peyré, G. (2014). Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection. SIAM Journal on Imaging Sciences
[3] Pedregosa, F. (2016). Hyperparameter optimization with approximate gradient, ICML2016
[4] Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017). Forward and reverse gradient-based hyperparameter optimization. ICML2017
review_title: The paper proposes two algorithms to solve bilevel optimization problems, with applications to hyperparameter optimization and meta-learning.

Meta-review: The authors propose two algorithms and their theoretical analysis for solving bilevel optimization problems where the inner objective is assumed to be strongly convex. The authors have greatly improved the paper to answer reviewer comments and three out of four reviewers have increased their scores. That said, given the large amount of new material added to this paper during the discussion phase, the program committee believes the paper requires a new round of reviews for a confident assessment. We encourage the authors to resubmit their work to a top conference such as ICML.
Decision: Reject