BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach
Authors: Bo Liu
Mao Ye
Stephen Wright
Peter Stone
qiang liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: bilevel optimization

Abstract: Bilevel optimization (BO) is useful for solving a variety of important machine learning problems including but not limited to hyperparameter optimization, meta-learning, continual learning, and reinforcement learning.
Conventional BO methods need to differentiate through the low-level optimization process with implicit differentiation, which requires expensive calculations related to the Hessian matrix. There has been a recent quest for first-order methods for BO, but the methods proposed to date tend to be complicated and impractical for large-scale deep learning applications. In this work, we propose a simple first-order BO algorithm that depends only on first-order gradient information, requires no implicit differentiation, and is practical and efficient for large-scale non-convex functions in deep learning. We provide non-asymptotic convergence analysis of the proposed method to stationary points for non-convex objectives and present empirical results that show its superior practical performance.

BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach
Bo Liu Mao Ye Stephen Wright Peter Stone Qiang Liu
'he University of Texas at Austin University of Wisconsin-Madison 3 Sony Al Hiblii,,yy22 , lqiang)@cc utexas edu, eswright&cs wisc. edu
Abstract
Bilevel optimization (BO) is useful for solving a variety important machine learning problems including but not limited to hyperparameter optimization, meta- learning, continual learning, and reinforcement learning. Conventional BO methods need to differentiate through the low-level optimization process with implicit dif- ferentiation, which requires expensive calculations related to the Hessian matrix. There has been recent quest for first-order methods for BO, but the methods pro- posed to date tend to be complicated and impractical for large-scale deep learning applications. In this work, we propose simple first-order BO algorithm that de- pends only on first-order gradient information, requires no implicit differentiation, and is practical and efficient for large-scale non-convex functions in deep learning. We provide a non-asymptotic convergence analysis of the proposed method to stationary points for non-convex objectives and present empirical results that show its superior practical performance.
Introduction
We consider the bilevel optimization (BO) problem:
min (v, s.t. A E arg min g ( 8'),
(1)
8'
where the goal to minimize an outer objective f whose variables include the solution of another minimization problem w.r.t an inner objective g. The 0 and are the inner and outer variables, respectively. We assume that v E IRm 1Rm"00 IR" and that g(t, -) attains a minimum for each v.
BO is useful in a variety of machine learning tasks. A canonical example is hyperparameter opti- mization, in which case / (resp. g) is the validation (resp. training) loss associated with model parameter 8 and hyperparameter v, and we want to find the optimal hyperparameter to minimize the validation loss f when 9 is determined by minimizing the training loss; see e.g., Pedregosa 42]. Franceschi et al. [12] Other applications include meta learning [2]. continual Icarning [43]. reinforcement learning 122 and adversarial learning 2
See Liu al. for recent survey.
BO is notoriously challenging due to its nested nature. Despite the large literature, most existing methods for BO are slow and unsatisfactory in various ways. For example, major class of BO methods is based on direct gradient descent on the outer variable while viewing the optimal inner variable 0* (v) arg ming g(v,0) a (uniquely defined) function of u. The key difficulty is to calculate the derivative v.00 (v) which may require expensive manipulation of the Hessian matrix of g via the implicit differentiation theorem. Another approach to replace the low level optimization with the stationary condition Vag(v, 0) O. This still requires Hessian information, and more importantly, unsuitable for nonconvex g since it allows 6 to be any stationary point of g(v.-).
* "Equal contribution. MY mainly contributes developing theory and BL mainly contributes conducting experiment. Both authors contribute equally on paper writing.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

not necessarily a minimizer. To the best of our knowledge, the only existing fully first-order BO algorithm: are BSG-1 [T5] and BVFSM with its variants B3 but BSG-1 relies on a non- vanishing approximation that does not yield convergence to the correct solution in general, and BVFSM is sensitive to uyper-parameters on large-scale practical problems and lacks a complete non-asympiotic analysis for the practically implemented algorithm.
In this work, we seek simple and fast fully first-order BO method that can be used with non- convex functions including those appear in deep learning applications. The idea is to reformulate ① as a single-level constrained optimization problem using the so-called sellee-funttion-bee approach [TO] 77.. The constrained problem is then solved by stopping gradient on the single variable that contains the higher-order information and applying a simple first-order dynamic barrier gradient descent method based on method of Gong et al. [16]. Our contributions are: 1) we introduce a novel and fast BO method by applying a modified dynamic barrier gradient descent on the malue-function reformulation of BO; 2) Theoretically, we establish the non-asymptotic convergence of our method to local stationary points (as measured by special KKT loss) for non-convex f and g. Importantly, to the best of our knowledge, this work is the first to establish non-asymplotic convergence rate for fully first-order BO method. This result is also much beyond that of Gong et al. [T and Ji et al. [22] 3) Empirically, the proposed method achieves better or comparable performance while being more efficient than state-of-the tt--hhe-rtt art BO methods on a variety of benchmarks.
2 Background
This section provides a brief background on traditional BO methods. Please see Bard 22. Dempe and Zemkoho Dempe [6] for overviews, and Liu et al. 62 for a survey on recent ML applications.
Hypergradient Descent Assume that the minimum of g(v,-) -) is unique for v so that we can write 8' (v) arg ming g(v, ()) as function of u; this is known as the low-level singleton (LLS) assumption. The most straightforward approach to solving Q is to conduct gradient descent on f(v,0'()) (v)) function of v. Note that
(u, 0 (v)) = Vif(u, (v)) + (v)
The difficulty is to compute V, (v). From implicit function theorem, it satisfies a linear equation:
V1,2((,, 0" (v)) + V2,20(v, 0* (u)) (0,0(()') (v) = O.
If 2.29 is invertible, we can solve for (v) and obtain a gradient update rule on et
uk+1 f Uk - ((V.V - (VI29)) T (V2.20)) (V (V2.2%)-'V221
where it denotes iteration, Vifa (Vk, 8" (vx)) sometimes known as the hypergradient descent. However, hypergradient descent is computationally expensive: Besides requiring evaluation of the inner optimum 8 ("x)), the main computational
and similarly for the other terms. This approach
bottleneck is to solve the linear equation in ( Methods have been developed that approximate ?
using conjugate gradient 4
Neumann series 29 37 and related variants [4] Another
popular approximation approach is to replace v,0*(u) (v) with V. (,)(T)(v). where ((T) denotes the
T-th iteration of gradient descent or other optimization steps on gl, 0) w.r.t. O starting from certain
initialization. The gradient (TT (w) can be calculated with auto-differentiation (AD) with either
forward mode [αI), backward mode [12 4o 28 or their variants 3I. While these approaches
claim to be first-order, they require many Hessian-vector or Jacobian-vector products at each iteration
and are slow for large problems.
Other examples of approximation methods include a neural surrogate method which approximates (v) and its gradient v.0"(v (c) with neural networks 38 and Newton-Gaussian approximation of the Hessian matrix with covariance of gradient [15. Both approaches introduce non-vanishing approximation error that is difficult to control. The neural surrogate method also suffers from high training cost for the neural network.
Stationary-Seeking Methods. An alternative method is to replace the argmin constraint in the stationarity condition Vog(v, 8) 0, yielding a constrained optimization:
| with
min f(v, 0) s.t. Vog(v, 0) 0.
v.0
By fully first-order, we mean methods that only require information of f, g, Vf. Vg, so this excludes meth- ods that apply auto-differre dioo-ffffeeentitiinn conjugate gradient that need multiple steps of matrix- vector computation.

---

Algorithms for nonlinear equality constrained optimization can then be applied 139 The constraint in 3 guarantees only that is stationary point of g(v,)), so is equivalent ! only when g is convex w.r.t. 0. Otherwise, the solution of s can be maximum or saddle point of g. This makes it problematic for deep learning, where non-convex functions are pervasive.
3 Method
We consider a value function approach [see c.g., +ll 5 33 which yields natural first-order al- gorithms for non-convex 9 and requires no computation of Hessian matrices. It is based on the observation that ① is equivalent to the following constrained optimization (even for non-convex g):
min f(v, 8) s.t. q(v,0) g(v, 0) g" g0()) 00 0.0
(4)
where g²(x) ming g(v, 0) g (v)) is known as the value function. Compared with the hypergradient approach, this formulation does not require calculation of the implicit derivative V V.0" Although g (v) depends 0* (v), its derivative V.g" (v) does not depend on V,)"(v). by Danskin's theorem:
Veg'()) Vig(v, V.l" (v)) = = Vig(v, (v)),
(5)
where the second term in 5 vanishes because we have V2g(u, (o((,,0(v)) at each iteration, solving 4 yields algorithm for BO that requires no Hessian computation. In this work,
by definition of the
optimum (v). Therefore, provided that we can evaluate 0
(u) (*)
make of the dynamic
barrier gradient descent algorithm of Gong et al. [16] to solve 4. This is an elementary first-order algorithm for solving constrained optimization, but it applies only to a special case of the bilevel problem and must be extended to handle the general case we consider here.
Dynamic Barrier Gradient Descent. The idea is to iterative update the parameter (v, () to reduce while controlling the decrease of the constraint q, ensuring that decreases whenever > 0. Specifically, denote & as the step size, the update at each step
(ML+1, 0k+1) < (ux, 0k) Eōk:
(6)
where 8x = arg min [V(v,, 6112 s.t. (Vg(uk, 0n), 2 dx.
Here V == (f,, 0%). Vga == V (1. 0x), and oR 2 0 is a non-negative control barrier and should be strictly positive Ox > 0 the non-stationary points of q: the lower bound on the inner product of Vq(uk, 0&) and òr ensures that the update in (6) can only decrease (when step size is sufficiently small) until reaches stationary.
addition, by enforcing 5% be close f 0%) in ① we decrease the objective ff as much as possible so long as it does not conflict with descent of q.
Two straightforward choices of du that satisfies the condition above de vg(un, 02) and Φx 77 / (k, l1 with y7 > We find that both choices of Ob work well empirically and use 6k = 17 ( 0x)l as the default (see Section 6.2).
The optimization in yields simple closed form solution:
6x - V (V,,, 0x) + ( 0k), with d max Ø (V 0c), Vg(vk, Fg(pk,0x) 0). [Vg(v 0x)
and A in the case of [g(Uk, 0x)l = O.
Practical Approximation. The main bottleneck of the method above is to calculate the g(vk, 0x) and Vg(ek, 0x) which requires evaluation of 6" (vx). In practice, we approximate 0 (vx) by ((T). where (T) is obtained by running 7 steps of gradient descent of (( w.r.t. 0 starting from 0g. That is, we set of 0₁. and let
(++1 0 a Veg(te, (()). t t.....,
(8)
for some step size parameter a > We obtain an estimate of g(v, 0) at iteration & by replacing 8 (vw) with o ((v,0) g(v, 0) g(v,0 ((7)
3

---

Algorithm Bilevel Optimization Made Easy (BOME!)
Goal: Solve min,,9 f(e, 0) 0 arg min g(u,)).
Input: Initialization (No, Bo); inner step T; outer and inner stepsize &, a (set by default).
for iteration & do
1. Get (57) by T steps of gradient descent on g(vk: starting from 02 (See Eq.
2. Set q(u, 0) g(e, 0) g(v,0% )))
3. Update (v, 0) (U++1, 0k+1) (uk, 0k) - ((V 0k. Au Va( 0k))
ΦR (VS(u,, 0k), VG(uk, 0n)) 0
where λ
max
[VV 0x)1
and 0E 17)
//| VQ(Uk, 0s)l (default), or Φx = np(u:: (/1x:10) 0x) with 1) 1>>00 0.
Remark: 1) We treat (T) as constant when taking derivative of q: 2) In practice, step 3 can
have separate stepsize (Ev, Eo) and use standard optimizers like Adam [26] 3) We 17 0.5 and 10 by default.
end for
We substitute a 0z) into to obtain the update direction og. The full procedure is summarized in Algorithm Note that the o% viewed constant when defining q(v, 0) and hence no differentiation of o( is performed when calculating the gradient Vg. This differs from truncated back preek-rropgtiinn methods [c.g..H6] which differentiate through r it can be viewed plug-in estimator. We know that
as function v. Alternatiell,,
nn (Uk; 0&)
V Vo 0z) Vv.g(vk, 0" (vx))
= (VK, 02) [iig(on 0 (vx)) + V (vu) Vag(un,
(an)Ver 0" (vx))
Vung(uR, 02) Vig(UA, H* (vx)).
where V denotes taking the derivative w.r.t the first variable. Since 0 (vx) is unknown, we estimate Vig(en, 0* (vx)) by plugging-in o(7)) to approximate 0* (ex):
Vv, _(v,, O&) = V ((k, 0k) Vig(vs, 0 (vx:).
Each step of Algorithm 1 can be viewed as taking step (starting from ux 02) toward solving an approximate constrained optimization problem:
min [u, s.l. g(v,0) 0) S g(v ( v
which can be viewed as relaxation of the exact constrained optimization formulation {(u, 0): g(v, 0) & g" g0()} } is subset of {(v, 0): g(u, S g(v, e ))
because
Analysis
We first elaborate the KKT condition of 4 (Section then quantify the convergence of the method by how fast meets the KKT condition. We consider both the case when g satisfies Polyak-E.ojssiens (PL. inequality w.r.t. 0, hence having unique global optimum (Section 4.2) and when have multiple local minimum (Section
4.1 KKT Conditions
Consider a general constrained optimization of form min f(v, 0) s.t. g(v, 0) < O. Under proper
regularity conditions known constraint quantifications 40 the first-order KKT condition gives a necessary condition for a feasible point (v" 0*) with q(v", 0*)) S to be a local optimum of 4
There exists Lagrangian multiplier X [0, +0o), such that
vʃ(v", 0*) V 000) 0,
(10)
and x satisfies the complementary slackness condition X" X'g(v", ; 0*) = 0. A common regularity
condition to ensure I0) is the constant rank constraint quantification (CRCQ) condition 20]

---

Definition 1. A point (v", ) is said to satisfy CRCQ with function h if the rank of the Jacobian matrix Vh(v, is constant in a neighborhood of (u", ).
Unfortunately, the KKT condition in 10 does not hold for the bilevel optimization in 4.. The CRCQ condition does not typically hold for this problem. This is because the minimum of is zero, and hence if (v*, (*)) ) is feasible for 4 then (v", (0") must attain the minimum of q. yielding q(v", (*) = O and Vg(u". 8*) = 00 is smooth; but we could not have Vg(w, 0) = uniformly in neighborhood of (v", 8") (hence CRCQ fails) unless q is constant around (v* 0*). In addition, if KKT (1) holds, we would have vf(v", "f(x000) 0**) - Va(e", ,0) = 0 which happens only in the rare case when (u", 00)) ) stationary point of both f.g.
Instead, one can establish a KKT condition BO through the form in because there nothing special that prevents (u", 8*) from satisfying CRCQ with Veq Veg (even though just showed that it is difficult to have CRCQ with g). Assume and Veg are continuously differentiable, and
(u* 0*) is a point satisfying Veg(t", (0) and CRCQ with Vog. Then by the typical first order KKT condition of 33, there exists a Lagrange multiplier w" E IR" such that
f(w"", 0*) + v(Vog(v", 8 ))))" 0.
(11)
This condition can be viewed as the limit of a sequence of IC in the following way: assume we relax the constraint in 4 to q 0) S Cg where c is sequence of positive numbers that converge
to zero, then we can establish 10 for each C₁ > and pass the limit to zero to yield (II).
Proposition Assume that f. q, Vg are continuously differentiable and [I fll f is bounded. For feasible point (0",0") of 4 that satisfies CRCQ with Vag, if (0",8") is the limit of sequence {Vr, ==) satisfying q(v,, 0k) # Vk, and there exists a sequence {Ak} } C [0, oo) such that
Vf(vk, 0k) + NE Vglkk, 0k) + O.
q(vk, 0k) - 0,
as l + +00, then (v", 0*)) satisfies
This motivates to the following function measure of stationarity of the solution returned by the algorithm:
K(u. min VV 8) AVq(v, q(u,))
local impruveement
fcasibility
The hope is to have an algorithm that generates a sequence ((1), ] as h -> +00.
Tizo that satisfies K((nk, 0x) + 0
Intuitively, the first term in K(v, 0) measures how much V conflicts with Vg (how much we can decrease without increasing 4), as it is equal to the squared &a norm of the solution to the problem mins || f 8112 s.t. (Vq. d) 2 0. The second term in K. measures how much the arg min constraint is satisfied.
4.2 Convergence with unimodal, g
We first present the convergence rate when assuming g(u,)) -) has unique minimizer and satisfies the (PL) inequality for all v, which guarantees a linear convergence rate of the gradient descent on the low level problem.
Assumption 1 (PL-inequalityy. Given any v, assume g(v,) -) has unique minimizer denoted as 0* (u). Also assune there exists & > 0 such that for any (v, 0), [VVg, 0)11² Z k(g(v, -gr, 0" (v))).
The PL inequality gives a characterization on how a small gradient norm implies global optimality. It is implied from, but weaker than strongly convexity. The PL-inequality is more appealing than convexity because some modern aver-parameterized deep neural networks have been shown to satisfy the PL-inequality along the trajectory of gradient descent. See, for example, Frei and Gu [ al.
Song
48
Liu et al. 30 for more discussion.
Assumption (Smoothness). f and g are differentiable, and f and g are L-Lipschitz w.r.t. the joint inputs (v, 0) for some L E (0, +00).
5

---

Assumption (Boundedness), There exists a constant M < oo such that [V |I (v, [f(u, and Ig(v,6) 8) are all upper bounded by M for any (v, 8).
Assumptions 2 and 3 are both standard in optimization.
Theorem 1. Consider Algorithm with &. a S 1/L, ΦR = VVVVVv( 0x)l and > 0. Suppose that Assumptions 2 and 3 hold. Then there exists constant depending a, K. 7. L such that when T 2 G, we have for any K 2 O,
min K(Uk, 0k) = (VE+ KSK
1
+ texp(
V
EK
where go = q(v,, Bu), and is a constant depending on K. L, and a.
Remark Note that one of the dominant terms depends on the initial value qu = g(v6, 0n). Therefore,
can obtain better rate if we start from O, with small go (hence near the optimum of g(v; -). In
particular, when (tin fn) ( choosing Ç O ([(K)//) gives min&g K[ 0&x O(K-1/4_ +/4+ (xp(-bt)) rate. On the other hand, if we start from a better initialization such that ((v, 00) = O((EK)-)). ), then choosing { = O gives ming< K[(n,, 0x) = O(K 113 + exp( DT)).
4.3 Convergence with multimodal
The PL-inequality eliminates the possibility of having stationary points that are not global optimum. To study cases in which y has multiple local optima, we introduce the notion of attraction points following gradient descent.
Definition (Attraction points). Given any (v. 0). we say that (v, 0) is the attraction point of (v. 0) with step size a > if the sequence (0 generated by gradient descent ((t) @(l-1) Vog(v, (((-1)) starting from ((0) 0 converges to (v, 0)-
Assume the step size a S. I/L where L is the smoothness constant defined in Assumption 2 one can show the existence and uniqueness of attraction point of any (v, 0) using Proposition Traonmilin and Aujol 499. Intuitively, the attraction of (u, f) is where the gradient descent algorithm
of
not make improvement. In fact, when < 1/L, can show that g 0) g(v, 8 (0, 0)) is equivalent to the stationary condition Veg(v.6)
The set of (v. 0) that have the same attraction point forms an attraction basin. Our analysis needs to assume the Pl-inequality within the individual attraction basins.
Assumption 4 (Local PL-inequality within attraction basins). Assume that for any (v, 0). (u,
exists. Also assume that there exists 0 such that for any (v, O) |I VVog(v, 0)11² 2 k(g(v,0) g(v, 0 (v, (v,0), 0)).
We can also define local variants of and IC as follows:
qº (v. 0) g(v, 0) g(v, (v, 0)), (c, 0) min VV (V, + (v, X20
Compared with Section 4.2 a key technical challenge that (v, 0) and hence (v, 0) can be discontinuous w.r.t. 9 when it is on the boundary of different attraction basins; K is not well defined on these points. However, these boundary points are not stable stationary points, and it is possible to arguments based the stable manifold theorem to show that an algorithm with random initialization will almost surely not visit them 27]
Theorem 2. Consider Algorithm I with a S 1/L, di = (V Oz)l and 17 > O. Suppose (ug, 0z) at every iteration k 2 O.
that Assumptions 2 and 4 hold and that d is differentiable Then there exists a constant c depending on ac, 16, 17, L, such that when T 2 c, we have
(VE+
VE +exp(-bT)
min 1C 1C 0v) kSK
VEK
V
EK
where b is a positive constant depending on K, L, and
Unlike Theorem [ the rate does not improve when qf : 9 (vp. 0v) is small because the attraction basin may change different iterations, eliminating the benefit of starting from good initialization. Choosing (KK3 gives OKK-1/1 exp(-bT)) rate of ming<K K XC (v,, (v,,0,) 0z).

---

5
Related Works
The value- finutinn formulation
How- ever, despite its attractive properties, it has been mostly used as a theoretical tool, and much less exploited for practical algorithms compared with the more widely known hypergradient approach (Section 2) especially for challenging nonconvex functions f and such as those encountered deep learning. One exception is Liu et al. [33] which proposes BO method by solving the value-function formulation using an interior-point method combined with a smoothed approximation. This was improved later in pessimistic trajectory truncation approach [55] and a sequential minimization approach 34 (BVFSM). Similar to our approach, these methods do not require computation of Hessians, thanks to the use of value function. However, as we observe in experiments (Section 6.2). BVFSM tends to be dominated by our method both in accuracy and speed, and is sensitive to some hyperparameters that are difficult to tune (such as the coefficients of the log-barrier function in interior point method). Theoretically, Liu et al. Bs 34 351 convergence of the smoothed and penalized surrogate loss to the target loss. They do not give an analysis for the algorithm that was actually implemented.
4 is classical approach in bilevel optimization 4 3
provide only asymptotic analysis on the
Our algorithm is build up on the dynamic control barrier method of Gong al. 16 an elementary approach for constrained optimization. Gong et al. [6]] also applied their approach to solve a lexico- graphical optimization of form ming (() s.t. 0 arg ming: g(0",, which is bilevel optimization
without an outer variable (known as simple bilevel optimization [8] (M). Our method is an extension
of their method to general bilevel optimization. Such extension is not straightforward, especially when the lower level problem is non-convex, requiring introducing the stop-gr stop-gradient operation in a mathematically correct way. We also provide mon-atymptoiic analysis for our method, that goes beyond the continuous time analysis in Gong et al. [16]. A key sophistication in the theoretical analysis is that need control the approximation error of 0* (*x)) with of4h) each step, which requires an analysis significantly different from that of Gong et al. [[6]. Indeed, non-asy msptootii results have not yet been obtained for many BO algorithms. Even for the classic hypergradient-
approach (such results are established only recently in Ji et al. (22)). We believe that we are the first to establish a aonmasymttoiic rate for a purely first-order BO algorithm under general assumptions, e.g. the lower level problem can be both convex or non-convex.
Another recent body of theoretical works BO focus how to optimize when only stochastic approximation of the objectives is provided [4] 19 22
18 25]; there are also recent works on the lower bounds and minimax optimal algorithms 21 22 These algorithms and analysis based
51
on hypergradient descent and hence require Hessian-vector products in implementation.
Experiment
We conduct experiments (1) to study the correctness, basic properties, and robustness to hyperpa- rameters of BOME, and (2) to test its performance and computational efficiency on challenging ML applications, compared with sate-of-the--al bilevel algorithms. In the following, we first list the baseline methods and how we set the hyperparameters. Then we introduce the experiment problems in Section I. which includes 3 toy problems and 3 ML applications, and provide the experiment results. Finally we summarize observations and findings in Section 6.2
Baselines A comprehensive set of state-of-the-art BO methods are chosen as baseline methods. This includes the fully first-order methods: BSG-1 [5] and BVFSM (34 stationary-seeking method:
Penalty [39]. explicit/implicit methods: ITD 22 AID-CG (using conjugate gradient), AID-FP
(using fixed point method) [17 reverse (using reverse auto-differentiation) stocBiO 22 and
VRBO [5I].
Hyperparameters Unless otherwise specified, BOME strictly follows Algorithm I with Φx " ( 0,) 1) 0.5, and T 10. The inner stepsize is set to be the same as outer stepsize g. The stepsizes of all methods are set by a grid search from the set {0.01, 0.05, 0.1, 0.5, 1, 5, 10, 50, 100, 500, 10003. All toy problems adopt vanilla gradient descent (GD) and applications on hyperparameter optimization adapts GD with a momentum of 0.9. Details are provided in Appendix A
7

---

comparison
[b) v.s. train step
[0] v.s. train step
(c) 1y (0.1,0.5,033 0.9)
T {1, 100)
strt
Duter snjectuu
Far 2000 200
506
Outer cloecive
vo 103
ming steps
Tatning
BOME (purs)
BVFSM
BSG-1
Ponalty
BOMEI
BOME
0.1
0.5
0.9
10
100
Optimistic
solution
Startlend of trajectory
Figure Results on the toy coreset problem and mini-max problem. (a)-(c): the trajectories of
(Ug, 0z). and f(V,, 2g) and éx (2k, v&) of BOME (our method), BSG-1 (TS]. BVFSM [4]. Penalty B9 and Optimistic GD [5] (only for minimax problem). (d)-(c) trajectories of BOME with different
choices of inner gradient step T and the control coefficient 77.
6.1 Experiment Problems and Results
Toy Coreset Problem To validate the convergence property of BOME, we consider:
min., |10 =oll² s.l. E arg ming |10' - Xo(vv)l"
where a(u) exp(v)/ Σi= exp(r;) the softmax function,
RT,0 R.2, and
[21, 22, 33, T34 _2x4 The goal is find the closest point to target point xo within the convex hull of (Z1,...,I.) FzJ. . See Fig. 6. (upper row) for the illustration and results.
Toy Mini-Max Game Mini-max game is special and challenging case of BO where f and g contradicts with each other completely (e.g., f -g). We consider
min vA s.t. 0 E arg maXgres v0'.
(12)
The optimal solution is v* = l" O. Note that the naive gradient descent ascent algorithm diverges to infinity on this problem, and standard alternative is (lower row) shows that BOME works on this problem while other first-order BO methods fail.
optimistic gradient descent [5]. Figure 6.]
Degenerate Low Level Problem Many existing BO algorithms require the low level singleton (LLS) assumption, which BOME does not require. To test this, we consider an example from Liu et al. 33
min |00 [e: 1112 s.t. 0 E arg min (00000000)) (e) =))
where (01, 02) and the solution v" 1 11. See Fig.
Appendix A.3 for the result.
Data Hyper-cleaning We are given a noisy training set Dtrain == {az ys ) and a clean validation set D The goal is optimally weight the training data points so that the model trained on the weighted training set yields good performance on the validation set:
(0), s.t. arg ming { (arinn (0', + +cc1011]]
minn.
where geal is the validation loss on D and train is a weighted training loss: errain Em (v:)) Vi,0) 0) with (v) = Clip(v. (0, 1]) and
Im.. We set 0.001. For the dataset, we use MNIST [9] (FashionMNIST (5)). We corrupt 50% of the training points by assigning them randomly sampled labels. See Fig. (upper panel) for the results. (Results for FaShionMNIST are reported in Appendix AA.4)
Learnable Regularization We apply bilevel optimization to learn the optimal regularization coeffi- cient on the twenty newsgroup dataset
min, gral s.t. 0 E arg ming. { (mrin (0') + ||
Dataset from
htt.:///ww.....a.aa.a/aaaaaaetta html

---

BOME (7' 1)
BVFSM
Penalty
ITD
BSG_1
stocBIO
(d) Ablation study on
BT 20)
VRBO
AID CG
AID FP
reverse
(a) Test loss v.s. Time
(b) Test loss v.s. T
[c] Time v.s. v.s.T
71 00
Time Comsum most (wec.)
Hyper- see--ciannnng
Tec Lods
Data
0.20
Inner Loop Itcrations
Loop ttenet ons
Time conoumptoon (otc)
Regularization
Learnable
Test Uoss
3423
2750
639
045
Training Time (oot.)
Inner InnerLoop Itaaaiins
Inner Loop tteraions
060
11
08
184 964
15:05
data hyper-cleaning on MNIST dataset. The solid black line is the model performance trained purely on the validation set and the dashed black line is the model performance trained on the validation set and on the part of training set that have correct labels. Bottom: learnable regularization on 20 Newsgroup dataset. The solid black line indicates the model performance without any regularization. All results are averaged on random trials. See Appendix A.4 and A.5 for results MNSTI and more details.
Figure 2: Result for hyperparameter optimization. Top:
PMNIST
Split CIFAR
Method
ACC (t)
NBT (U)
FT (t)
ACC (t)
NBT (L)
FT (t)
Offline
84.95 = 0.95
74.11 :: 0.66
MER
76.59 + 0.74
5.73 + 0.59
82.32
0.34
60.32 + 0.86
8.91 0.86
69.23 0.40
CTN (+ITD)
78.40 + 0.28
5.62 4: 0.39
84.02 + 0.29
67.7 + 60.96
4.88 + 0.77
72.58 + 0.62
CTN (+BVFSM)
77.78 0.32
7.25
0.28
85.03 0.28
07.04 + 0.76
0.62
74.01
CTN (+BOME)
80.70 = 0.26
4.09 0.27
84.79 + 0.25
68.16 + 0.60 4.72 + 0.75
72.88 0.48
Table 1: Results of continual learning as bilevel optimization. We compute the mean and standard error of each method's results over 5 independent runs. Best results are bolded. The full result with comparison against other methods are provided in Table in the Appendix.
where W, is a matrix depending on v, c.g., W, = diag(exp(v)). See Fig. 2 (lower panel) for results.
Continual Learning (CL) CL studies how to learn on sequence of tasks in an online fashion without catastrophic forgetting of previously learned tasks. We follow the setting of contextual transformation network (CTN) from Pham et al. 4 which trains a deep neural network consisting of quickly updated backbone network (parameterized by 0) and a slowly updated controller network (parameterized by v). When training the 7-th task, we update (v, 0) by
ming,
C (v. 0) s.t.
arg ming
grrai (v, 0'),
where grain and eyal are the training and validation loss available up task T. The goal update the controller such that the long term loss Cyal is minimized assuming 0 is adapted to the available training loss when new tasks come, Assume the CL process terminates at time Denote by o the test accuracy of task s after training on task т. We measure the performance of CL by 1) the final mean accuracy on all seen tasks (ACC = EEgrap az), 2) how much the model forgets as measured by negative backward transfer NBT = E - a.)). and 3) how fast the model learns on new tasks as measured by forward transfer FT ETsr oF. Note that FT +CC NBT.
We follow the setting of Pham et al. 2 closely, except replacing their bilevel optimizer (which is essentially ITD (2) with BOME. See Appendix(A.6))
experiment details. The results are shown in Table I where in addition to the bilevel algorithms, we also compare with set of fate-offtthe-at CL algorithms, including MER 45), ER [ and GEM [Md) Table I also includes an "Offline" basline- learning tasks simultancously using single model (which is the upper bound on performance).

---

6.2 Observations
BOME yields faster learning and better solutions at convergence Figure 6.1 show that BOME converges to the optimum of the corresponding bilevel problems and work well on the mini-max optimization and the degenerate low level problem; also Fig B in Appendix A. In comparison, the other methods like BSG-1, BVFMM, and Penalty fail to converge to the true optimum even with a grid search over their hyperparameters. Moreover, in all three toy examples, BOME guarantees that q. which is a proxy for the optimality of the inner problem, decreases to O. From Fig. 2 that BOME achieves comparable or better performance than the state-of-the-art bilevel methods for hyperparameter optimization. Moreover, BOME exhibits better computational efficiency (Fig. 2
it is observed
especially on the twenty newsgroup dataset where the dimension of 0 is large. In Table [
find that directly plugging in BOME to the CL problem yields a substamtial performance boost.
Robustness parameter choices Besides the standard step size & in typical optimizers, BOME only has three parameters: control coefficient 7, inner loop iteration T, and inner step size a. We use the default setting of 7 = 0.5, = 10 and a = { across the experiments. From Fig. 6.1 (d.e) and Fig. 2 (b.d). BOME is robust to the choice of 17. T and a varying them results in almost identical performance. Specifically, T = 1 works well in many cases (see Figure 6. (e) and 2 (b). The fact that BOME works well with small I' empirically makes it computationally attractive in practice.
Vi("). 0x 0x) by default. Another option is use o2 = 7 Uk. 0x). We test both options on the data hyper-cleaning and learnable regularization experiments in Fig. 2 (d), and observe no significant difference (we choose v) properly so that both choices of Φx is on the same order). Hence we use dh [V I=l as the default.
Choice of control barrier Φb The control barrier is set as 02
Comparison against BVFSM The most relevant baseline BOME is BVFSM, which similarly adopts the falueffunction reformulation of the bilevel problems. However, BOME consistently outperform BVFSM in both converged results and computational efficiency, across all experiments. More importantly, BOME has fewer hyperparameters and is robust to them, while we found BVFSM is sensitive to hyperparameters. This makes BOME a better fit for large practical bilevel problems.
7 Conclusion and Future Work
BOME, simple fully first-order bilevel method, proposed in this work with non-asymptotic convergence guarantee. While the current theory requires the inner loop iterations to scale in logarithmic order w.r.t to the outer loop iterations, we do not observe this empirically. A further study to understand the mechanism is an interesting future direction.
8 Acknowledgement
The research was conducted in both the statistical learning and AI group (SLAI) led by Qiang Liu and the Learning Agents Research Group (LARG) led by Peter Stone in computer science UT Austin, SLAI research is supported in part by CAREER-184666 884421,, SenSE-2037267. Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML). LARG research is supported in part by NSF 18-2243), ARO (W91 INF- 19-N-119--03333 DARPA, GM, Bosch, and UT Austin's 's Good Systems grand challenge. Peter Stone serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy objectivity in research.
BAGER-204133 2041327, and
172417,, FAIN-2019844), ONR (N00014-
References
[1] Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:2111.14580 2021.
[2] Jonathan F Bard. Practical bilevel optimization: algorithms and applications, volume 30. Springer Science & Business Media, 2013.
[3] Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Marc' Aurelio Ranzato. On tiny episodic memories in continual learning. arXiv preprint
2019.
10

---

[4] Tianyi Chen, Yuejiao Sun, and Wotao Yin. A -igeeell stochastic bilevel optimization method. arXiv preprint arXiv:2102.0467/ 2021.
[5] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: 2017.
[6] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
[7] Stephan Dempe and Alain Zemkoho. Bilevel optimization. Springer, 2020.
[8] Stephan Dempe, Nguyen Dinh, Joydeep Dutta, and Tanushree Pandit. Simple bilevel program- ming and extensions. Mathematical Programming, 188(1):22--253, 2021.
[9] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 2012.
[10] Nguyen Dinh, B Mordukhovich, and Tran TA Nghia. Subdifferentials of value functions and optimality conditions for de and bilevel infinite and semi-infinite programs. Mathemattcall Programming, 123(1):101-138, 2010.
[11] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 165--1173 PMLR, 2017.
[12] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. International Conference Machine Learning, pages 1568-1577. PMLR, 2018
[13] Spencer Frei and Quanquan Gu. Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
[14] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246 2018.
[15] Tommaso Giovannelli, Griffin Kent, and Luis Nunes Vicente. Bilevel stochastic methods for optimization and machine learning: Bilevel stochastic descent and darts. arXiv preprint arXiv:2110.00604, 2021.
[16] Chengyue Gong, Xingchao Liu, and Qiang Liu. Automatic and harmless regularization with constrained and lexicographic optimization: A dynamic barrier approach. Advances in Neural Information Processing Systems, 34, 2021.
[17] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference Machine Learning, pages 3748-3758. PMLR, 2020.
[18] Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochas- tic bilevel optimization. arXiv preprint arXiv:2105.00 02266, 2021.
[19] 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 0rXiv:2007.05170. 2020.
[20] Robert Janin. Directional derivative of the marginal function in nonlinear programming. In Sensitivity, Stability and Parametric Analysis, pages 110-126. Springer, 1984.
[21] Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.03926 2021.
[22] Kaiyi Ji, Junjie Yang. and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMIR, 2021.

---

[23] Haoming Jiang, Zhehui Chen, Yuyang Shi, Bo Dai, and Tuo Zhao. Learning to defend by learning to attack. In International Conference on Artificial Intelligence and Statistics, pages 577-585. PMLR, 2021.
[24] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the tojassawaja condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-8 Springer, 2016.
[25] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. arXiv preprint arXiv:2102.00336 2021.
[26] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
[27] Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pages 1246-1257. PMLR, 2016.
[28] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint arXiv:2 / 12.04660. 2021.
[29] Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent back- propagation. In International Conference on Machine Learning, pages 3082-3091. PMLR, 2018.
[30] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Compulational Harmonic Analysis, 2022.
[31] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, pages 6305 6315. PMLR, 2020.
[32] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from a unified perspective: survey and beyond. arXiv preprint arXiv:2101. 2021.
[33] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A celuu-funnction-aee interior-point method for non-convex bi-level optimization. arXiv preprint ar0iv:2206.60 10.90799, 2021.
[34] Risheng Liu, Xuan Liu, Shangzhi Zeng. Jin Zhang, and Yixuan Zhang. falue-function-bae based sequential minimization for bi-level optimization. arXiv preprint arXiv:2110.04974, 2021.
[35] Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based based bilevel opti- mization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34, 2021.
[36] David Lopez- Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances neural information processing systems, 30:6467-64777 2017.
[37] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[38] Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv: 1e0.. 2019.
[39] Akshay Mehra and Jihun Hamm. Penalty method for inversion free deep bilevel optimization. In Asian Conference on Machine Learning, pages 347-362. PMLR, 2021.
[40] Jorge Nocedal and Stephen Wright, Numerical Optimization. Springer Science & Business Media, second edition, 2006.
12

---

[41] Jivrí V Outrata. On the numerical solution of a class of stackelberg problems. Zeitschrift für Operations Research, 34(4):255-277, 1990.
[42] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference machine learning, pages 737-746. PMLR, 2016.
[43] Quang Pham, Chenghao Liu, Doyen Sahoo, and HOI Steven. Contextual transformation net- works for online continual learning. In International Conference on Learning Representations, 2020.
[44] Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients. 2019.
[45] Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Ger- ald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv: /810. /9/00 2018.
[46] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[47] Michael Shub. Global stability of dynamical systems. Springer Science & Business Media, 2013.
[48] Chaehwan Song, Ali Ramezani-Kebrya Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameterization for shallow neural networks, Advances in Neural Information Processing Systems, 34, 2021.
[49] Yann Traonmilin and Jean-Fraad Can-Francciss Aujol. The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem. Inverse Problems, 36(4):045003, 2020.
[50] Han Xiao, Kashif Rasul, and Roland Vollgraf. Rashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint atXiv:1708007745 2017.
[51] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. arXiv preprini arXiv: 206.0:2006..4622,, 2021.
[52] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. 2019.
[53] and DL Zhu, Optimality conditions for bilevel programming problems. Optimization, 33
(1):9-27, 1995.
13

---

Societal Impacts
This paper proposes a simple first order algorithm for bi-level optimization. Many specific instanti- ation of bi-level optimization such as adversarial learning and data attacking might be harmful to machine learning system in real world, a general optimization algorithm for bi-level optimization, our method can be a tool in such process. We also develop a great amount of theoretical works and to best knowledge, do not observe any significant negative societal impact of our theoretical result.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Ys]], [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/anssers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
14

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "Txjehbjg1rU", "reviewer": "Reviewer_RuUT", "summary": "The authors present a first-order smooth bilevel optimization algorithm that avoids implicit differentiation, instead using a value function to reduce the problem to a single level constrained optimization problem. The single level problem is solved by a so-called dynamic barrier gradient descent algorithm, which notably does not require the lower level problem to have a unique solution. Convergence guarantees are proven for the algorithm and numerical experiments are reported on several different examples, confirming the theoretical results and suggesting that the algorithm performs favorably in practice.", "questions": "In line 113, where it's explained that theta T is treated as constant despite depending on v, how is this justified? Even if you had a global minimizer theta star instead of the approximation, it would still depend on v, so it's unclear if this works.\n\nIn line 44, what is meant by powerful BO method?\n\nIn line 82 and line 107, if the lower level problem is nonconvex then what is meant by theta star?\n\nIn line 138, should it be CRCQ instead of CRCO?", "limitations": "I think the paper has done a good job explaining the limitations of its contributions, which are primarily theoretical analyses, by clearly stating the assumptions needed to apply the theorems.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the paper to be generally well written and clear, save for a few small typos that otherwise don't affect the arguments, and I appreciated that the assumptions on the functions and problem settings were clearly stated, adding to the quality of the paper. \n\nWhile the idea of using a value function in bilevel optimization to reduce the problem to a single level optimization problem isn't original per se, the algorithm and analysis here seem original and significant to the best of my knowledge, particularly the convergence rate for the case where the lower level solution is not unique. The analysis given doesn't require necessarily the uniqueness of the minimizer for the lower level problem, which makes the algorithm more broadly applicable than many other bilevel optimization algorithms, adding to the significance of the paper.\n\nThere were a lot of different problems considered in the applications section and the results were fairly convincing, although I think that in the examples which admit a unique minimizer for the lower level problem it would be interesting to compare to AmIGO as well.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NV6dxEZGV2z", "reviewer": "Reviewer_67cV", "summary": "The paper studies the bilevel optimization with unique inner solution, proposed the algorithm that utilizes the dynamic barrier gradient methods, theoretically captures the convergence rate of the proposed algorithm, and implemented plenty of numerical simulations to ensure the validity of the proposed algorithm.", "questions": "Since we do not have the access to the second order information of $\\nabla^2 g(v, \\theta)$, do we implicitly approximately computed the inverse of Hessian?", "limitations": "It would be better if the authors provide more intuition on how the convergence rate is derived.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is convincing that it provides various numerical simulations that verifies the validity of the algorithm, and it also provides the convergence rate, not just asymptotic guarantee.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KJUSrkBFyzu", "reviewer": "Reviewer_DoMn", "summary": "This paper proposes a first-order bilevel algorithm which updates only based on first-order gradient information. The author provides convergence analysis for such algorithm and conducts different experiments to demonstrates its superior performances across different settings.", "questions": "1. It will be better to have a discussion about the comparison between convergence results of proposed algorithm and other benchmarks (e.g. AID, ITD, VRBO). \n\n2. In terms of experiments, it will be better to include several stochastic algorithms, e.g. (SUSTAIN [24], StocBiO [21])         \n for comparison to check if BOME ranks top among these algorithms.\n\n3. The continual learning experiments (Table 1) do not show the superior performances of BOME compared with BVFSM. However, in Section 6.2, the author still claims that \"BOME outerforms BVFSM across all experiments\". \n\n4. In Line 290, the author states that FT=ACC+NBT. However, the results in Table 1 do not support such states. Any possible explanation?\n\n", "limitations": "Non negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In terms of strengths, it is interesting to use value function approach to avoid Hessian computation in bilevel optimization. Such design helps to reduce the computational cost. Proposed algorithm has been demonstrated in various settings. In general, this paper is well written and presented. \n\nIn terms of weakness, the convergence result is not standard (not in gradient norm form) which make it hard to compare such result with other benchmarks. In experiments, all algorithms have adopted GD to update while some algorithms (e.g. VRBO) is designed for update stochastically. It will be better to involve stochastic algorithms for comparison. In continual learning experiment, CTN (+BOME) does outperform CTN (+BVFSM).", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AoScuwzWUfH", "reviewer": "Reviewer_wdMq", "summary": "This paper proposes a fast bi-level optimization (BO) algorithm, that only involves the calculation of the first-order gradient. The proposed method is built on the value-function approach, and integrated the dynamic barrier gradient descent algorithm into the new BO algorithm, which helps solve the BO problem more efficiently. The proposed method is a fully first-order method and the authors also establish the non-asymptotic convergence analysis for the proposed method. Experiments on toy examples as well as real deep learning tasks are conducted to demonstrate the effectiveness of the proposed method.", "questions": "Please address the comments and questions above in the \"weakness\" column.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical Analysis: The convergence analysis for the proposed method is indeed one contribution to the bi-level community. The discussion on the condition of the lower-level objective $g$ is also remarkable. I understand when $g$ has multiple local minima, the analysis could become very tricky. Therefore, the introduction of the attraction points is very impressive.\n\n2. Presentation: This paper is well-organized, straight forward and in general very easy to follow. I have no difficulty in grasping the main idea as well as the technical details of the proposed method.\n\nWeakness:\n\n1. Novelty: In general, I think the novelty of this paper is less significant and incremental. Firstly, the value function based bi-level optimization algorithm is well studied and known to not require the computation of the Hessian matrix. Secondly, as the authors mentioned in the paper for several times, the core algorithm used in the proposed method \"Dynamic Barrier Gradient Descent\" is an existing approach. The authors have yet to convince me that the integration of a proposed method is significant enough. The authors should make the difference between the proposed method and the existing method more distinctive, or discuss the essential difference between these two methods.\n\n2. Experiments: The authors claim that their method is good at large-scale practical deep learning tasks. However, the current experiments all seem to be far away from \"large-scale\". Therefore, the authors are suggested to design some larger scale experiments to verify their argument. The current results all look good to me. \n\n3. The authors are also suggested to do an additional experiments on the few-shot meta-learning tasks, since this task is very widely accepted as one experiment to examine the feasibility of a BO method. \n\n4. Regarding the hyper-parameters, the author claim that \"BOME is robust to the choice of $\\eta$, T and $\\alpha$ as varying them results in almost identical performance\". I think this is counter-intuitive, since more inner steps T generally indicates a better lower-level solution, closer to the stationary point, which could lead to possible better results. Further, why do you choose $\\eta=0.5$? Is there any logics behind this?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept