Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work presents an auto-differentiation library for gradient-based MLO. This work makes the following contributions:
1. This work develops an efficient automatic differentiation technique for LO based on a novel interpretation of MLO as a special type of dataflow graph. This technique can reduce the complexity of automatic differentiation from $O(d^3)$ to $O(d^2)$.
2. This work introduces a software library named BETTY to support large-scale MLO based on the technique mentioned in contribution 1. 
The authors demonstrate the effectiveness and stability of BETTY with hundreds of millions of parameters by performing MLO on the BERT-base model. 

strength_and_weaknesses: Strength:
1. The efficient automatic differentiation method is novel and effective. 
2. The proposed system BETTY is thoughtfully designed and clearly presented. It is a very meaningful contribution to facilitating efficient implementations of MLO programs. The authors also showcase the scalability of the proposed system to models with hundreds of millions of parameters by performing MLO on the BERT-base model. 
2. The system will be released open source. 
3. The background knowledge and math foundations are clearly presented. 
     
This is very impressive work to me. I do not see a major limitation of the proposed system.
clarity,_quality,_novelty_and_reproducibility: 1. The paper is overall well-written and clearly presented. 
2. The quality of this work is impressively high. 
3. I do not have concerns about reproducibility.
summary_of_the_review: This work proposes an automatic differentiation technique based on a novel interpretation of MLO as a special type of dataflow graph and then builds a software library for large-scale MLO based on the automatic differentiation technique. Both the automatic differentiation technique and the proposed system BETTY are very impressive contributions to facilitate further research and development on MLO. The paper is well-written and a pleasure to read.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The paper provides a representation for multilevel optimization problems, going beyond the more common bilevel optimization problems, as a dataflow graph. This graph contains two type of edges, representing 1) dependencies of higher-level optimal parameters on lower-level optimal parameters, and 2) dependencies of lower-level optimal parameters on higher-level non-optimal parameters. It can be used to efficiently compute best-response Jacobians and total gradients.
It then introduces a software library based on that principle, which enables user to express multi-level optimization problems in short programs, by defining each problem's cost function and solver configuration, and dependencies between problems.
Experiments showcase the computational (and memory) efficiency of the library, as well as its flexibility, on existing problems and variants.
strength_and_weaknesses: Strengths
-------------
1. Principled expansion of bilevel optimization (which enjoy increasing popularity) to a DAG of sub-problems, well described
2. Understandable and usable formalism to define such problems in practice in a framework
3. Several informative examples, demonstrating the range of capabilities of the framework
4. Comparison with (and exploration around) SOTA, demonstrating similar (or improved) results and efficiency.
5. Extensive appendix with details
6. Opensource code

Weaknesses
------------------
1. Clarity could be improved in some places, as it can be a difficult problem to grasp (see below)

clarity,_quality,_novelty_and_reproducibility: Clarity
---------
The paper reads well overall, and describes multi-level optimization and the approach taken in understandable terms.

Some things could be improved a bit, or clarified, in particular:
1. It would be nice to have diagrams similar to Fig. 2 for the actual examples, especially 5.3 / B.3
2. The direction of arrows / dependencies is not obvious to grasp, when they're presented as "dependencies". They may plausibly be "use -> definition" as well as "definition -> use"
3. "training_step" is a confusing name when what seems to be described is a cost function, rather than an update step.
4. How does it work when there is more than 1 top-level problem, as in 5.2 / B.2? Are both problems implicitly given a weight? It looks like there would usually be a trade-off.
5. It would probably help if indices i, j, k, l were used in a more consistent way (in which indices are upper vs. lower, for instance)

Quality
----------
The paper is convincing, the use cases described in the text (then in appendices) demonstrate simple examples (bilevel optimization) as well as non-trivial ones (5.3, where dependencies would otherwise form a cycle).
Experiments reproduce (or improve on) existing problems, showcasing the usefulness (and correctness) of the library.

Novelty
----------
To my knowledge, this is the first library that explicitly organizes dependencies in MLO in such a way, enabling to easily express MLO problems without explicitly redefining gradient expressions around solvers multiple times.

The factorization of best-response-Jacobian * vector products (Section 3.2) is similar to the usual factorization of Jacobian-vector products in forward-mode AD, so I don't think that part is really novel, but it's not presented as one major result, so that's OK.

Reproducibility
--------------------
The provided code and examples are great to help with reproducibilitiy of the concept, and specific experiments.
I have no doubt the results can be reproduced.

Other questions
----------------------
Definition 1 defines a "constrained" optimization problem, but that is quite different from other usual ways constraints can be defined in optimization problems, for instance equality and unequality constraints on the parameters.
I suppose equality constraints can be expressed explicitly with slack variables in BETTY (although it may be tedious to write, if there is no specific support), but what about inequality constraints? Are there any incompatibilities in the way problems are expressed? Could they be supported by a future version of the framework?

Minor & typos
1. On p.3, when defining $P_1$, should the last term of the argmin be $\mathcal D_1$ instead of $\mathcal D_k$? Or maybe $\emptyset$?
2. In B.2 (p. 15), both `Correct` and `Reweight` have exactly the same implementation for `training_step`, but the text and math in 5.2 (p.7-8) mention a different loss, $\mathcal L'_{val}$, "augmented with the classification loss of the correction network", which I don't see in the code listing.

summary_of_the_review: This paper introduces a well-motivated framework to express and solve multilevel optimization problems. The paper is quite clear, and the experiments are convincing regarding the correctness, ease-of-use, and efficiency of the implementation. Exploring the MLO space beyond bi-level (or even stacked) optimization problems is of interest to the community, and this frameworks seems to be the first in that domain, and may enable it.
I recommend to accept it.

**Update after response**
Thanks to the authors for their answers and for elaborating on the points raised. I still recommend acceptance, and maintain my rating.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed an automatic differentiation method for multilevel optimization (MLO) by a special dataflow graph. Specifically, by reverse-traversing the paths of the dataflow graph, the best-response Jacobians can be computed iteratively following the chain rule. This method can reduce the computational complexity of automatic differentiation from O(d^3) to O(d^2). Based on the proposed automatic differentiation method, this paper has introduced a software library that supports mixed-precision and data-parallel training. Finally, this paper demonstrated the library on several MLO applications and observed higher accuracy than baselines.
strength_and_weaknesses: Strength:
1. The paper is well written and the presentation is clear.
2. Applications of MLO in machine learning are very common hence studies of more efficient automatic differentiation methods are interesting.
3. The evaluations are performed on several commonly used scenarios. The empirical evidences for the validation of the proposed method is relatively strong.

Weaknesses:
1. The experiments are conducted for MLO with at most three-levels but the general method is applicable to MLO with more levels. Applications with at most three-levels might not demonstrate the full advantages of the proposed method.
2. The proposed method is specifically designed for deep learning based classification problems. It's unclear whether the proposed method is generally applicable for problems in domains outside machine learning.
3. More comparisons with existing software libraries should be considered other than the single default baseline in each application.
4. Experiments are mainly focused on the relatively simple CIFAR-10 benchmark.
clarity,_quality,_novelty_and_reproducibility: This paper is clearly written and the quality is good. The proposed method is valid and the novelty of this paper is relative good. The experiments in this paper is reproducible and the codes of the software will be made publicly available.
summary_of_the_review: The technique proposed in this paper is valid and show potentials to be applied in common MLO applications. However, the evaluations of the proposed method can be made more extensive by considering wider applications and more baseline methods. Also, it's good to show experimentally the improvement of computational efficiency over baseline methods.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes Betty, a library for automatic differentiation for
optimization. The authors describe the library and its design and evaluate it on
a number of problems, comparing to other approaches.
strength_and_weaknesses: + important problem
+ useful library that achieves good results
clarity,_quality,_novelty_and_reproducibility: The paper is clear, the proposed library novel, and results should be easily reproducible once the software is available.
summary_of_the_review: The paper is well written, the design of the proposed library makes sense and
allows for more efficient differentiation than other methods, and the
experimental results are convincing. This is a nice paper that should be
accepted.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Thank you for your submission to ICLR.  This paper presents a library and associated methodological approaches for multilevel optimization.  The paper is quite valuable as both a methodological contribution (understanding dataflow graphs better for the multilevel optimization setting), as well as from a software engineering standpoint, where the paper evaluates in detail the design methodology.  All the reviewers were in agreement about the strength of this paper, and thus I recommend it for acceptance.
justification_for_why_not_higher_score:  N/A.
justification_for_why_not_lower_score:  The oral recommendation for this paper is somewhat high for a "mostly" software-based paper, but in this case I think it's justified.  Both the technical developments and the showcasing of a usable and potentially very valuable software library makes this work likely to have a substantial impact.  I believe that there is quite a bit of value in highlighting these software efforts more to the broader ICLR community and thus (in addition to the well-received paper, as illustrated by the reviewer scores), I think this paper makes sense to present in this mode.
Decision: Accept: notable-top-5%