Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduce two new algorithms to tackle bi-level optimisation, which has wide-ranging application in machine learning.
Crucially, these two algorithms forego second order gradient computation completely, favoring instead an evolution strategies approach. 
While this approach has been proposed before in this context, the new algorithms are more efficient because they do not treat the whole problem as a black box, and leverage the structure of the hypergradient.
Theoretical convergence analyses are then provided for both the full gradient and the stochastic gradient alternatives, as well as experiments on various bi-level optimisation problems, showcasing improved performance over previous approaches.
main_review: This paper tackles a very relevant problem. to the machine learning community. It introduces two interesting new algorithms, executing on a simple but elegant idea, which is to limit the black box to its bare minimum, and leverage whatever problem structure of the hypergradient possible.
The writing is clear and enjoyable to read, and the problem is well motivated.

A number of significant issues remain, however.
1. The paper references deep neural networks many times, but crucially relies on the objective being strongly convex with respect to y, which if I understand correctly are the parameters of the model. Deep learning optimisation landscapes are notoriously not even convex, let alone strongly convex. If y is actually only the final layer of a neural network, this needs to be explained right from the start to put the exposition in context. Further, this doesn't seem compatible with the claim that all the 12M resnet12 parameters are learned in the experiment. Some clarity there would go a long way.

2. There are some overclaims, notable regarding 'large' neural networks,  when only fairly small ones are used in the experiments (that is in itself not an issue; claiming that they are large scale when they are not is a problem though).

3. Another overclaim is that the proposed algorithms are 'efficient'. Only requiring gradient computation does not make an algorithm efficient, particularly when it requires NQ *full* gradient steps per outer step. A comprehensive cost analysis with AID and ITD which use second-order information is necessary here, to see when N and Q become too big for this approach to yield gains.

4. The theoretical results, while interesting, are not properly put into context. First, the upper bounds contain a massive additive constant, which isn't smaller than any epsilon. So the results are only valid when this constant is smaller than epsilon, which should be made clear. Second, the settings needed to make the constant small are drastic, meaning Q needs to be in p/epsilon, which if p is the amount of weights of a neural network means using incredibly big Qs, and in turn massive amounts of full gradient steps.
No context is given here on the limitations of the theoretical results, which appear to be all but unusable from a practical perspective.

On a related note, in proposition 3 we need at least some context on how big the constants are.

5.  The experiments are all using small scale neural networks, so claiming that the approach succeeds on large neural nets is misleading.
Finally, there seems to be a discrepancy between the analysis on strongly convex objectives, and the experiments using non-strongly convex objectives.

Question: is it necessary to use the same batch sampling path for every mu? Has this been ablated?

All told, this paper introduces promising new ideas, but at this stage the execution is a bit lacking.  At this stage I do not recommend it for publication at ICLR, but I encourage the authors to take this feedback to heart and improve the paper so that it can have all the more impact on the community.
summary_of_the_review: Interesting new methods to tackle a very relevant problem.
Unfortunately a few too many issues remain in the presentation of the paper to make it ready for publication this time around, but it absolutely can be with a bit of additional work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work mainly focuses on proposing a computational efficient for approximating the response Jacobian matrix in the hypergradient of bilevel optimization with only first-order information of the loss functions. The proposed methods are applicable for developing both deterministic and stochastic bilevel optimization algorithms. The author further show the convergence guarantees and computational complexity of the proposed algorithms. Multiple numerical results showcase the efficiency of the proposed method in applications of machine learning.
main_review: The paper is generally well written. The core part of this work is the ES Jacobian algorithm, which is specialized in solving bilevel optimization problems. The assumptions made for analyzing the bilevel algorithms are standard, where the main theoretical contributions are Prop.1 and 2 that serve as the pillars of showing the convergence of the bilevel algorithms. I found that method is novel and interesting, but still, have the following concerns regarding the contribution and technical correctness of this work:

1) The proposed ES algorithm is quite similar to the zeroth-order methods. What are the unique differences here? Comparing the first-order and zeroth-order methods, the theoretically guaranteed convergence rate of the zeroth-order ones is slower than the first-order algorithm with a dependency of problem dimension in general. Here, the authors try to argue that the proposed ES is computationally efficient of using the black-box type of methods, which contradicts the common intuition that ES would be slower w.r.t. rate. Please justify.

2) The proposed algorithm is basically a double loop one, since $N$ is a function of $\epsilon$. This again contradicts the intuition that single loop algorithms would be more efficient. To my understanding, the current algorithm cannot be improved as a single loop one.

3) Regarding the convergence rate results, can authors compare the obtained one with existing works, e.g., single- or two-timescale bilevel algorithms? my understanding is that the proposed one for both the deterministic and stochastic cases needs more iterations resulting in higher sample complexity.

4) The required step sizes for the ESJ-S are a little wired. Why do $\alpha,\beta$ be constants? I think the step sizes are either decreasing sequences or depending on $\epsilon$. Please justify.

5) In section 4.3, why not consider MAML and ANIL as baselines?  Also, it seems that all the compared methods have not been converged yet during the training.  Also, it would be great that more statistical measures can be reported such as variance.



summary_of_the_review: Overall, I believe that it is an interesting work, but the proposed is only applicable for solving a class of problems given a special structure of hypergradient. Even the authors justify the computational efficiency of the proposed algorithm numerically w.r.t. running time, the theoretical justification of the efficiency of the iteration and sample complexities should be further addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims to reduce the computational cost in solving a bilevel problem. In bilevel optimization, the outer gradient can be decomposed into direct and indirect gradients. The indirect gradient requires computing the response Jacobian, which involves computing & inverting the Hessian and computing mixed derivative. To avoid expensive second-order approximations, the authors propose to use the evolution strategies (ES) based method to approximate the response Jacobian. The authors provide the convergence guarantee of the algorithm and empirically demonstrate that the proposed algorithm performs well on large-scale bilevel problems. 
main_review: Pros:
* The idea of using ES based method to approximate the response Jacobian matrix is interesting.
* Overall, the paper is easy to follow. In particular, the main contribution section makes it easier to highlight the important contribution made in the paper and the related work is written well and makes the algorithm well motivated. 

Concerns:
* I believe that the paper misses several important related works. There have been earlier works on using ES-based methods for bilevel optimization (e.g. [1]) that share a similar idea of approximating the Jacobian of the response function. Moreover, STNs ([2], [3]) use the ES gradient approximation method to approximate the response function (or response Jacobian) in an amortized manner. I believe that these should be discussed in the related work section and contribution section of the paper, and should be compared against in the experiment section since the core idea is very similar. 
* The key concern about the paper is the lack of rigorous experimentation to show that the proposed method is superior to other bilevel optimization approaches. The paper majorly focuses on the hyper-representation experiments and compares the proposed method to only three baselines (e.g. HOZOG, AID-CG, AID-FP). I believe that the paper should experiment with the algorithm in more diverse settings (e.g. hyperparameter optimization) and compare it to other gradient-based methods (e.g. [2], [3], [5] and various ITD based methods). At the moment, I am not convinced that the proposed algorithm is superior to other bilevel optimizers (both in terms of accuracy and computation it required).
* In the first experiment, the authors do not properly explain why there is an improvement in the outer data accuracy. Does this mean that the proposed method approximates the response Jacobian more accurately than CG? 
* What are additional hyperparameters introduced by ESJ-S? I believe that they are Q (number of Gaussian samples) and N. It would be good to have an ablation study of how Q affects the quality of the algorithm. 
* In the first experiment, the authors mention that they follow the same experimental procedure as [4], but I couldn’t find the paper. I believe that there are typos in the reference. 
* Some mathematical notations are not properly defined throughout the paper and make the paper hard to follow in terms of the notation. For example, in Algorithm 1, the authors did not define variables such as K, N, and Q.

Some minor comments: 
* In section “related work”, the paragraph header “Bilevel optimization” is missing “.” at the end.
* In algorithm 1, it would be helpful to identify variables such as K, Q
* In section 3.2, “Differently from …” → “Different from …”
* I believe that some information in the Appendix is outdated. For example, in Appendix B, the authors say “paper demonstrates the superior performance of the proposed ES-based bilevel optimizer in meta-learning and hyperparameter optimization”. However, there was no experiment on hyperparameter optimization.

[1] Sinha, Ankur, Pekka Malo, and Kalyanmoy Deb. "An improved bilevel evolutionary algorithm based on quadratic approximations." 2014 IEEE congress on evolutionary computation (CEC). IEEE, 2014.

[2] MacKay, Matthew, et al. "Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions." arXiv preprint arXiv:1903.03088 (2019).

[3] Bae, Juhan, and Roger Grosse. "Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians." arXiv preprint arXiv:2010.13514 (2020).

[4] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Machine Learning (ICML)), 2020.

[5] Pedregosa, Fabian. "Hyperparameter optimization with approximate gradient." International conference on machine learning. PMLR, 2016.
summary_of_the_review: The paper is easy to follow and I believe that the contents of the paper are technically correct. However, the paper doesn't discuss several important related works and the empirical analysis is not rigorous: the authors conduct the empirical investigation in a limited setting and don't compare the proposed method with competitive baselines. It is still unclear if the proposed algorithm is superior to the previous approaches. I believe that there should more in-depth empirical analysis to make the proposed method more convincing.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the evolution strategies (ES) based method to estimate the Jacobian matrix used in bilevel optimization. The main idea is to use first-order information to estimate the second-order information in the Jacobian matrix. Some convergence results have been provided, companied with some simulations. 
main_review: **Things I like**: The paper proposes an alternative approach to bypass the need of computing the costly second-order information in bilevel optimization and provides theoretical guarantees for the proposed algorithms. The problem is important, and the algorithms are well-motivated.

**Things can be improved**:

**Limited technical novelty**: While this paper uses ES in a more careful manner in the bilevel optimization, it should be noted that the idea of using ES mainly follows from [Gu et al 2021] and the convergence analysis of the bilevel part mainly follows from [Ji et al 2021]. 

Specifically, compared with [Gu et al 2021], the proposed algorithm only uses ES on Jacobian in (3) not the entire bilevel gradient. On the theoretical side, it is known in optimization literature that applying an ES method will only introduce a small bias that is proportional to \mu, and the remaining of the analysis follows directly from the bilevel optimization [Ji et al 2021]. Also see a couple of earlier and important works such as

[1] Ghadimi, S. and Lan, G., 2013. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4), pp.2341-2368.

Building upon previous results in bilevel optimization and ES, the theoretical contribution of this work amounts to establish the estimation error of the proposed gradient estimator, which looks not as impressive as claimed in the introduction. 

**High actual complexity**: While the goal is to reduce the complexity of bilevel optimization, the proposed algorithm still incurs large computation overhead. By carefully looking at Theorems 1 and 2, to guarantee convergence, the theory requires the number of queries Q and the batch size S to grow with $\epsilon^-1$, which makes the theory less favorable to practitioners. Such high complexity seems to be hidden in the simulations by choosing small Q and S, which makes the comparison with baselines less convincing. 

**Limited empirical verification**: One should provide a thorough empirical studies on the proposed algorithms and the existing ones. However, most of experiments are carried out on simple problems with small networks. And the running time (in second, minute, or hour) is not clearly marked. I have several questions:

i) The baselines on MNIST only get a test accuracy of 93, which is too small. Have the authors tuned the parameters well? To my knowledge, it is not hard to achieve 97 or 98 test accuracies on reasonable networks.

ii) It looks like that the authors do not scale up the learning rate with e.g., 0.1, after several epochs. This learning rate trick is useful in practice, and some algorithm benefits significantly from this trick. 

iii) ResNet12 is not big enough to justify the claim on scalability. 

As a matter of fact, only a subset of experiments of [Gu et al 2021] has been tested with ESJ using synthetic data in this paper. This seems implausible to claim its practical advantage to HOZOG [Gu et al 2021]. 

summary_of_the_review: Overall, first-order bilevel optimization is a worthy direction to pursue, but efforts on both technical and empirical novelty are needed to make this paper competitive.
review_title: null

Meta-review: This paper presents an algorithm for approximating the hypergradient for bilevel optimization using a trick based on evolution strategies. It seems like an interesting approach, somewhat reminiscent of STNs, so it's interesting to see experiments with it.

I have a big concern about the proposed justification of the method, namely that each iteration is more efficient than methods based on HVPs. The authors claim that because they only require gradient computations and not HVPs, their method is more efficient. However, as various reviewers point out, the proposed method requires numerous inner optimization runs. By comparison, a method based on unrolled backprop simply requires a single inner run, followed by backprop on the trajectory; hence it should be about as expensive as 2-3 inner optimizations (or less if it is truncated BPTT). Similarly, each HVP has a small multiple of the cost of an inner optimization step, so methods based on HVPs ought to be cheaper unless they're doing quite a lot of HVPs.

It's conceivable the proposed method could be more efficient than AID, etc. if each hypergradient estimate is more accurate. However, this isn't shown, and it would seem surprising for an ES-based approximation to be more accurate than the exact gradient.

The authors claim in the rebuttal that the efficiency claims aren't based on the theoretical analysis, but rather on the experiments (which use Q=1); however, Section 3.2 still finishes with the conclusion that ESJ is more efficient, which seems problematic.

I encourage the authors to formulate their theoretical claims more carefully and to consider the reviewers' other feedback, and I think this could make an interesting submission for the next cycle.
Decision: Reject