Betty: An Automatic Differentiation Library for Multilevel Optimization
Authors: Sang Keun Choe
Willie Neiswanger
Pengtao Xie
Eric Xing
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Multilevel Optimization
Automatic Differentiation
Bilevel Optimization
Meta Learning
Software Library

Abstract: Gradient-based multilevel optimization (MLO) has gained attention as a framework for studying numerous problems, ranging from hyperparameter optimization and meta-learning to neural architecture search and reinforcement learning. However, gradients in MLO, which are obtained by composing best-response Jacobians via the chain rule, are notoriously difficult to implement and memory/compute intensive. We take an initial step towards closing this gap by introducing Betty, a software library for large-scale MLO. At its core, we devise a novel dataflow graph for MLO, which allows us to (1) develop efficient automatic differentiation for MLO that reduces the computational complexity from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$, (2) incorporate systems support such as mixed-precision and data-parallel training for scalability, and (3) facilitate implementation of MLO programs of arbitrary complexity while allowing a modular interface for diverse algorithmic and systems design choices. We empirically demonstrate that Betty can be used to implement an array of MLO programs, while also observing up to 11% increase in test accuracy, 14% decrease in GPU memory usage, and 20% decrease in training wall time over existing implementations on multiple benchmarks. We also showcase that Betty enables scaling MLO to models with hundreds of millions of parameters. We open-source the code at https://github.com/leopard-ai/betty.

Published as a conference paper at ICLR 2023
BETTY: AN AUTOMATIC DIFFERENTIATION LIBRARY FOR MULTILEVEL OPTIMIZATION
Sang Keun Choe'
Willie Neiswanger?
Pengtao X
Eric Xing
Cammeiie Mellon University
Stanford University
UCSD 'MBZUAI
'Equal contribution
(sangkeuc, epxing) ccs cmu. edu, wwwpaangeeeessssaaoooooooee edu, plxie@ucsd. edu
ABSTRACT
Gradient-basee multilevel optimization (MLO) has gained attention as a framework for studying numerous problems, ranging from hyperparameter optimization and meta-learning to neural architecture search and reinforcement learning. However, gradients in MLO, which are obtained by composing best-response Jacobians via the chain rule, are notoriously difficult to implement and memory/compute intensive. We take initial step towards closing this gap by introducing BETTY, a software library for large-scale MLO. At its core, we devise a novel dataflow graph for MLO, which allows to (1) develop efficient automatic differentiation for MLO that reduces the computational complexity from (dd) to Odd)), (2) incorporate systems support such as mixed-precision and data-parallel training for scalability, and (3) facilitate implementation of MLO programs of arbitrary complexity while allowing modular interface for diverse algorithmic and systems design choices. We empirically demonstrate that BETTY can be used to implement an array of MLO programs, while also observing up 11% increase in test accuracy, 14% decrease in GPU memory usage, and 20% decrease in training wall time over existing implementations on multiple benchmarks. We also showcase that BETTY enables scaling MLO to models with hundreds of millions of parameters. We open-source the code at https: : //gittuuuatt/ www.coo////////o aeoparddddd---e ai/ //btty.
INTRODUCTION
Multilevel optimization (MLO) addresses nested optimization scenarios, where upper level opti- mization problems are constrained by lower level optimization problems following an underlying hierarchical dependency. MLO has gained considerable attention as unified mathematical framework for studying diverse problems including meta-learning (Finn et al., 2017; Rajeswaran al., 2019), hyperparameter optimization (Franceschi et al., 2017), neural architecture search (Liu et al., 2019), and reinforcement learning (Konda & Tsitsiklis, 1999; Rajeswaran al., 2020). While majority of existing work is built upon bilevel optimization. the simplest case of MLO, there have been recent efforts that go beyond this two-level hierarchy. For example, (Raghu al., 2021) proposed trilevel optimization that combines hyperparameter optimization with two-level pretraining and finetuning. More generally, conducting joint optimization over machine learning pipelines consisting of multiple models and hyperparameter sets can be approached as deeper instances of MLO (Garg et al., 2022; Raghu et al., 2021: Somayajula et al., 2022; Such et al., 2020).
Following its increasing popularity, multitude of optimization algorithms have been proposed to solve MLO. Among them. gradient-based (or first-order) approaches (Pearlmutter & Siskind, 2008; Lorraine et al., 2020; Raghu et al., 2021; Sato et al., 2021) have recently received the limelight from the machine learning community, due to their ability to carry out efficient high-dimensional optimization, under which all of the above listed applications fall. Nevertheless, research in gradient- based MLO has been largely impeded by two major bottlenecks. First, implementing gradients in multilevel optimization, which is achieved by composing best-response Jacobians via the chain rule, requires both programming and mathematical proficiency. Second, algorithms for best-response Jacobian calculation, such iterative differentiation (ITD) approximate implicit differentiation (AID) (Grazzi et al., 2020), are memory and compute intensive, as they require multiple forward/back- ward computations and oftentimes second-order gradient (i.e. Hessian) information.

---

Published as a conference paper at ICLR 2023
lower
Problem
Beat-response Jacobian
upper prob.
dlsta loader
6054
ITD-RMAD
AID-FD
lower prof.
optimbeer
module
AID -MNN
ADD
Probtem
Step
Systems Support
gred cali.
Problem
Problem
grad
Figure 1: In Engine (left), users define their MLO program a hierarchy/graph of optimization problems. In Problem (middle), users define an optimization problem with a data loader, cost function, module, and optimizer, while upper/llowr level constraint problems (i.e. Us Lx) are injected by Engine. The "step" function Probl I em serves as the base of gradient- based optimization, abstracting the one-step gradient descent update process. Finally, users can easily try out different best-response Jacobian algorithms & system features (right) via Con ig in modular manner.
In recent years, there has been some work originating in the meta-learning community on developing software libraries that target some aspects of gradient-based MLO (Blondel et al., 2021; Deleu et al., 2019; Grefenstette et al., 1).. For example, JAXop! (Blondel et al., 2021) provides efficient and modular implementations of AID algorithms by letting the user define a function capturing the optimality conditions of the problem to be differentiated. However, JAXopt fails to combine the chain rule with AID support general MLO programs beyond two-level hierarchy. Similarly, higher (Grefenstette et al., 2019) provides several basic primitives (e.g. making PyTorch's (Paszke al., 2019) native optimizers differentiable) for implementing ITD/AID algorithms, but users still need to manually implement complicated internal mechanisms of these algorithms as well as the chain rule implement given instance of MLO. Furthermore, most existing libraries do not have systems support, such as mixed-precision precision and data-pan parallel training, that could mitigate memory and computation bottlenecks. As a result, gradient-bass based MLO research built upon these libraries has been largely limited to simple bilevel optimization and small-scale setups.
In this paper, we attempt to bridge this gap between research and software systems by introducing BETTY, an easy-to-use and modular automatic differentiation library with various systems support for scale MLO. The main contributions of this paper are as follows:
1. We develop an efficient automatic differentiation technique for MLO based on novel interpreta- tion of MLO as special type of dataflow graph (Section 3). In detail, gradient calculation for each optimization problem automatically carried out by iteratively multiplying best-response Jacobians (defined in Section 2) through the chain rule while reverse-travers this dataflow graph. This reverse-traversing procedure is crucial for efficiency, as it reduces the computational complexity of our automatic differentiation technique from (dd) to Odd)), where is the dimension of the largest optimization problem in the MLO program.
specific paths of
We introduce a software library for MLO, BETTY, built upon the above automatic differentiation technique. Our software design (Section 4), motivated by the dataflow graph interpretation, provides two major benefits: (1) it allows for incorporating various systems support, such as mixed- precision and data-paralle training, for large-scale MLO, and (2) it facilitates implementation of MLO programs of arbitrary complexity while allowing a modular interface for diverse algorithmic and systems design choices. The overall software architecture of BETTY is presented in Figure 1.
We empirically demonstrate that BETTY can be used to implement an array of MI.O applications with varying scales and complexities (Section 5). Interestingly, we observe that trying out different best-response Jacobian algorithms with our modular interface (which only requires changing one line of code) can lead to up 1 11% increase in test accuracy, 14% decrease in GPU memory usage, and 20% decrease in training wall time on various benchmarks, compared with the original papers' implementations. Finally, of millions of parameters by performing MLO on the BERT-base model with the help of BETtY's systems support, which was otherwise infeasible.
showcase the scalability of BETTY to models with hundreds
2

---

Published as a conference paper at ICLR 2023
2 BACKGROUND: GRADIENT-BASED MULTILEVEL OPTIMIZATION
To introduce MI.0, we first define an important concept known as "constrained problem" (Vicente & Calamai, 1994).
Definition 1. An optimization problem P is said be constrained by À when its cost function C has À argument in addition to the optimization parameter 0 (i.e. P arg ming C(O, ).)))
Multilevel optimization (Migdalas al., 1998) refers field of study that aims solve nested set of optimization problems defined on a sequence of so-called levels, which satisfy two main criteria: A1) upper-level problems constrained by the optimal parameters of lower-level problems while A2) lower-level problems are constrained by the nonoptimal parameters of upper-level problems. Formally, an n-level MLO program can be written as: 0 = argmin C. (0n,,un, Lni D,))
Pa
D Level problem
0n
Pk
s.t. 0% argmin (0 Lz; Dk)
Level A: E (2...., 1} problem
P.
Pi
s.t. 07 = argmin (1 D- Level problem
0, where, Pa stands for the level & problem, 02/ 0% for corresponding nonoptimal optimal parameters,
and U4 / Cc for the sets of constraining parameters from upper/ / lower level problems. Here, D3 is the training dataset, and C₁ indicates the cost function. Due to criteria A1 & A2, constraining parameters from upper-level problems should be nonoptimal (i.e. Us S [6x+1, 1..+1.... parameters from lower-level problems should be optimal (i.e. Ls (0r.... , denote only one optimization problem per level in the above formulation, each level could in fact have multiple problems. Therefore, henceforth discard the concept of level, and rather assume that problems [P1, P2.... Pa of general MLO program are topologically sorted in a "reverse" order (i.e. P, / P1 denote uppermost lowermost problems).
(n.) while constraining
---11)
}). Although
For example, in hyperparameter optimization formulated as bilevel optimization, hyperparameters and network parameters (weights) correspond to upper and lower level parameters (02 and 02). Train / validation losses correspond to C1 C2, and validation loss is dependent on optimal network parameters 0 obtained given 22. Thus, constraining sets for each level are L41 {02) and L2 {8t)-
In this paper, we focus in particular on gradient-batt based MLO, rather than zeroth-order methods like Bayesian optimization (Cui Bai, 2019), in order to efficiently scale to high-dimensional problems. Essentially, wradient-based based MIO calculates gradients of the cost function (OR. 2r. Lx) with respect to the corresponding parameter lz. with which gradient descent is performed to solve for optimal parameters 0% for every problem Pt. Since optimal parameters from lower level problems (i.e. dC'
or L&) can be functions of Og (criterion A2), dee
be expanded using the chain rule follows:
dC+
OC₁
d0i dBk
aCk T
Σ
X
d0,
o, EC
direct gradient
best best-response Jacobian
direct gradient
While calculating direct gradients (purple) is straightforward with existing automatic differentiation engines like Py Torch (Paszke et al., 2019), major difficulty in gradient-basee MLO lies in best- response Jacobian' (orange) calculation, which will be discussed in depth in Section Once gradient calculation for each level & is enabled via Equation (1), gradient-based optimization is executed from lower to upper level problems in a topologically reverse order, reflecting underlying hierarchies.
AUTOMATIC DIFFERENTIATION FOR MULTILEVEL OPTIMIZATION
While Equation (1) serves mathematical basis for gradient-basel based multilevel optimization, how to automatically and efficiently carry out such gradient calculation has not been extensively studied
We abuse the Jacobian for total derivative here while is originally matrix of partial derivatives
3

---

Published as a conference paper at ICLR 2023
and incorporated into software system that can support MLO programs involving many problems with complex dependencies. In this section, we discuss the challenges in building an automatic differentiation library for MLO, and provide solutions to address these challenges.
3.1 DATAFLOW GRAPH FOR MULTILEVEL OPTIMIZATION
One may observe that the best-response Jacobian term in Equation (1) is expressed with a total derivative instead of partial derivative. This is because O2 can affect Of not only through direct interaction, but also through multiple indirect interactions via other lower-level optimal parameters. For example, consider the four-problen, MLO program illustrated Figure 2. Here, the parameter of Problem 4 (0p,) affects the optimal parameter of Problem 3 (0 in two different ways: 1) 8p. + 0%
and 2) 8pp + p. + ps- In general, we can expand the best-response Jacobian
dei in Equation (1) 2bg
by applying the chain rule for all paths from 02 to 07 as
dC* UCk
Σ E B7EC. nEDui
00*
o(1)
x
len(y)- -1
II
00 g(++1)
x
OC 209
(2)
d0,
00,
00p
00
2(3)
upper-to-lower
lower-to-upper
where Qa, is a set of paths from 03 to Of and g(i) refers to the index of the i-th problem in the path with the last point being 0j. Replacing total derivative term in Equation (1) with a product of partial derivative terms using the chain rule allows us to ignore indirect interactions between problems, and only deal with direct interactions.
To formalize the path finding problem, we develop a novel dataflow graph for MLO. Unlike traditional dataflow graphs with no predefined hierarchy among nodes, dataflow graph for multilevel optimization has two different types of directed edges stemming from criteria A1 & A2: lower-to-upper and upper-to-lower. Each of these directed edges is respectively depicted with green and red arrows in Figure Essentially, lower-to-upper upper edge represents the directed dependency between two optimal parameters (i.e. 0%, - 8p, with P. < Pý), while an upper-to- lower edge represents the directed dependency between nonoptimal and optimal parameters (i.e. 0p. 8%, with P. > Pj). Since need to find paths from the nonoptimal parameter 02 to the optimal parameter 0r, the first directed edge must be an upper-to-lower edge (red), which connects 0g to some lower-level optimal parameter. Once it reaches the optimal parameter, it can only move through optimal parameters via lower-to-upper edges (green) in the dataflow graph. Therefore, every valid path from 0g to 07 will start with an upper-to-lows edge, and then reach the destination only via lower-to-upper edges. The best-response Jacobian term for each edge the dataflow graph is also marked with the corresponding color in Equation (2). We implement the above path finding mechanism with a modified Septh-first search algorithm in BETTY.
Op.
Opy
Figure 2: An example dataflow graph for MLO.
3.2 GRADIENT CALCULATION WITH DEST-RESPONSE JACOBIANS
Automatic differentiation for MLO can be realized by calculating Equation (2) for each problem Pa (k 1. n)). However, naive calculation of Equation (2) could be computationally onerous as involves multiple matrix multiplications with best-response Jacobians, of which computational complexity is Odd)), where d is the dimension of the largest optimization problem in the MIO program. To alleviate this issue, we observe that the rightmost term in Equation (2) is a vector, which allows us reduce the computational complexity of Equation (2) (dd) by iteratively performing matrix-vector multiplication from right to left (or, cquivalently, reverse-traversing a path in the dataflow graph). As such, matrix-vector multiplication between the best-response Jacobian and vector serves as a base operation of efficient automatic differentiation for MLO. Mathematically, this problem can be simply written as follows:
Ow (A)
Calculate
(3)
ax
Given w" (A) argmin C(w, A).
(4)
4

---

Published as a conference paper at ICLR 2023
Two major challenges in the above problems are: 1) approximating the solution of the optimization problem (i.e. w" (A)), and 2) differentiating through the (approximated) solution.
In practice, an approximation of w" (A) is typically achieved by unrolling a small number of gradient steps, which can significantly reduce the computational cost (Franceschi et al., 2017). While we could potentially obtain a better approximation of w" (*()) by running gradient steps until convergence, this procedure alone can take a few days (or even weeks) when the underlying optimization problem
large-scale (Deng et al., 2009; Devlin al., 2018).
Once w" (A) is approximated. matrix- vector multiplication between the best-response Jacobian die (X) and vector is popularly obtained by either iterative differentiation (TTD) approximate implicit differentiation (AID) (Grazzi et al., 2020). This problem has been extensively studied in bilevel optimization literature (Finn et al., 2017; Franceschi al., 2017; Lorraine et al., 2020), and direct interested readers to the original papers, as studying these algorithms is not the focus of this paper. In BETTY, we provide implementations of several popular ITD/AII algorithms which users can easily plug-and-play for their MI.0 applications. Currently available algorithms within BETTY include ITD) with reverse-mode automatic differentiation ((TD-RMAD) (Finn et al., 2017), AID with Neumann series (AID-NMN) (Lorraine et al., 2020), AID with conjugate gradient (AID-CG) (Rajeswaran et al., 2019), and AID with finite difference (AID-FD) (Liu al., 2019).
dx
3.3 EXECUTION OF MULTILEVEL. OPTIMIZATION
In MLO, optimization of each problem should be performed in topologically reverse order, as the upper-level optimization is constrained by the result of lower-level optimization. To ease an MLO implementation, we also automate such an execution order with the dataflow graph developed in Section 3.1. Specifically, let's assume that there is lower-to-upper edge between problems P; and Pj (i.e. 0- - 87). When the optimization process (i.e. a small number of gradient steps) of the problem P; is complete, can call the problem Pj to start its one-step gradient descent update through the lower-to-upper edge. The problem P3 waits until all lower level problems in Lj send their calls, and then performs the one-step gradient descent update when all the calls from lower levels are received. Hence, to achieve the full execution of gradient-based MLO, we only need to call the one-step gradient descent processes of the lowermost problems, as the optimization processes of upper problems will be automatically called from lower problems via lower-to-upper edges.
To summarize, automatic differentiation for MLO is accomplished by performing gradient updates of multiple optimization problems in topologically reverse order based on the lower-to-upper edges (Sec. 3.3), where gradients for each problem are calculated by iteratively multiplying best-response Jacobians obtained with ITD/AID (Sec. 3.2) while reverse-traversing the dataflow graph (Sec. l).
4 SOFTWARE DESIGN
On top of the automatic differentiation technique developed in Section 3, we build an easy-to-use and modular software library, BETTY, with various systems support for large-scale gradient- based MLO. In detail, we break down MLO into two high-level concepts, namely 1) optimization problems and 2) hierarchical dependencies among problems, and design abstract Python classes for both of them. Such abstraction is also motivated by our dataflow graph interpretation, as each of these concepts respectively corresponds to nodes and edges. The architecture of BETTY is shown in Figure
Problem Each optimization problem Ps: in MLO is defined by the parameter (or module) 6g. the sets of the upper and lower constraining problems Us & Lx. the dataset Dx. the cost function Cr. the optimizer, and other optimization configurations (e.g best-response Jacobian calculation algorithm, number of unrolling steps). The Probl em class is an interface where users can provide each of the aforementioned components to define the optimization problem. In detail, each one except for the cost function C₂ and the constraining problems Us & Cs can be provided through the class constructor, while the cost function can be defined through "training step" method and the constraining problems are automatically provided by Engine.
Abstracting an optimization problem by encapsulating module, optimizer, and data loader together additionally allows us to implement various systems support, including mixed precissonn data aatallarallll training. and gradient accumulation, within the abstract P Probl em class. A similar strategy has also
5

---

Published as a conference paper at ICLR 2023
been adopted in popular frameworks for large-scale deep learning such as DeepSpeed (Rajbhandari et al., 2020). Since implementations of such systems support as well as best-response Jacobian are abstracted away, users easily plug-and-pla different algorithmic and systems design choices, such as unrolling steps or mixed-precision training, via Confi in modular fashion. An example usage of P Proble is shown in Listing 1, and full list of supported features in Config g is provided in Appendix F.
Xysrablem (Problem
def training stop (self, batca):
# Jaera define the cost funcsion
selurn coat_fn self.module, self selI.othe:_protee ...)
config (type"" unroll_steps=ib, fpi6-1rue, MyProblem ("myoroblen", Myy2coblemttmyyrrbbeer
prob
contig, nodule, ogtimizer, data_loader!
Listing Problem class example.
Engine While Problem manages each optimization problem, Engine handles hicrarchical dependencies among problems in the dataflow graph. As discussed in Section 3.1, datallow graph for MLO has upper-to-lower and lower-to-upper upper directed edges. We allow users to define two separate graphs, for each type of edge, using Python dictionary, in which keys/values respectively represent start/end nodes of the edge. When user-defined dependency graphs are provided, Engine compiles them and finds all paths required for automatic differentiation with modified depth-first search algorithm. Moreover, Engine ne sets constraining problem sets for each problem based on the dependency graphs, as mentioned above. Once all initialization processes are done, users can run full MLO program by calling Engine's hees run method, which repeatedly calls the one-step gradient descent procedure of lowermost problems. The example usage of Engint provided in Listing 2.
prob1 MyProblen !....
9rob2 MyProblen22 I...)
dependency (*u21*: (prebl: [prob21), ), "12u": (probl: [prob2]]
engine Engine (problems= (probi,,, prob2], dependencieesssaaandnnny (un
Listing 2: Engine class example.
5 EXPERIMENTS
To showcase the general applicability of BETTY, we implement three MLO benchmarks with varying complexities and scales: data reweighting for class imbalance (Sec. 5.1), correcting and reweighting corrupted labels (Sec. 5.2), and domain adaptation for a pretraniingfinetuning framework (Sec. 5.3).
Furthermore, we analyze the effect of different best-response Jacobian algorithms and system features by reporting GPU memory usage and training wall time. Last but not least, in the Appendix, we include an additional MI. benchmark experiment on differentiable neural architecture search (Appendix A), code examples (Appendix B), training details such as hyperparameters (Appendix C), analyses on various algorithmic and systems design choices (Appendix D and E).
5.1 DATA REWEIGHTING FOR CLASS IMBALANCE
Many real-world datasets suffer from class imbalance due underlying long-tailed data distributions. Meta- Heia-Weiggt-Net (MWN) (Shu et al., 2019) proposes to alleviate the class imbalance issue with a data reweighting scheme where they learn assign higher/lower weights to data from more rare/common classes. In detail, MWN formulates data reweighting with bilevel optimization as follows:
8* argmin Lval (w" (0))
Reweighting
1 N
s.t. w" (0) = argmin
R R(Livain:)) Liraen (f(z w), y:)
D> Classification
to
where w is the network parameters, Livain is the training loss for the i-th training sample, and is the MWN R's parameters, which reweights each training sample given its training loss L [irasn-
Following the original paper, we artificially inject class imbalance into the CIFAR-10 dataset by geometrically decreasing the number of data sample for each class, per imbalance factor. While

---

Published as a conference paper at ICLR 2023
the official implementation, which is built upon Torchmeta (Deleu et al., 2019), only adopts ITD- RMAD for best-response Jacobian calculation, we re-implement MWN with multiple best-response Jacobian algorithms, which only require one-liner changes using BETTY, to study their effect test accuracy, memory efficiency, and training wall time. The experiment results are given in Table 1.
Algorithm
IF 200
IF 100
50
Memory
Time
MWN (original)
ITD-RMAD
68.91
75.21
80.06
2381MiB
35.8m
MWN (ours, step=l)
ITD-RMAD
71.96
75.13
79.50
2381 MiB
36.0m
MWN (ours, step=1)
AID-CG
66.23+1188
7..88+1.68
75.41+0.61
2435MiB
67.4m
MWN (ours, step=1)
AID-NMN
66.45=1.18
10.92++..35
75.90 11.3
2419MiB
67.1m
MWN (ours, step=1)
AID-FD
75.45.10.3
78.11
81.15
2051MiB
28.5m
MWN (ours, step=5)
AID-FD
76.56.1.11
80.45
83.1110.554
2051MiB
65.5m
Table MWN experiment results. IF denotes an imbalance factor. AID-CG/NMN/FD respectively stand for implicit differentiation with conjugate gradien//Neuman series/finite difference.
We observe that different best-Jacobian algorithms lead to vastly different test accuracy. memory efficiency, and training wall time. Interestingly, we notice that AID-FD with unrolling steps of both 1 and 5 consistently achieve better test accuracy (close to SoTA (Tang et al., 2020)) and memory efficiency than other methods. This demonstrates that, while BETTY is developed to support large and general MLO programs, it is still useful for simpler bilevel optimization tasks as well. An additional analysis the effect of best-response Jacobian also be found in Appendix D.
Furthermore, to demonstrate the scalability of BETTY to large-scale MLO, we applied MWN to sentence classification with the BERT-base model (Devlin et al., 2018) with 110M parameters. Similarly, we artificially inject class imbalance into the SST dataset, and use AID-FD as our best- response Jacobian calculation algorithm. The experiment results are provided in Table 2.
Algorithm
IF
IF 50
Memory
Baseline
AID-FD
89.9
87.54
8319MiB
MWN (fp32)
AID-FD
out-of-memory 10511MiB
MWN (fp16)
AID-FD
91.06=0.09
89.79-0.655
Table MWN+BERT experiment results. fp32 and fp16 respectively stand for full-precision and mixed-precision training.
As shown above, default full- full-precision training fails due to the CUDA out-of out-of-memory error, while mixed-precision training, which only requires one-line change Config, avoids this issue while also providing consistent improvements in test accuracy compared to the BERT baseline. This demonstrates that our system features are indeed effective in scaling MLO to large models. We include more analyses our systems support in Appendix E.
5.2 CORRECTING & REWEIGHTING CORRUPTED LABELS
Another common pathology in real-world data science is the issue of label corruption, stemming from noisy data preparation processes (e.g. Amazon MTurk). One prominent example of this is in weak supervision (Ratner et al., 2016), where users create labels for large training sets by leveraging multiple weak/noisy labeling sources such as heuristics and knowledge bases. Due to the nature of weak supervision, generated labels are generally noisy, and consequently lead to a significant performance degradation. In this example, we aim mitigate this issue by 1) correcting and 2) reweighting potentially corrupted labels. More concretely, this problem can be formulated as an extended bilevel optimization problem, as, unlike the MWN example, we have two optimization problems-corredd correcting and reweighting-in the upper level, opposed to one. The mathematical formulation of this MLO program is as follows:
8 argmin Lvat(w" (w" (8,a)),
a" = argmin (w (f,
RWT & CRT
s.t. w/ (0, a)- argmin 10
R R(Lirasni 0) Liraen v())))))
Classification
7

---

Published as a conference paper at ICLR 2023
where, is the parameter for the label correction network g. and S is augmented with the classification loss of the correction network in addition to that of the main classification network f on the clean validation set.
We test our framework on the WRENCH benchmark (Zhang et al., 2021a), which contains multiple weak supervision datasets. In detail, response Jacobian algorithm, and Snorkel Data Programming (Ratner et al., 2016) as our weak supervision algorithm for generating training labels. The experiment results provided in Table 3.
a 2-layer MLP as classifier, AID-FD as best-
TREC
AGNews
IMDB
SemEval
ChemProt
YouTube
Snorkel
07.52:10.18
62.00:10.07
0.55
71.00.10.00
51.54:10.41
77.44
Baseline
13.88
80.74=0.20
72.26=0.81
71.50=0044
54,47=0.78
1.56
+RWT
1..56=1144
82.79=0.100
77.18=0.13
77.23=3.38
65.33++0.2
91.60=0.75
+RWT&CRT
1..76:t1.31
83.16-+0.20
77.80-0.26
84.34+1.43
67.69-11.17
91.52-+0.66
Table 3: Wrench Results. RWT stands for reweighting and CRT for correction
We observe that simultaneously applying label correction and reweighting significantly improves the test accuracy over the baseline and the reweighting-oni scheme in almost all tasks. Thanks to BETTY, adding label correction in the upper-level on top of the existing reweighting scheme only requires defining one more Problem class, and accordingly updating the problem dependency in Engine (code examples can found Appendix B).
5.3 DOMAIN ADAPTATION FOR PRETRAINING & FINETUNING
Pretraining/fnetuninng paradigms are increasingly adopted with recent advances in self-supervised learning (Devlin et al., 2018; He et al., 2020). However, the data for pretraining are oftentimes from different distribution than the data for finetuning, which could potentially cause negative transfer. Thus, domain adaptation emerges as a natural solution to mitigate this issue. As domain adaptation strategy, (Raghu et al., 2021) proposes combine data reweighting with a pretraining/finttmn framework to automatically decrease/increase the weight of pretraining samples that cause negative/- positive transfer. In contrast with the above two benchmarks, this problem can be formulated as trilevel optimization as follows:
0 argmin LFr(U" (pr("((w"()) (B)))
Reweighting
0
s.t. 0" (w" (0)) argmin (CFT(U) + N||u w- (0)11)
Finetuning
n
w² (0) argmin
R(x;0)) (up)(w))
Pretraining
where o; / Tipr stands for the i-th pretraining sample/loss, R for networks that reweight importance for each pretraining sample and X for the proximal regularization parameter, Additionally, w, and are respectively parameters for pretraining, finetuning, and reweighting networks.
We conduct an experiment on the OfficeHome dataset (Venkateswara et al., 2017) that consists of 15,500 images from 65 classes and 4 domains: Art (Ar), Clipart (CI), Product (Pr), and Real World (RW). Specifically. we randomly choose 2 domains and use one of them as a pretraining task and the other as finetuning task. ResNet-18 (He al., 2016) is used for all networks, and AID-FT with an unrolling step of is used our best-response Jacobian algorithm. Following (Bai et al., 2021), the finetuning and the reweighting stages share the same training dataset. We adopted normal pretraining/fietuming framework without the reweighting stage our baseline, and the result is presented in Table 4.
Our trilevel optimization framework achieves consistent improvements over the baseline for every task combination at the cost of additional memory usage and wall time, which demonstrates the empirical usefulness of multilevel optimization beyond two-level hierarchy. Finally, provide an example of (a simplified version of) the code for this experiment Appendix B to showease the usability of our library for general MLO program.
8

---

Published as a conference paper at ICLR 2023
Algorithm
Cl-+Ar
Ar-+Pr
Pr-+Rw
Rw-+CI
Memory
Time
Baseline
N/A
65.43.10.36
87.62-10.33
77.43.1041
68.76.10.13
3.8GiB
290s
+ RWT
AID-FD
67.76.10.83
88.53
78.58
69.75.10.43
8.2GiB
869s
Table 4: Domain Adaptation for Pretraining & Finetuning results. Reported numbers are classification accuracy on the target domain (right of arrow), after pretraining on the source domain (left of arrow). We note that Baseline is a two-layer, and Baseline + Reweight a three-layer, MLO program.
6 RELATED WORK
Bilevel & Multilevel Optimization There are a myriad of machine learning applications that built upon bilevel optimization (BLO), the simplest case of multilevel optimization with two- level hierarchy. For example, neural architecture search (Liu et al., 2019; Zhang et al., 2021b), hyperparameter optimization (Franceschi al., 2017; Lorraine al., 2020; Maclaurin et al., 2015), reinforcement learning (Hong et al., 2020; Konda & Tsitsiklis, 1999), data valuation (Ren et al., 2020; Wang et al., 2020), meta learning (Finn et al., 2017; Rajeswaran et al., 2019), and label correction (Zheng et al., 2019) are formulated as BLO. In addition to applying BLO to machine learning tasks, a variety of optimization techniques (Couellan & Wang, 2016; Grazzi al., 2020; Ji et al., 2021; Liu et al., 2021) have been developed for solving BLO.
Following the popularity of BLO, MLO with more than a two-level hierarchy has also attracted increasing attention recently (Raghu et al., 2021; Somayajula et al., 2022; Such et al., 2020; Xie & Du, 2022). In general, these works construct complex multi-stage ML pipelines, and optimize the pipelines in an end-to-end fashion with MLO. For instance, (Garg et al., 2022) constructs the and (He et al., 2021) of (data
pipeline of (data gennraatoon)((rcchtttttttt (wweighting)-(innttunnnn (prettatnnnn)-rrrrranninnnnnnn all of which are solved with MLO. Furthermore, (Sato et al., 2021) study gradient- based methods for solving MLO with theoretical guarantees.
search)-
Multilevel Optimization Software There are several software libraries that are frequently used for implementing MLO programs. Most notably, JAXopr (Blondel et al., 2021) proposes an efficient and modular approach for AID by leveraging JAX's native autodiff of the optimality conditions. Despite its easy-to-ure programming interface for AID, it fails to support combining the chain rule with AID as in Equation (2), because overrides the default behavior of JAX's automatic differentiation, which takes care of the chain rule. Therefore, it cannot be used for implementing MLO beyond a two-level hierarchy without major changes in the source code and the software design. Alternatively, higher (Grefenstette et al., 2019) provides two major primitives of making 1) stateful Py PyTorch modules stateless and 2) PyTorch optimizers differentiable to ease the implementation of AID/ITD. However, users still need to manually implement complicated internal mechanisms of these algorithms as well as the chain rule with the provided primitives. Torchmeta (Deleu et al., 2019) also provides similar functionalities as higher, but it requires users use its own stateless modules implemented in the library rather than patching general modules as in higher. Thus, it lacks the support for user's custom modules, limiting its applicability. learn2learn (Amold al., 2020) focuses on supporting meta learning. However, since meta-learning is strictly a bilevel problem, extending it beyond two-level hierarchy is not straightforward. Finally, most existing libraries do not have systems support, such as data- lata-parallel training, that could mitigate memory/compute bottlenecks.
7 CONCLUSION
In this paper, we aimed to help establish both mathematical and systems foundations for automatic differentiation in MLO. To this end, we devised a novel dataflow graph for MI.O, upon which an automatic differentiation procedure is built, and additionally introduced BETTY, software library with various systems support, that allows for easy programming of a wide range of MLO applications in modular fashion. We showed that BETTY allows for scaling up to both larger models with many parameters, as well as to MLO programs with multiple dependent problems. As future work, we plan to extend BETTY to support additional algorithmic and systems features, such as best-response Jacobian algorithms for non con-differentiable processes, and advanced memory optimization techniques like model-paralle training and CPU-offloading.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
Multilevel optimization has the power to be a double-edged sword that can have both positive and negative societal impacts. For example, both 1) defense or attack in adversarial game, and 2) decreasing or increasing bias in machine learning models, can all be formulated as MLO programs, depending on the goal of the uppermost optimization problem, which is defined by users. Thus, research in preventing malicious use cases of MLO is of high importance.
REPRODUCIBILITY STATEMENT
As one of main contributions this work a new software library for scalable multilevel optimization, all of the source code for the library and examples will be released open source with an Apache-2.0 License, including a full implementation of all MLO programs and experiments described this paper. In addition, for reviewing purposes, we include source code and easily runnable scripts for all experiments in the supplemental material of this submission.
ACKNOWLEDGEMENTS
We thank all the reviewers for invaluable comments and feedback. EX acknowledges the sup- port of NSF IIS I 563887, NSF CCF1629559 NSF IIS 161161583, NGA HLM0476201000) NIGMS R0IGM140467, NSF IIS 1955532, NSF CNS2008248. NSF IIS212395,, and NSF BCS2040381. WN was supported in part by NSF (1651565), AFOSR IFA955019100244 ARO (W91 INF-211-0012) CZ Biohub, Sloan Fellowship, and U.S. Department of Energy Office of Science under Contract No. DE-ACO2-76SFF05155
REFERENCES
Sébastien MR Aroold, Praateek Mahajan, Debajyoti Datta, Ian Bunner, and Konstantinos Saitas Zarkias. learn2learn: A library for meta-learning research. arXiv preprint arXiv:2008. /2284, 2020.
Yu Bai, Minshuo Chen, Pan Zhou, Tuo Zhao, Jason Lee, Sham Kakade, Huan Wang, and Caiming Xiong. How important is the train-validation split in meta-learning? In International Conference on Machine Learning, pp. 543-553, PMLR, 2021.
Mathieu Blondel, Quentin Berthet, Marco Cuturi. Roy Frostig, Stephan Hoyer, Felipe Llinares-Lópzz, Fabian Pedregosa, and Lean-Philipee Vert. Efficient and modular implicit differentiation. arXiv preprint arXiv:2 105. 15/33, 2021.
Nicolas Couellan and Wenjuan Wang. On the convergence of stochastic bi-level gradient methods. Optimization, 2016.
Hua Cui and Jie Bai. A new hyperparameters optimization method for convolutional neural networks. Pattern Recognition Letters, 125:828-834, 2019.
Tristan Deleu, Tobias Würfl, Mandana Samici, Joseph Paul Cohen, and Yoshua Bengio. Torchmeta: A Meta-Learning library for PyTorch, 2019. URL https::t.p.................t.. wwwaaiiiwoggaaaaaaeee..e. w9wpaa/////.././///// 06576. Available at:
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 1135-113. JMLR. org, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning, pp. 1165-1173. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2023
Bhanu Garg. Li Zhang, Pradyumna Sridhara, Ramtin Hosseini, Eric Xing, and Pengtao Xie. Learning from mistakes a framework for neural architecture search. Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference Machine Learning, pp. 3748-3758. PMLR, 2020.
Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Htut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, and Soumith Chintala. Generalized inner loop meta-learning arXiv preprint arXiv:1910.0177,, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
Xuehai He, Zhuo Cai, Wenlan Wei, Yichen Zhang, Luntian Mou, Eric Xing, and Pengtao Xie. Towards visual question answering on pathology images. In Proceedings of the 59th Annual Meeting the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pp. 708-718, 2021.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05/70. 2020.
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp. 4882 4892. PMLR, 2021.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXiv:1412.6988. 2014.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In ICLR, 2019.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34, 2021.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pp. 1540-1552. PMLR, 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- based hyperparameter optimization through reversible learning. In International conference machine learning, pp. 2113-2122 PMLR, 2015.
Athanasios Migdalas, Panos M Pardalos, and Peter Värbrand. Multilevel optimization: algorithms and applications, volume 20, Springer Science & Business Media, 1998.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Barak A. Pearlmutter and Jeffrey Mark Siskind. Reverse-mode in functional framework: Lambda the ultimate backpropagator. ACM Trans. Program. Lang. Syst., 30:7:1-7:33 2008
11

---

Published as a conference paper at ICLR 2023
Aniruddh Raghu, Jonathan Lorraine, Simon Kornblith, Matthew McDermott, and David K. Duvenaud. Meta-learning to improve pre- treiiiiinngg.... Advances in Neural Information Processing Systems, 34, 2021.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-16. IEEE, 2020.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. In International conference on machine learning, pp. 7953-7963. PMLR, 2020.
Alexander Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly, Advances in neural information processing systems, 29, 2016.
Zhongzheng Ren, Raymond Yeh, and Alexander Schwing. Not all unlabeled data are equal: Learning to weight data in semi-supervised learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21786-21797. Curran Associates, Inc., 2020. URL https::/ neurips. cc/ paper/ 201///22200//// f7 6 9a ddl.aaadd55522222 2al.a988000555222211111111666653
Ryo Sato, Mirai Tanaka, and Akiko Takeda. A gradient method for multilevel optimization. Advances in Neural Information Processing Systems, 34, 2021.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Samping Zhou, Zongben Xu, and Deyu Meng. Meta-weight- net: Learning an explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, pp. 1919-1930, 2019.
Sai Ashish Somayajula, Linfeng Song, and Pengtao Xie. A multi-level optimization framework for end-to-end text augmentation. Transactions of the Association for Computational Linguistics, 10: 343-358. 2022.
Felipe Petroski Such, Aditya Rawal, Joel Lehman, Kenneth Stanley, and Jeffrey Clune. Generative teaching networks: Accelerating neural architecture search by learning generate synthetic training data. In International Conference on Machine Learning, pp. 9206-9216. PMLR, 2020.
Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. Advances in Neural Information Processing Systems, 33:1513-1524, 2020.
Hemanth Venkateswara, Jose Fusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5018-5027, 2017.
Luis N Vicente and Paul H Calamai. Bilevel and multilevel programming: A bibliography review. Journal of Global optimization, 5(3):291-306, 1994.
Yulin Wang, Jiayi Guo, Shiji Song, and Gao Huang. Meta-semi: A meta-learning approach for semi-supervised learning, CoRR, abs/2007.02394 2020. URL https: 2007.02394
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. Proceedings of the IEEE conference on computer vision and pallern recognition, pp. 2691-2699, 2015.
Pengtao Xie and Xuefeng Du Performance-awar mutual knowledge distillation for improving neural architecture search. CVPR, 2022.
12

---

Published as a conference paper at ICLR 2023
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. Wrench: A comprchensive benchmark for weak supervision. arXiv preprint arXiv:2109.11377 2021a.
Miao Zhang, Steven W Su, Shirui Pan, Xiaojun Chang, Ehsan M Abbasnejad, and Reza Haffari. idarts: Differentiable architecture search with stochastic implicit gradients. In International Conference on Machine Learning. pp. 12557-12566. PMLR, 2021b.
Guoqing Zheng, Ahmed Hassan Awadallah, and Susan T. Dumais, Meta label correction for learning with weak supervision. CoRR, 191000899, 2019, URL http: / /arxivvxvvv////////////////v/av/ org/orgg///... / 1911. 03809.
13

---

Published as a conference paper at ICLR 2023
A ADDITIONAL MULTILEVEL OPTIMIZATION BENCHMARKS
A.1 DIFFERENTIABLE NEURAL ARCHITECTURE SEARCH
neural network architecture plays significant role in deep learning research. However, the search space of neural architectures is so large that manual search is almost impossible. To overcome
this issue, DARTS (Liu al., 2019) proposes an efficient gradient- based neural architecture search method based on the bilevel optimization formulation:
a' argmin (vel(w" (ox),
Architecture Search
S.t. w (a) argmin Ltrain (w; ox)
>
Classification
where is the architecture weight and is the network weight. The original paper uses implicit differentiation with finite difference as its best-response Jacobian algorithm to solve the above MLO program.
We follow the training configurations from the original paper's CIFAR- 10 experiment, with a few minor changes. While the original paper performs finite difference method on the initial network weights, we perform it on the unrolled network weights. This is because we view their best-response Jacobian calculation from the implicit differentiation perspective, where the second-order derivative is calculated based on the unrolled weight. This allows us to unroll the lower-level optimization for more than one step as opposed to strict one-step unrolled gradient descent of the original paper. A similar idea was also proposed in iDARTS (Zhang et al., 2021b). Specifically, we re-implement DARTS with implicit differentiation and finite difference using and unrolling steps. The results are provided in Table 5.
Algorithm
Test Acc.
Parameters
Memory
Wall Time
Random Search
Random AID-FD"
96.71%
3.2M
N/A
N/A
DARTS (original)
97.24%
3.3M
10493MiB
25.4h
DARTS (ours, step=l)
AID-FD
97.39% %
3.8M
10485MiB
23.6h
DARTS (ours, step=3)
AID-FD
97.22%
3.2M
10485MiB
28.5h
Table 5: DARTS re-implementation results. AID-FD refers to implicit differentiation with a finite difference method, and indicates the difference in the implementation of AID-FD explained above.
Our re-implementation with different unrolling steps achieves a similar performance as the original paper. We also notice that re-implementation achieves slightly less GPU memory usage and wall time. This is because the original implementation calculates gradients for the architecture weights (upper-level parameters) while running lower-level optimization, while ours only calculates gradients of the parameters for the corresponding optimization stage.
14

---

Published as a conference paper at ICLR 2023
A.2 CORRECTING & REWEIGHTING CORRUPTED LABELS (EXTENDED)
To further demonstrate the general applicability of BETTY to different datasets and scales, we performed experiments from Section 5.2 in two additional settings.
Clothing-IM 1M ResNet-50 Clothing- IM (Xiao et al., 2015) is real-world noisy dataset that consists of million fashion images collected from various online shopping websites and has the approximate noise ratio of 38.5%. Following the standard, we use ResNet-50 our backbone model and attempt to correct and reweight noisy labels with extended bilevel optimization. The experiment result is presented in Table
Test Accuracy
Baseline
70.76%
+RWT 75.57% RRT&&CRT
76.34%
Table 6: Clothing- 1M ResNet-50 results.
In this experiment, we are able to empirically show that the MLO application implemented with BETTY works well with a large-scale dataset.
Wreneh + BERT-base In recent years, finetuning the pretrained large language model has become the standard for text classification. As the Wrench benchmark mostly consists of text classification datasets, we further applied our "correcting and reweighting corrupted labels" framework to the BERT-base model.
TREC
AGNews
IMDB
SemEval
ChemProt
YouTube
Baseline
6,,14
16.1270.17
71.66=2.05
79.93+1.55
52.35=+0.56
93.20 1. 1.44
+RWT
84.07+4.42
89.622+060
87.85-0.24 87.45=0.39
87.45=0.69
7..42+1.50
94.67=0.46 94.80=0.80
+RWT&CRT
93.07=0.31
90.40=20.16
87.92=0.04
7..27=1.23
Table 7: Wrench BERT-base results.
In this experiment, we are able to empirically show that the MLO application implemented with BETTY works well with a large model.
15

---

Published as a conference paper at ICLR 2023
B CODE EXAMPLE
Here, we provide simplified code for our experiments from Section Note that every experiment shares a similar code structure when implemented with BETTY.
B. DATA REWEIGHTING FOR CLASS IMBALANCE
train Loader, valid loader setup_dataloace dataloader rwt moc_mo, rwt ont_peeee bettupreweight// cls module, optiiiemm cls scheduler setup cttupcclassifer//
Level 2
class Reweight (ImplicitProblem):
def training (self, batch) inputs, labels batch
outputs self.classifier (inputs)
10
return F.cross_ent (cutputs, labels)
Level class Classitier (tgpaiiieetnmlliitttPPtooo..
13
14
def training_step (self,, batch)
15
inputs, 1abels batch
outputs self self.module (inputs)
lcss = crosss entropy (cutputs, labels, redaction="none")
18
lcss rrsspeehape- reshaee (less, (-1, 1))
19
# Reweighting
20
weight self.reweinn
detach )))
return torch.mean (weight loss_reshape)
22
23 upper_config (ty retain_graph-Truee
24
lower_config = Confittty"===defautt,, unroll_steps-5)
reweight Reweight (name="reweignt",
27
coniigrupper_ccntigg,
28
module=zwt_mmcdule,
29
train_atta_lcaeerrvaaldddddddde
classifier C
32
config=lower_coonii.,
33
module=cis_mmddule,
34
ottinier=:cl__ppimmbee,,
schcdule:=classchhccdlllr
36
37
38 probs = [reweight, classifier]
u21 (reweight: [classifier:
12u (classi fier: [reweight]]
41 depencs ("12u": 12u, "u21": u21)
42
43 engine Engine (problems=probs, dependenciessdepeends))
engine. run
Listing 3: Simplified code of "Data Reweighting for Class Imbalance"
16

---

Published as a conference paper at ICLR 2023
B.2 CORRECTING & REWEIGHTING CORRUPTED LABELS
train_ oader, val id loader secup aecup_dataloade
mot_med est_opt r1
ort_module, ert_aptiimizer setup_correste cla_module, cls_optimizer, cla_scheduler setup_clasaitler) ()
Level 2
class correct [ImplicitPrablcnn) def training_atep bates):
inguts, labels batch
outputa, embeds sel fellfclassi fl (inputs, return_ Trrurss-eeedsstrru
11
cozrect_outputa melf.module (embeds, Lest=Tcue)
ce_icss eay leutputs, iabels)
13
aux_loss = s.cross_entreppy (correer__uuputs,, labels! return ce_lesa aux_loas
15
16 Level 2
Reweight (TapLieitPrablem): def sralning_stepp(est batea):
18
imputs, labels outputs celf. return pooross_nttroyyootttee lasels)
20
22
23
Level 1
clasa Classifier (implicttProhhlmm
25
def training_step (zelf, batca):
inputs, labels outputa, embeds f. (tootul return_embeda=Truo) 1 Correcting
27
28
29
new_labeie self.correct lembeds, lsbels]
30
log_softmax = s.log_scftme (outputs, dims-1)
loss tarch.aum torch.oum(-loggoofteee coffloooottoxxxx new_labels, dims-1]
32
loss_reshape reshape
(-1, 2))
33
Reweighting
34
weight rellf.rowightt (loss_ reshape.detachh ())
35
zeturn Lorch.mesn (weight loss_reshlape)
36
37 upper_config Config (typa="aaaa"" grthhh
ower_oonfig Config "dypa unrol _sceps=5)
39
correct (name=*correct"
41
aarri--uppe_contiig
42
module=crt_modalee.
43
ogtimizeerwrtt_ottinng
aaash_data_loddar-ttt
reweight Reweige (name="rewelgnt",
46
configsugpor_confiig
47
moduleerat_nodtule.
48
49
trein_det__ooderrallllleeee
classifier Classifier alaciifirrimmes=ssaaasiiiii
51
con"|galower_confis
nodilee=ll__module.
53
optimilzersca__pptin
cchedullereel__Bchedllee
55
tzain_@ata_loddeerrtteiii..
56
prcbs [correct, rexaight, classifies]
58 321 icorrect: [classitier], reweight: [classitier]]
:classifier: Icorrect, zeweight]; 60 depends = (*12u": 12u, "u21"; u21;
62 engine Engine (problems-probs, dependencies-deeer:di)
63
engine.ren()
Listing 4: Simplified code of "Correcting & Reweighting Corrupted Labels"
17

---

Published as a conference paper at ICLR 2023
B.3 DOMAIN ADAPTATION FOR PRETRAINING & FINETUNING
Get module, optimizer, lr_scheduler, data loader for each problem
2 re__odule, pt_optimizer, st_scheduler, pt_loader ft_module, st_optimizer, ft_scheduler, ft_loader setup_fineture ()
()
rw_module, rw_optimizer, rw_scheduler, rw_loader setup_reweight ()
level
class
def training_step (self, batch)
inputs, targets patch outs wwwf..oouueeeeeee..eee.ee.eee.we (inputs)
10
11
lcss raw = F. cross cerrossentrroyyyoeeee (outs, targets, reduction="nont "nore")
12
logit celf.reweight (inputs) weight torch. s sigmoid (lcgit)
14
15
return torch. mean (loss_raw raw weight)
16
Level 2
class Finetune (ImplicitProolem)
19
def training_step (selt, batch)
20
inputs, targets = patch
21
outs self.module
less w.cross_entroos (ocross_entrooyyoutss,,, targets, reduction-"nanse less torch.mean (ce_loss)) # Proximal reqularization for (nl, pl), p2 in pretrain..rodue..r (aramleepaammmterss(
23
24
25
self.
lam if "fo" in nl clse args. lam
27
lcss lam (pl p2) pow (2) sum ()
28
return loss
29
Level 3
class Reweight (ImplicitProollmm) def training step training_step(sel1t, batch) inputs, targets = patch outs = melfffineture (inputs)
32
33
34
return roy (cuts, targets)
36
37 Define optimization configuratiens
38 reweight__cnnffe = (type="dat step=1,
finetune_config = Config Config defull"" step=1)
pretrain_config Config (tn==ddtttt=="ffaalttt" step=1) 41
42
pretrain = Pretrain ("pretrain", pt_config, pt_module, pt_optimizer pt_scheduler, pt_loader)
43
finetune Finetune ("finetune", ft_config, ft_module, ft_optimizer ft_scheduler, ft_loader)
46
reweight Reweight ("reweight", rw_config, rw_nodule, rw_optimizer rw rw_scheduler, rw_leader)
47
48
probs rreweight, finetune, pretrain]
50 u21 (reweight: [pretrain]
31 12u (pretrain: [finetune], finetune: [reweight]]
22 depends ("u21": u21, "12u": 12u)
engine Engine (problems=probe, dependenclee--deennss)
engine.run
Listing Simplified code of "Domain Adaptation for Pretraining & Finetuning"
18

---

Published as a conference paper at ICLR 2023
B.4 DIFFERENTIABLE NEURAL ARCHITECTURE SEARCH
train_loader, valid boaid_ @ecu__datlloderr1 ()
arch arch_moaule, arch_optimizen = aetupaarchitecturo.
cls_moculc, ims_optimizer, cls_schedule sctupcllassifier
Level class (Implctorr def training_step (self, f, batch):
target batch alphas self.module return classfiarr loss (x, alphas, target)
10
11
12
Level 1
class Classi (ImplicitProblem)
14
def training_step(sel1 batch) x, target batch alphas self.architecture()
15
16
return self half.module.loss( alphas, target)
19
arch_contig Cenfig (type="darts",
20
step=1,
21
retain_graph-irue,
first_order-True)
23
cls_config config(tyye==defaul""))
24
25
architecture = Architecture Aratitetture (nane="architecturre)
contigsarch_config,,
modulc-arch_mmodule,,
28
cot.m/eerFarchh.opimmlzzz..
29
30
classifier Classifier (mame="classifierr"
config=cls_config.
module=c1l__mobble,
33
ogtimlze===dss.ppimmeeee:
34
35
train data train_ in Loader)
37 probs [architecture, classifier]
38 u21 (architecture: [classifier]
39 12u (classifier: [architecture]]
depends ("12u": 12u, "u21": u21]
12 engine Engine (problems=probs, dependenciees-dependes)
0 engine.run ()
Listing 6: Simplified code of "Differentiable Neural Architecture Search"
19

---

Published as a conference paper at ICLR 2023
C EXPERIMENT DETAILS
In this section, we provide further training details (e.g. hyperparameters) of each experiment.
C.I DATA REWEIGHTING FOR CLASS IMBALANCE
Dataset We reuse the long-tailed CIFAR- 10 dataset from the original paper (Shu al., 2019) as inner-level training dataset. More specifically, the imbalance factor is defined the ratio between the number of training samples from the most common class and the most rare class. The number of training samples of other classes defined by geometrically interpolating the number of training samples from the most common class and the most rare class. We randomly select 100 samples from the validation set construct the upper-level (or meta) training dataset, and use the rest of it the validation dataset, on which classification accuracy is reported in the main text.
Meta- Weight-Network We adopt a MLP with one hidden layer of 100 neurons (i.e. 1-100-1) as our Meta- Weight-Network (MWN). It is trained with the Adam optimizer (Kingma & Ba, 2014) whose learning rate set to 0.00001 throughout the whole training procedure, momentum values to (0.9, 0,999), and weight decay value to O. MWN is trained for 10,000 iterations and learning rate is fixed throughout training.
Classification Network Following the original MWN work (Shu et al., 2019), use ResNet32 (He et al., 2016) as our classification network. is trained with the SGD optimizer whose initial learning rate is set to 0, momentum value to 0.9, and weight decay value 0.0005. Training is performed for 10,000 iterations, and we decay the learning rate by a factor of 10 on the iterations of 5,000 and 7,500.
C.2 CORRECTING & REWEIGHTING CORRUPTED LABELS
Dataset We directly use TREC, AGNews, IMDB, SemEval, ChemProt, YouTTub text classification datasets from the Wrench benchmark (Zhang et al., 2021a). More specifically, we use the training split of each dataset for training the classification network, and the validation split for training the correcting and the reweighting networks. Test accuracy is measured on the test split.
Correct Network Our correct network takes the penultimate activation from the classification network, and outputs soft labels through the linear layer and the softmax layer. These new soft labels are interpolated with the original labels via the reweighting scheme which is achieved with 2-layer MLP. As our reweighting network, the correct network is trained with Adam optimizer whose learning rate is set to 0.00001, momentum values to (0.9, 0.999), and weight decay value to 0.
Reweighting Network For our reweighting network, we reuse Meta- Weight-Ne from the "Data Reweighting for Class Imbalance" experiment, follow all the training details.
Classification Network As our classification network, we adopt a 2-layer MLP with the hidden size of 100. The classification network is trained for 30,000 iterations with the SGD optimizer whose learning rate is set to 0.003, momentum to 0.9, and weight decay to 0.0001. Learning rate is decayed with the cosine annealing schedule during training.
C.3 DOMAIN ADAPTATION FOR PRETRAINING & FINETUNING
Dataset We split each domain of the OfficeHome dataset (Venkateswara et al., 2017) into train- ing/validation/test datasets with ratio of 5:3:2. The pretraining network is trained on the training set of the source domain. Finetuning and reweighting networks are both trained on the training set of the target domain following the strategy proposed in (Bai et al.. 2021). The final performance is measured by the classification accuracy of the finetuning network on the test dataset of the target domain.
20

---

Published as a conference paper at ICLR 2023
Pretraining Network We use ResNet18 (He et al., 2016) pretrained on the ImageNet dataset (Deng et al., 2009) for our pretraining network. Following the popular transfer learning strategy, we split the network into two parts. namely the feature (or convolutional layer) part and the classifier (or fully-connected layer) part, and each part is trained with different learning rates. Specifically, learning rates for the feature and the classifier parts respectively set 0.001 and 0.0001 with the Adam optimizer. They share the same weight decay value of 0,0005 and momentum values of (0.9, 0.999). Furthermore, we encourage the network weight to stay close the pretrained weight by introducing the additional proximal regularization with the regularization value of 0.001. Training is performed for 1,000 iterations, and the learning rate decayed by factor of 10 on the iterations of 400 and 800.
Finetuning Network The same architecture and optimization configurations the pretraining net- work are used for the finetuning network. The proximal regularization parameter, which encourages the finetuning network parameter stay close to the pretraining network parameter, is set to 0.007.
Reweighting Network The same architecture and optimization configurations as the pretraining network are used for the reweighting network, except that no proximal regularization is applied the reweighting network.
C.4 DIFFERENTIABLE NEURAL ARCHITECTURE SEARCH
Dataset Follwing the original paper (Liu et al., 2019), we use the first half of the CIFAR-10 training dataset as our inner-level training dataset (i.e. classification network) and the other half as the outer-level training dataset (i.e. architecture network). Training accuracy reported in the main text is measured the CIFAR-10 validation dataset.
Architecture Network We adopt the same architecture search space as in the original paper (Liu al., 2019) with 8 operations, and nodes per convolutional cell. The architecture parameters are initialized to zero to ensure equal softmax values, and trained with the Adam optimizer (Kingma & Ba, 2014) whose learning rate fixed 0.0003, momentum values to (0.5, 0.999), and weight decay value to 0.001 throughout training. Training is performed for 50 epochs.
Classification Network Given the above architecture parameters, we set our classification network to have 8 cells and the initial number of channels to be 16. The network is trained with the SGD optimizer whose initial learning rate is set to 0.025, momentum to 0.9, and weight decay value to 0.0003. Training is performed for 50 epochs, and the learning rate decayed following the cosine annealing schedule without restart to the minimum learning rate of 0.001 by the end of training.
21

---

Published as a conference paper at ICLR 2023
D DESIGN CHOICE ANALYSIS
In this section, we visually compare the convergence speed of different best-response Jacobian algorithms with the loss convergence graphs on the synthetic hyperparameter optimization task and the data reweighting task (Section 5.1). Specifically, we analyze the convergence speed in terms of both the number of steps and training time, the per-step computational cost differs for each algorithm.
D.1 SYNTHETIC HYPERPARAMETER OPTIMIZATION
Following (Grazzi et al., 2020), we constructed synthetic hyperparameter optimization task where we optimize the weight decay value for every parameter in simple binary logistic regression. Mathematically, this problem can be formulated as bilevel optimization as follows:
x arg min sigmoid (ya w*)
w arg min sigmoid ) + _ diag(A)u
w
where, (Iz, yt) and (Zaa are repsectively the training datasets for the lower-(and upper-))eve llevel problems, with æ E Bnxd and y E R Here, is the number of training data in each dataset and d the dimension of the feature vector. w E gdx1 is the logistic regression parameter, and [Rdx] the hyperparameter (i.e. the per-parameter weight decay value).
Given the above setup, we compared four different best-reponse Jacobian algorithms: 1) ITD-RMAD, 2) AID-FD, 3) AID-CG, and 4) AID-Neumann. For the fair comparison, we fixed the unrolling step to 100 for algorithms. The experiment result presented below:
ITD-RMAD
AID-FD
AID-Neumam
AIDDOG
(a) Outer training loss (x-axis: time)
(b) Outer training loss (x-axis: step)
Figure 3: Convergence analysis of different best-response Jacobian algorithms the synthetic hyperparameter optimization task
As shown in Figure 3, AID-CG achieves the fastest convergence both in terms of training steps and training time. However, AID-FD achieves the fastest per-step computation time as the only algorithms that doesn't 't require the explicit calculation of the second-order derivative (i.e. Hessian).
D.2 DATA REWEIGHTING
To study how different best-response Jacobian algorithms perform on more complex tasks, we repeated the above experiment the data reweighting task from Section 5.1. Again, for the fair
22

---

Published as a conference paper at ICLR 2023
comparison, used the same unrolling step of for all algorithms. The experiment result is provided in Figure 4.
ITD-RMAD
AID-FD
AID-Neumann
:AID-CG
Valid 8Oc.
Valid
acc.
80
60
40
40
12k
0.2
0.4
0.6
0.8
1
1.2
Training step
Training time (hr)
Figure 4: Convergence analysis of different best-response Jacobian algorithms the data reweighting task
Unlike in the synthetic hyperparameter optimization task, AID-FD achieves the fastest convergence terms of training steps and training time as well as the best final validation accuracy. As AID- FD doesn't require any second-order derivative calculation, it also achieves the minimal per-step computation cost.
Above two experiments follow the free lunch theorem: the optimal design choice can vary for different tasks without golden rules. However, thanks to the modular interface for switching between different design choices (in Config) only minimal programming efforts would be needed with BETTY, expediting the research cycle.
23

---

Published as a conference paper at ICLR 2023
E SYSTEMS SUPPORT
In this section, we perform additional analyses on the memory saving effects of our system features with two benchmarks: (1) differentiable neural architecture search and (2) data reweighting for class imbalance.
E.1 DIFFERENTIABLE NEURAL ARCHITECTURE SEARCH
Baseline
+ mixed-precision
GPU Memory Usage
9867MiB
S759MiB
Table 8: GPU memory usage analysis for DARTS.
E.2 DATA REWEIGHTING FOR CLASS IMBALANCE
In this experiment, ResNe150 (He al., 2016) instead of ResNet30, to better study the memory reduction from our system features, when the larger model is used. Importantly, we also test the data-parallel training feature in addition to the sixed-precision training feature.
Baseline
mixed-precision
data-parallel (2 GPUs)
GPU Memory Usage
681 1MB
4397MiB
3185/3077MiB (GPU0/I)
Table 9: GPU memory usage analysis for MWN with ResNet-50.
As shown above, we observe more reduction in memory usage as we add system features.
24

---

Published as a conference paper at ICLR 2023
F
SUPPORTED FEATURES
Here, we summarize the supported features within BETTY.
Category
Features
ITD-RMAD
Best-response
AID-FD
Jacobian
AID-NMN
algorithms
AID-CG
MMieed-preee precision
Systems
-ataaaaaaaat Data-parallel
Gradient accumulation
Default Python logging TensorBoard
Logging
Weights & Biases
Gradient clipping Early stopping
Miscellancous
Table 10: Supported features in BETTY
25

---

Published as a conference paper at ICLR 2023
G
DATAFLOW GRAPHS FOR EXPERIMENTS
Reweight
Reweight
Correct
Reweight
Architecture
0r
lr
0
w
w
Classifier
Classifier
Finetune
Classifier
Pretrain
Data Revieghting for Cless Imbalance
5.2 Correcting Reweighitng Corrupted Labels
Domaiin Adaptation Pretraining Finetuning
A.1 Differentiable Neural Architecture Search
Figure 5: Dataflow graphs for all experiments
26


Reviews:
[{"review_id": "ii6AmZQj0eC", "reviewer": "Reviewer_5V8s", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strength:\n1. The paper is well written and the presentation is clear.\n2. Applications of MLO in machine learning are very common hence studies of more efficient automatic differentiation methods are interesting.\n3. The evaluations are performed on several commonly used scenarios. The empirical evidences for the validation of the proposed method is relatively strong.\n\nWeaknesses:\n1. 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.\n2. 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.\n3. More comparisons with existing software libraries should be considered other than the single default baseline in each application.\n4. Experiments are mainly focused on the relatively simple CIFAR-10 benchmark.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XyIBV8vIFB", "reviewer": "Reviewer_gnFX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work presents an auto-differentiation library for gradient-based MLO. This work makes the following contributions:\n1. 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)$.\n2. This work introduces a software library named BETTY to support large-scale MLO based on the technique mentioned in contribution 1. \nThe authors demonstrate the effectiveness and stability of BETTY with hundreds of millions of parameters by performing MLO on the BERT-base model. \n", "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. ", "strength_and_weaknesses": "Strength:\n1. The efficient automatic differentiation method is novel and effective. \n2. 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. \n2. The system will be released open source. \n3. The background knowledge and math foundations are clearly presented. \n     \nThis is very impressive work to me. I do not see a major limitation of the proposed system.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IsnEAKXC2Ay", "reviewer": "Reviewer_G2gf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes Betty, a library for automatic differentiation for\noptimization. The authors describe the library and its design and evaluate it on\na number of problems, comparing to other approaches.", "summary_of_the_review": "The paper is well written, the design of the proposed library makes sense and\nallows for more efficient differentiation than other methods, and the\nexperimental results are convincing. This is a nice paper that should be\naccepted.", "strength_and_weaknesses": "+ important problem\n+ useful library that achieves good results", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6ZWuiPUattY", "reviewer": "Reviewer_MAHC", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\nIt 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.\nExperiments showcase the computational (and memory) efficiency of the library, as well as its flexibility, on existing problems and variants.", "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.\nI recommend to accept it.\n\n**Update after response**\nThanks to the authors for their answers and for elaborating on the points raised. I still recommend acceptance, and maintain my rating.", "strength_and_weaknesses": "Strengths\n-------------\n1. Principled expansion of bilevel optimization (which enjoy increasing popularity) to a DAG of sub-problems, well described\n2. Understandable and usable formalism to define such problems in practice in a framework\n3. Several informative examples, demonstrating the range of capabilities of the framework\n4. Comparison with (and exploration around) SOTA, demonstrating similar (or improved) results and efficiency.\n5. Extensive appendix with details\n6. Opensource code\n\nWeaknesses\n------------------\n1. Clarity could be improved in some places, as it can be a difficult problem to grasp (see below)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%