Non-Convex Bilevel Games with Critical Point Selection Maps
Authors: Michael Arbel
Julien Mairal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bilevel Optimization
Morse theory
gradient flows
Lojasiewicz gradient inequality

Abstract: Bilevel optimization problems involve two nested objectives, where an upper-level objective depends on a solution to a lower-level problem. When the latter is non-convex, multiple critical points may be present, leading to an ambiguous definition of the problem. In this paper, we introduce a key ingredient for resolving this ambiguity through the concept of a selection map which allows one to choose a particular solution to the lower-level problem. Using such maps, we define a class of hierarchical games between two agents that resolve the ambiguity in bilevel problems. 
This new class of games requires introducing new analytical tools in Morse theory to extend implicit differentiation, a technique used in bilevel optimization resulting from the implicit function theorem. In particular, we establish the validity of such a method even when the latter theorem is inapplicable due to degenerate critical points.
Finally, we show that algorithms for solving bilevel problems based on unrolled optimization solve these games up to approximation errors due to finite computational power. 
A simple correction to these algorithms is then proposed for removing these errors.

Non-Convex Bilevel Games with Critical Point Selection Maps
Michael Arbel and Julien Mairal
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France firstname. Jastname@inria.fr
Abstract
Bilevel optimization problems involve two nested objectives, where an upper-level objective depends on a solution to a lower-level problem. When the latter is non- convex, multiple critical points may be present, leading to an ambiguous defini- tion of the problem. In this paper, we introduce a key ingredient for resolving this ambiguity through the concept of selection map which allows one to choose a particular solution to the lower-level problem. Using such maps, we define a class of hierarchical games between two agents that resolve the ambiguity in bilevel problems. This new class of games requires introducing new analytical tools in Morse theory to extend implicit differentiation, technique used in bilevel opti- mization resulting from the implicit function theorem. In particular, we establish the validity of such method even when the latter theorem is inapplicable due to degenerate critical points. Finally, we show that algorithms for solving bilevel problems based on unrolled optimization solve these games up to approximation errors due to finite computational power. A simple correction to these algorithms is then proposed for removing these errors.
1 Introduction
Bilevel optimization has proven to be major tool for solving machine learning problems that pos- sess a nested structure such as hyper-parameter optimization [17], meta-learning [6], reinforcement learning [23, 33], or dictionary learning [38]. Introduced in the field of economic game theory in [49], bilevel optimization problem can be understood as game between leader and follower each which optimizes their own objective function but where the leader can anticipate follower's actions. In the context of machine learning, the leader typically optimizes hyper-parameter validation loss while the follower optimizes the model parameter on training loss [37].
Bilevel optimization introduces many challenges. In particular, when multiple optimal solutions are available to the follower, the leader would need to optimize a different objective depending on the follower's strategy select optimal solution. As result, the bilevel problem becomes am- biguously defined without knowing the follower's strategy [35]. A large body work on bilevel programs for machine learning gets around these considerations by assuming the follower to have a unique optimal choice, a situation that typically occurs when the follower's ' objective is strongly convex, leading to efficient and scalable algorithms [1. 2, 7, 14, 20, 32, 33, 47]. However, in many machine learning applications, the strong convexity of the follower's objective is an unrealistic as- sumption. This is particularly the case in the context of deep learning, where the follower's objective, the training loss, can be highly non-convex in the parameters of the model and can have regions of flat optima due symmetries and other degeneracies [15.
In the literature on mathematical optimization, the ambiguity in bilevel problems often resolved by making additional assumption on the follower's 's strategy for choosing their optimal solution. In particular, two problems are often considered: optimistic and pessimistic bilevel programs, see [13].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Both problems rely on two assumptions: (i) the follower is using a strategy for selecting solution to their problem that is either improving or degrading the leader's objective and (ii) the leader knows exactly what strategy the follower is using. These assumptions are strong from a game-theoretica perspective and often unrealistic for machine learning problems such as hyper-paramen tion. Still, oprimistic/pessimisti bilevel games are well defined and early works have proposed several algorithms to solve them with strong convergence guarantees [55, 56, 57J. Yet. these algo- rithms are often ill-suited to large-scale and high-dimensional problems arising in machine learning applications as they rely on second-order optimization methods such as Newton's 's method [21]. For this reason, scalable first-order algorithms for such games have been proposed recently [34, 35].
optimiza-
However, many of the best- best-perfonning approaches for pyper-paramedt optimization rely neither on an optimistic nor pessimistic formulation of the bilevel problem [50]. Instead, they often rely on algorithms initially designed for bilevel problems with strongly convex lower objectives even though the convexity assumption does not hold [37]. Consequently, these algorithms are solving a seemingly ill-defined bilevel program due to the ambiguity in the way the follower selects their solu- tion. However, their ability to provide models with good empirical performance raises the question of whether these algorithms are solving another class of well-defined hierarchical problems beyond optimistic and pessimistic bilevel programs that are still relevant for machine learning.
In this work, we answer the above question by introducing Bilevel Games with Selection (BGS), a class of games between two agents: a leader and follower, where the leader uses mechanism for anticipating the solution of the follower without knowing the exact follower's strategy. We define such a mechanism using the notion of selection, which is simply map for selecting particular solution to the follower's objective given the current state of the game. In particular, BGS recovers a usual bilevel program when the follower's ' objective admits unique solution. By playing a BGS, the agents seek an equilibrium point for which each of their objectives ceases to vary. The equilibria are completely determined by the selection thus resulting in a well-defined problem.
When the selection is differentiable, the equilibrium point can be characterized by first-order op- timality condition which enables gradient-based based approximations. More precisely, we show that implicit differentiation [42], which, a priori, only valid when the critical points of the follower's objective are non-degenerate, remains applicable for solving BGS even when these critical points are degenerate. To this end, we consider general construction of the selection as the limit of a gradient flow of the follower's objective and prove the differentiability of such a selection near local minimizers, provided the follower's objective satisfies generalization of the Morse-Bow Bott property [4, 16]. We then characterize the differential of the selection solution to a linear system thus extending implicit differentiation to degenerate critical points. Finally, we leverage this characteri- zation to show that popular algorithms based on iterative differentiation (ITD) [5] find fixed points approximating the BGS's equilibria up to approximation errors. We then introduce a simple correc- tive term to these algorithms based on implicit differentiation to remove these errors.
2 Related Work
Iterative/Unrolle optimization (ITD) is a class of methods approximating the lower-level solu- tion map by a differentiable function obtained through successive gradient updates [5]. When the lower-level objective is strongly convex, these algorithms solve a well-defined bilevel problem up to an error that is controlled by increasing the computational budget for the approximate solution [25]. Our analysis suggests a simple algorithmic correction to these approaches which can result in solu- tions to bilevel game with constant budget for the approximate solution.
Approximate Implicit Differentiation (AID) is class of methods approximating the variations of the lower-level solution map using the Implicit Function theorem [18, 19, 42, 43]. The non- degeneracy requirement under which the latter theorem holds restricts the applicability of AID to, essentially, strongly convex lower-level objectives. These algorithms admit fixed points that match the solutions to the bilevel problem [19, 23, 24, 25]. As such, they typically require a smaller computational budget than ITD [2, 25]. Recently, [8, 10, 9] extended AID to non-smooth objectives while still requiring non-degenerate critical points. The present work is complementary these works as it extends AID to smooth objectives that have possibly degenerate critical points.
Optimistic and pessimistic bilevel optimization. When the lower-level objective is non-convex, the ambiguity of the problem arising from the multiplicity of the lover-level solutions can be re-
2

---

solved by optimizing the upper-level objective over all such possible solutions [53, 58]. The opti- mistic and pessimistic problems arise when either minimizing or maximizing the upper-level over all such lower-level solutions. Early works proposed to solve these problems using exact penalization [57], second-order optimization [55, 56] or smoothing method [54]. However, these approaches are hard to scale to the high dimensional problems arising in machine learning. More recently, [35, 34] considered first-order methods based on unrolled optimization or interior-point methods for solving optimistic bilevel problems and provided approximation guarantees. However, as shown in [50], most practical applications to bilevel optimization rely on a formulation that goes beyond optimistic or pessimistic formulations. The present work departs from these approaches and instead introduces a bilevel game that is more tractable to solve. We show that popular bilevel algorithms, such as unrolled optimization, yield approximations of these games.
3 Non-Convex Bilevel Optimization with Selection
Notations. Define X = R2 and y = R for some positive integers p and d. We consider two real valued functions and g defined on X' and assume g be twice-continuously differentiable.
3.1 Background on Bilevel Optimization
A bilevel program is an optimization problem where an upper-level objective f defined over a set X' ) of variables (Ir, 2) is optimized in the first variable under the constraint that the second variable y is optimal for a lower-level objective y + g(x,y) y) depending on the upper-variable x. When (x,..) admits unique minimizer denoted by y (æ)) which is the case if y + g(z, y) is strongly convex, the bilevel problem is well-defined and can be expressed as:
min (zz 3" (z)), ZE
y (x) arg min g(2z, y).
(BP)
yEy
When g is non-convex, the set of minimizers T(æ):= arg miny g(,, y) may contain more than one element making (BP) ambiguous. A possible approach for resolving the ambiguity is to adopt game-theoretical point of view, where a lower-level agent uses a particular strategy for selecting a solution in T(x). For instance, in pessimistic bilevel games, the lower agent chooses minimizer of g(x,.- that maximizes ((x,-) while the upper agent minimizes the resulting worst-case loss in a:
(UL):
min F(x), sEX
and (LL). F(x) wEy
max f*, s.t. y E ((x). (pessimistic-BG)
Similarly, an optimistic bilevel game can be obtained by replacing maximization with minimization so that both agents cooperate. While these approaches are highly relevant from a game-theone theoretctt point of view, many machine learning applications do not rely on a pessimistic/optinssti bilevel formulation. For instance, for hyper-parameee training data, but it should not have access to the validation data processed (used in f) by the upper agent. Instead, a popular approach consists of applying algorithms designed for bilevel programs that admit unique solutions for the lower problems, even though this assumption may not hold in practice [37]. In the next section, introduce class of games that allow characterizing the equi- librium points obtained by these popular algorithms while resolving the ambiguity of non-convex bilevel problems and bypassing the limitations of pessimisticloptimisti bilevel formulations.
optimization, the lower agent may have access to
3.2 Bilevel Games with Selection (BGS)
We introduce a new class of nested games for bilevel optimization with two agents, a leader and follower. The follower minimizes the lower-level objective g w.r.t. a variable y in y. Similarly, the leader minimizes the upper-level objective f w.r.t a variable x E X while anticipating the fol- lower's solution. More precisely, the leader has access to a selection map: Φ X'xX + 3 to choose a unique critical point 6(x, y) of y + g(x.z) y) given the current state of the game (x, y) E X' X'x)) thus allowing the leader anticipate the follower's solution. Typically, the selection 6(2, y) repre- sents the critical point that is selected by an optimization process of .). starting from an initial condition y (e.g., the limit of a gradient flow for a gradient descent algorithm). The Bilevel Game with Selection (BGS) is therefore defined as the following interdependent optimization problems:
(UL):
min (a v) f (z., d(x, v)), xeX
(LL):
min g v).
(BGS)
vey
3

---

Selection map
Bilevel Game Selection
15
g a))
0.5
(x.0(x. u))
0,f(x.s
-.5
[x" w2'
-0.5 0.5 1.5
0.5 0.5
1.5
Figure I: Left: Hcatmap of the lower-level objective g(z, v). The local minimizers of + g(z, v) are represented by the 'critical lines' in blue. The selection map Φ(2 y) is defined by following the vector field 0gg(2, y). in black. Right: Iterates (æx, ykk ) (in red) obtained by playing BGS. The follower finds the next update ys by optimizing y ++ g( y) starting from previous iterate yk-1- The leader finds the next update ank by optimizing the upper-level objective f along the critical lines' (iterates in green).
Given a selection map o, the game (BGS) is well-defined and does not suffer from the ambiguity problem in (BP). The explicit dependence of o(x, y) on the initialization y might seem unnecessary at first, as could simply fix y to some value Yo and consider only the dependence on the vari- able æ. However, such a dependence on the variable y allows performing warm-start [50], where the lower-level problem is optimized starting from previous state of the game, thus resulting in computational savings Figure 1. We provide below a formal definition for the selection map.
Definition 1 (Selection map). Given a continuously differentiable function g XX x y + R. the map Φ : X 3 -> )) is selection if it satisfies the following properties for any pair (z, v) E X y):
1. Criticality: The element y' -6x,8) y) is critical point of g(z,.). i.e. 0gg(2, 3²)
2. Self-consisteney: yf is a critical point of g(x..) i.e. 0g y) 0, then ((x, v) y.-
Criticality ensures the leader possesses a hierarchical advantage in that they know what are the optimal choices accessible the follower. Self-consistency implies that the leader makes guess that is not contradicting the current choice y of the follower. Both properties ensure the leader can rationally anticipate the follower's 's actions from the current state of the game yI, We will see in Section 4, under mild assumptions on g. that it is always possible to define a selection & as the limit of a continuous time gradient flow of y + g(,,, y) initialized at y. Moreover, as we discuss later in Section 5, the selection does not need to be explicitly constructed for solving (BGS) in practice. It can be simply related to the implicit bias of the algorithm used for solving the follower's problem.
Connection to (BP). When the lower-level objective y + g(x, y) admits unique minimizer y² (xx) is easy to check that there exists a unique selection map @ satisfies ((x,))-y(aa (x)) Hence, (BGS) recovers the bilevel problem in (BP) as particular case.
Connection to (pessimistic-BGG or the optimistic variant. Key differences between (BGS) and pessimistic optimistic games is that (i) the follower has never access the upper function with (BGS), which matches practical hyper-parament optimization applications where f relies on a distinct training set; (ii) the leader in (pessimistic-BGi does
validation dataset, whereas g relies not take into account the strategy used by the follower, whereas the leader in (BGS) makes more rational choices by guessing the strategy of the follower through the selection map d.
First-order equilibrium conditions. The agents can play the game (BGS) by successively taking actions (2 yk) to improve their own objectives x ++ Lg(x, yk-1) and y + g( y). by hoping the strategy will reach an equilibrium pair (x",, .y") Figure 1(Right). In the case where f. 9 and & are differentiable at (x* y²), the equilibrium pair is characterized by a first-order stationary condition:
0, When g is smooth and strongly convex in y, the implicit function theorem [28, Theorem 5.9] ensures that di is differentiable and provides an expression of 0_ .y") ) as a solution to linear system which key for implicit differentiation. This allows to devise efficient algorithms using estimates of the gradient o Cz. see, e.g., [2]. However, extensions of the implicit function theorem, such as the
(x v²) )- = fz fa ",, ,v") ) + 2200x".00 v² (0"
0,g(x", ,y) 0. (SC)

---

Smopth Selection
Non-smooth Selection
g(31.-))
de (2) sti)
dbit, 300
g(
de (soo 3hh)
dizu, 30)
Y2
Y,
Figure 2: Two examples of functions I with different behaviors of the gradient flow under perturbations of x. both figures, the green surface represents a function y + ( y) with y E R² resembling a Mexican hat which has a manifold of (degenerate) local minimizers (in dark green). The blue surfaces represent de- formed versions of the Mexican hat function when the parameter is slightly perturbed Ra0p. Depending the deformation, the resulting function y->g(a11))) !) either preserve the same type of critical points the unperturbed function, i.e. local minimizers remain local minimizers (Left), or change their type, i.e.: local minimizers can become saddle-points (Right). Left: the selection behaves smoothly as a function of the defor- mation. Right: the selection is discontinuous since the gradient flow is pushed away from 6(2v, 3o) which is deformed into saddle point.
constant rank theorem [29, Theorem 4. 4.] for cases where g has possibly degenerate critical points require strong assumptions on which are unrealistic in machine learning. In the next section, we provide new analytical tools for extending implicit differentiation by studying the differentiability of a family of selection maps corresponding to a large class of functions The resulting expression will be key for devising first-order methods solve (BGS), as discussed in Section 5.
4 Selection Based on Gradient Flows for Parameteric Morse-Bott Functions
In this section, we extend implicit differentiation to a class of functions with possibly degenerate critical points. To this end, consider particular selection 6(x, y) obtained the limit of gradient flow (0, 2)) of g(x,-) initialized at y. We then study the differentiiaiility w.r.t. x of the selection by analyzing the dynamics of such gradient flow. For general non-convex functions, the selection might be non-differentiable since a small perturbation to the parameter x can change the geometry of the critical points of g. causing the perturbed flow move away from the perturrddd one (see Figure 2). We are therefore interested in functions g preserving the local geometry near varies. In Section 1. we introduce such class of functions called parametric Morse-Bott functions, which covers many practical machine learning models. We then show, in Section 4.2, that the selection resulting from such function is differentiable near local minima.
critical points
4.1 Parameteric Morse-Bott Functions
We introduce parametric Morse- Bott functions, a class parametric functions g X x R with parameter z in X extending the more familiar notion of Morse-Bott functions (Appendix A.I, [16]) to account for the effect of the parameter x on the geometry of critical points.
Definition 2 (Parametric Morse-Bott function.). Let g X' be real-valued twice continu- ousely differentiable function and define the set of augmented critical points M as follows:
M = {(x, E X x y 0g 9) =0}
(1)
Let (zo, vo) M. We say that is Morse-Bott yo w.r.t. Zo, if there exists open neighbordhood of (zo, 2o) s.t. the intersection MnV is C"-coneected sub-manifold of X x of dimension:
dim(M n V) dim(X) +
(g Mo)))-
g is a parametric Morse-Bott function for any (Ip, E. is Morse-Bel Bott at yo W.E.t. Zg-
The functions in Definition 2 satisfy condition that is stronger than simply satisfying the Morse- Bott property at any parameter value x (Definition of Appendix A.1). Indeed, we show Propo- sition 7 of Appendix A.2 that, for any Zo E X. the function y + g y) is Morse-Boo function,
5

---

meaning that the critical set C(x))) of y + g(zo..) near a critical point yo is locally C² con- nected sub-manifoll of Y of dimension equal to the dimension of the null-space of the Hessian " yo). For conciseness, we introduce the following assumption which ensures g satisfies the condition of Definition as well as possesses continuous third- derivatives.
Assumption (Parameteric Morse-Bott property). The function g is al least three-times contin- uously disferentiable and is a parameteric Morse-Boll function as defined in Definition 2.
Examples of parametric Morse-Bott function. A notable class of parametric Morse-Bov Bott func- tions is the one containing all twice-continuously differentiable functions that are strongly convex or, more generally, possess only non-degenerate critical points in the second variable as shown in Proposition 8 of Appendix A.2. Note that parametric Morse-Bott functions need not be convex and can have multiple (possibly degenerate) local minima, saddle- saddle-points, and local maxima.
Another class of functions, this time with possibly degenerate critical points, are those that can be ex- pressed as a composition of some Morse-Bott function and family (Tx) of diffeomorphisms on Y' parameterized by x, i.e. g y)=h(r=(v)). This particular form is relevant in generative modeling where the diffeomorphisms are defined using normalizing flows of parameter [44].
The condition in Definition 2 ensures that the degree of freedom of the augmented critical set M exactly determined by the degree of freedom of the parameter x and the degree of degeneracy of the Hessian at a critical point y. This condition is precisely what guarantees the stability of the local shape of critical points when the parameter x varies as we formalize through the next theorem.
Theorem 1 -oot lemma with parameters), Let g be a function satisfying Assumption 1. Let (ro. (o) in M be augmented critical point of 9. Denote by K. the null space of the Hes- Wo) and by K- its orthogonal complement in Y. Let Jo be diagonal matrix with diagonal element given by the sign of the non eigenvalues of Ag. Then, there exists open neighborhoods Ut and V of (ro, Oc, 0k+) and (Io, yo) in XxXxK and XxY, and a diffeomor- phism &p : U + V preserving the first variable, iee. b(x, r, w) y) for any (2, (,T,,w) w) E U. with (1o, O2, 0g= (= yo) such that g admits the representation:
sian Ag (y:
g( r, w)) = g(v(1, Occ, 0k+ + 2 Jow,
V(a, r, w) edu
Theorem 1, which is proven in Appendix A.3, shows that, near an augmented critical point (200 yo). looks like a quadratic function up to an additive term that depends only on the parameter x. More- over, slightly varying the parameter x does not change the quadratic function and thus preserves the local shape near critical points. Theorem is an extension of the Morse-Bor lemma [16. Theorem 2.10] the case when there is a dependence on parameter x. It can also be seen as an extension of the Morse lemma with parameters [16, Theorem 4] which allows dependence to a parameter but requires the critical points to non-degenerate (invertible matrix Ag). To our knowledge, The- orem 1 is the first result in the literature providing a decomposition of parametric functions with degenerate critical points into the sum of a quadratic nen-degenerate term and singular term de- pending only on the parameter ær We present now a corollary of Theorem which is strengthened version of the standard Eojasiewicz inequality [36] that will be essential for our subsequent analysis.
Proposition 1 (Locally Uniform Lojasiewicz gradient inequality). Let be a function satisfying Assumption and let (Iu, yu) be in M the augmented critical set defined Definition 2. Then, there exists an open neighborhood U of (ro, and a positive number μ >> 0 such that + g(x. y) constant on the set M O U with some common value G(z) := g(z, y) and the following holds:
1 plg(z, v) G(x))= < T 1100g(0z
((,y)) E.
Proposition 1, which is proven in Appendix A.3, ensures that the łojasiewicz gradient inequality holds uniformly on (I, y) near any augmented critical point (o). This result will be essential in Section 4.2 for defining selection é obtained as limits of gradient flows and obtain a lo- cally uniform control of these flows in the parameter x. This in turn will allow us to obtain the differentiability of the selection in the parameter whenever 6(x, y) is a local minimum.
4.2 Smoothness of Selections Based on Gradient Flows of a Parametric Morse-Bote Function
We consider a construction for the selection ø in Definition as limit of a continuous-tine gradient flow of g. More precisely, we define a continuous-time trajectory (Ø.(I, y)) in y initialized at

---

00(2, v) and driven by the differential equation:
d v) 0gg (e
(GF)
dt
Provided (z, y) converges towards some element o(x, 2) as 400000 we can expect such limit to satisty both conditions of Definition I, therefore constituting a valid selection. However, for general non-convex functions, $1(2, y) might not always converge [36]. To guarantee the existence and convergence of the flow, we make the following assumptions on the function g. Assumption 2 (Smoothness). There exists L>0 such that y u) is L-Lipschitz.for any xEX. Assumption (Coercivity). For any x E X, it holds that g(x, y) + +00 as ||||| - +00.
The smoothness assumption in Assumption 2 is standard and guarantees the existence of the flow by the Cauchy-Lipschitz theorem. The coercivity condition in Assumption guarantees that de y) cannot escape to infinity. It can be casily enforced by adding a small f2-penalty to a non-negative loss (such eross-entropy learning. These assumptions, along with Assumption I ensure that the limit (xx; y) always exists as summarize in the following proposition, which is proven in Appendix B.
mean-squared loss) which is already a common practice in machine
Proposition 2. Under Assumptions 1 to 3, and for any (x. E X x V, the gradient flow (GF) always converges towards critical point 6(I, y) of + g(2, and the map (z, y) + Φ(z y) is selection map as defined in Definition! I. We call 6 the flow selection relatively to g.
Proposition 2 is consequence of a general result that holds for functions satisfying Lojasiewiez gradient inequality [3, 40] which is the case here by Proposition 1. From now on, we restrict our attention to the selection & defined in Proposition 2. Even though 6 satisfies the implicit equation 0yg(2, Φx. y)) 0, we cannot rely anymore on the implicit function theorem for studying the differentiability of Φ(x.y) in x since can have degenerate critical points. Instead, we propose to characterize the differentiability of Φ by studying the limit of Ue(2, y) == Öz y) which is formally driven by a linear differential equation of the form:
dUe(x, v) - Sy (r(2, ()) + Uclæ, v) Byg (e( di
(2)
Had we known in advance that Φ(z, y) is differentiable in x, the limit (2, y) of Uz y) as t + +0o, whenever defined, would be a promising candidate for the differential of d(x, y) in x. Such limit is indeed expected to satisfy the following linear equation:
0 = -2,9(2 6(z, v)) - Uso (2,v) V) g 6(2,)) y)).
(3)
A first challenge is to ensure that U, does not diverge. For critical points Φ(x, y) that are not local minima, it easy to see that the Hessian (z, (1, u)) must have a negative eigenvalue for t large enough, therefore causing the system (2) to diverge. Intuitively, unless o(x, y) is a local minimum, there is no reason to expect a y) to be differentiable or even continuous in x, simply because (xx, y) would be an unstable fixed-point of the flow (x y). so that any change in x might cause large variation in 6(z, (z, v). The possible non-differentiability of 6(x, y) for critical points that are not local minima is not problematic in practice, since for almost all initial conditions y of the flow (x, v). the limit dxx, y) is guaranteed to be local minimizer [41]. In addition, we show in Proposition 13 of Appendix B.3 that if 6(zo, y) is a local minimum, then o(x, y) must also be a local minimum in neighborhood of Z0-
Nevertheless, even for local minima, if the Hessian (2 (fx, y)) non-invertible, (3) might never hold if ( Φ(x, y)) does not belong to the image of the Hessian. However, we show in Proposition 6 of Appendix A.2 that, for any pair (x, y) of critical points, Pe y) must always belong to the span of the Hessian 82 gr, y) as soon as g satisfies Assumption 1, therefore ensuring that (3) admits a solution. The following theorem, which is proven in Appendix C, establishes the differentiability of é at local minima and shows that O, is exactly given by the limit U...
Theorem 2 (Degenerate implicit differentiation.). Let g be a function satisfying Assumptions to 3 so that the flow selection ó is well-defined. Ler (Io, Yo) be in Xxy. If 6xID, yo) is a local minimizer of y + g(xo. y). then there exists a neighborhood U of zo on which x + Φ(z, yo) is differentiable with differential 0n0(2, =0)=-Uo(1s, (ad(a,)))-Uaa wo). Moreover, if yo is local minimizer of y->g(ao, y), then, denoting by i the pseudo inverse operator, 0, yo) is exactly given by:
0,6(2o. (o)= Deng (zo, yo) (0 (20, y0))
(4)
7

---

The expression in (4) is very similar to the one that would arise by application of the implicit function theorem a strongly convex function g. However, the proof technique does not rely on such theorem which would not be applicable here. 'he key technical challenges in proving the above result are: (i) showing that d(x, y) must continuous at zo and (ii) controlling the error [[U,(z,)) y) - (T, v)l locally uniformly in z. The result follows by the application of classical uni- form convergence results [46, Theorem 7.17J. The continuity of Φ is established in Proposition 12 of Appendix B.3 and relies on stability analysis of the flow performed in Appendix B.2. The uni- form convergence of Uz towards Uso is shown Proposition 17 Appendix C and relies on local uniform convergence of the flow d, towards & which is proven in Proposition 14 of Appendix B.4. is worth noting that, even though we identified 0₂ to be Ux.. the latter is not fully characterized by (3) it might contain non-zero component in the null-space of the Hessian. However, when (Io, yo) is an augmented critical pair of such a component vanishes, and 0z yo) is exactly determined by the minimal norm solution in (4). The latter fact has practical implications when designing algorithms for solving (BGS) as we discuss next.
5 Algorithms
5.1 Unrolled Optimization for BGS
Unrolled optimization constructs a map (r( y) approximating a critical point of the function y >> g(r,y) y) for any fixed by applying finite number T of gradient updates starting from some initial condition y. By convention, we set fo y)=y. Hence, fr can be understood as an approximation the selection map defined in Section 4.2. We emphasize that for is not a selec- tion (Definition 1) since (It y) is not a critical point of g in general. Nevertheless, it provides a tractable approximation to critical points which is key for constructing practical algorithms for bilevel optimization. The gradient of (T(xI,) y) w.r.t x is then obtained by differentiating through the optimization steps and used to optimize the approximate upper-level objective:
Cr v) = fx, pp (z)
Given the k-th upper-level iterate 23 and initial condition ÿk for the unrolled optimization, these approaches compute an approximation yx=pr(#x-11 5s) and find an update direction dg for the upper-level variable x: by differentiating Lr(x, Ut) in the current iterate 26-1. The following
iterate Iy is obtained by applying an update procedure, such as -g= 1-74 for positive small enough step-size y. Algorithm 1, we present several variants of these schemes, including simple correction allowing them to solve (BGS) instead of an approximation.
The initial condition ÿK is often com- puted using warm-start procedure TM=IM((Ix1:: Mk-1). The simplest procedure is to set 8 in which case Io(2, y)=y. However, is not uncommon to perform M>0 opti- mization steps to minimize the objec- tive g= y) starting from yk-1- By doing so, gradient unrolling stops ýk and ignores the dependence of in on yk resulting in Truncated un- rolled optimization [47]. Algorithm summarizes these approaches when
Algorithm BGS-Opt(ro, yo)
1: Inputs: To. yo.
2: Parameters: K, T, M AddCorrection
3: for h {1,..., K + 1} do
4:
Uh + Imr(Fx 1k-1). # Warm-start.
5:
y4 pog--pr(RK-- 9k # Unrolled optimization.
6:
de < O. V&h)
7:
if AddCorrettion= True then
8:
th + 0,CTT(MN11
9:
E (0 ( vx)) og Approx. solver
10:
du + dy +00zygg(zaa 3x Grad. correction
11:
end if
the binary variable AddCorrection is set to False. To characterize the limit points of Algorithm we make the following assumptions on IMs PI.
12: Ikk +- Ib-1 7dk # Updating
end for
14:
Return (IK, UK))
the maps Isa and 4P are continuous on X' x y and take values in y, with fTT being continuously differentiable. Moreover, for any (x,y) E X x y s.t. 0gg(2, 0 and M,T 2 0, there exists a matrix D such that:
Assumption 4. For any non-negative integers M,T
IM (z, y) = (2 v) = y. OxpT(( v) 2 D) 02 4) = =1 -1+02 8, D.
8

---

Finally, for any (z, xx, and M,T 2 S.t T M > 0, the equality y=pr Iad (z) implies that y is critical point of g. i.e. (zg(2,y) = 0.
Assumption 5. PT converges to selection & and PT converges uniformly near local minima.
Assumption 4 is satisfied by many mappings used in practice such T-steps of the gradient de- scent or proximal point algorithms, whenever is twice-continuouslly differentiable and L-smooth shown in Proposition 19 of Appendix D. Assumption convergence result in Proposition 17 of Appendix C but that we directly assume here for simplicity. Under these assumptions we show that Algorithm 1 can find equilibria of (BGS) up an approxi- mation error resulting from the fact that şT is not an exact selection.
a discrete-time version of the uniform
Proposition Let M. T be non-negative numbers s.t. M T > T of Algorithm using the maps Im and pr and without any correction, i.e. AddCorrection If (It: Ws) converges to limit point (xi, V/) then, under Assumption 4:
and let (Ik Miks be the iterates
Gxfr( WT) = O,
=0
Let E be the set of limit points (0T yT) for T 2 O. If E bounded and yf is a local minimum of g( for any T 2 0, then, under Assumptions 4 and 5, the elements of E. are approximate equilibria for (BGS):
simsup (0 v-)1== =0
0gg(2 = =0, (VT > 0).
Proposition 3 shows that unrolled optimization algorithms approximately solve (BGS) in the limit where the number of unrolling steps T of the pr goes to infinity. This result is consistent with the ones obtained in [25] for the case where g is strongly convex and illustrates the high computational cost for solving (BGS) without correcting for the bias introduced by unrolling. Next, show how to get rid of such a bias in light of Theorem 2.
5.2 Implicit Gradient Correction
We propose to correct the bias of unrolling by exploiting the expression of the gradient Ô_ provided Theorem 2. The key idea to obtain an expression for (z, y) in terms Lt and the second-order derivatives of y which holds for any local minimizer of g(z, y) as shown by the proposition below.
Proposition 4. Let db be the selection defined in Section 4.2 and (x,y) 3) E X x 3 be s.t. y is local minimum of y + g(x, y). Then, under Assumptions to 4, 02 C. (z, u) is given by the equation:
O. O.Lo(x. v) = (z.r(z. v) - gl (8 g v)) Cx
Proposition 4, which is proven in Appendix D, suggests a simple correction for the gradient esti- mate de in Algorithm By doing so, the corrected algorithm would be performing an approximate gradient descent on each of the upper-level and lower-level objectives, suggesting that the algorithm may recover equilibrium points of (BGS) without having increase the computation budget for the unrolling as we show later in Proposition 5. A simple way to proceed would to compute satisfy- ing the approximate equation c - B&(As)
where A y. Br:=oryg(a 1, 91)
and 1r (x)- More concretely, Cs can be computed by setting C ng-Bey B&E& where EK ap- proximates the minimum norm solution to the least squares problem:
EN A arg migmin/l ||E1?,
s.t. E min | + u
(5)
Approximate solution (5). is possible to solve (5) approximately using an iterative procedure by constructing N iterates &* starting from 5 = 0 and performing (conjugate) gradient descent the quadratic objective. This can be implemented efficiently using only Hessian vector products with the Hessian A% [37]. The constrained problem (5) can also be expressed as unconstrained one by re- parametrizing & Ag2:
EK ~ Axa
s.t. 2 E arg ||A 2 + 0k ||
(6)
Eq. (6) has the advantage that = solves an unconstrained problem. As such, it is more amenable to applying warm-start strategy, which can yield efficient approximation 2μ to = by exploiting pre- viously computed approximation 2 2 [2]. This strategy can be achieved using a standard

---

iterative algorithm P for approximately solving the least-squares problems, such as fixed num- ber of conjugate gradient iterations, that takes as imput the matrix A,, vector vk and initialization 2k-1 R = and returns the next iterate R zt. More formally we view P as continuous map of v, 2) returning a vector z' and such that the only fixed points are exact solutions to the least square problem ming ||A2 + ell We refer Appendix D.I for examples of such maps. We can then define the iterates 2 and &a as follows:
E - AsTk,
Zk - P(Ak, Uk. =k-1).
(7)
The corrected algorithm is obtained by setting the variable AddCorreetion=Truu in Algorithm and computing the using any approximate solver including, in particular, the ones based on warm-start strategy as in (7). The following proposition, with proof in Appendix D, shows that the proposed correction indeed yields equilibrium points of (BGS).
Proposition 5. Let (Ix. U&) be the tterates obtained using Algorithm I with AddCorrection-Tree True and + M > O and assume that Es are computed using (7). If (Ix. yks 2g)x20 converges to limit point (x", 1² ²²),, then y² is critical point of - g(2", y) and if. in addition, y² is a local minimizer, then (x" ,y" must an equilibrium of (BGS) satisfying (SC):
OeLole', =0 and 0yg(a* y=)=
Proposition 5 shows that the proposed correction allows to recover equilibria of (BGS) without hav- ing to increase the number of iterations of the unrolled algorithm. This by contrast with Propo- sition 3 where T must increase to infinity, which would be impractical. We discuss in Appendix D.2 how different choices for the parameters T and M recover known algorithms. In particular, that Algorithm 1 with correction allows interpolating between two families of algorithms: (ITD) and (AID) while still recovering the correct equilibria. Numerical results illustrating the benefits of the correction are presented in Appendix E.
6
Discussion
We have introduced bilevel game that resolves the ambiguity in bilevel optimization with non- convex objectives using the notion of selection maps. We have shown that many algorithms for bilevel optimization approximately solve these games up to bias due to finite computational power. Our study of the differentiability properties of the selection maps has resulted in practical procedures for correcting such a bias and required the development of new analytical tools. This study opens the way for several avenues of research understand the tradeoff between unrolling and implicit gradient correction for designing efficient algorithms. In future work, studying these algorithms in a non-smooth and stochastic setting would also of great theoretical and practical interest.
Funding
This project was supported by ANR 3IA MIAI@Grenobil Alpes (ANR-19-P3IA-0003)
References
[1] Pierre Ablin, Gabriel Peyré, and Thomas Moreau. Super-efficiency of automatic differentiation for functions defined as a minimum. In International Conference on Machine Learning, pages 32-41. PMLR, 2020.
[2] Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. working paper or preprint, November 2021. URL https://hall archives- ouvertes wwwporttts..r.al..e..
[3] Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and reg- ularized gauss-seidel methods. Mathematical Programming, 137(1):91-129, 2013.
[4] David M Austin and Peter Braam. Morse-bott theory and equivariant cohomology. In The Floer memorial volume, pages 123-183. Springer, 1995.
[5] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation machine learning: a survey. Journal of machine learning research, 18, 2018
10

---

[6] Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:/805.081.6. 2018.
[7] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Lean-Philippe Vert. Efficient and modular implicit differentia- tion. arXiv preprint arXiv:2105. 15183, 2021.
[8] Jérôme Bolte, Tam Le, Edouard Pauwels, and Tony Silveti-Falls. Nonsmooth implicit differ- entiation for machine-leaminng and optimization. Advances in neural information processing systems, 34:13537-13549 2021.
[9] Jérôme Bolte, Ryan Boustany, Edouard Pauwels, and Béatrice Poopueu. Nonsmooth automatic differentiation: cheap gradient principle and other complexity results. arXiv
preprint arXiv:2206.01730, 2022.
[10] Jéröme Bolte, Edouard Pauwels, and Samuel Vaiter. Automatic differentiation of nonsmooth iterative algorithms. arXiv preprint arXiv:2206.00457, 20222
[11] Ralph L Cohen. Topies in Morse theory. Stanford University Department of Mathematics, 1991.
[12] Sara Daneri and Giuseppe Savaré. Lecture notes on gradient flows and optimal transport. arXiv preprint arXiv: 1009.3737 2010.
[13] S Dempe, J Dutta, and BS Mordukhovichh. New necessary optimality conditions in optimistic bilevel programming. Optimization, 56(5-6):577-604, 2007.
[14] Justin Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[15] Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International conference on machine learning, pages 1309-1318. PMLR, 2018.
[16] Paul Feehan. On the morse- property of analytic functions on banach spaces with to- jasiewicz exponent one half. Calculus of Variations and Partial Differential Equations, 59(2): 1-50, 2020.
[17] Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated machine learn- ing, pages 3-33. Springer, Cham, 2019.
[18] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning, In International Conference on Machine Learning, pages
PMLR, 2018.
[19] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 022446.6. 2018.
[20] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint 16X1v:1607.05447, 2016.
[21] Lei Guo, Gui-Hua Lin, and Jane J Ye. Solving mathematical programs with equilibrium con- straints. Journal of Optimization Theory and Applications, 1 (66(1))234-22) 256, 2015.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2015. doi: 10.1 10.1CO///2P
[23] 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/74, 2020.
[24] Kaiyi Ji and Yingbin Liang, Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.03926 2021.
[25] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and en- hanced design. In International Conference on Machine Learning, pages 4892. PMLR, 2021.
[26] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.

---

[27] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[28] Serge Lang. Fundamentals of differential geomelry, volume 191. Springer Science & Business Media, 2012.
[29] John M. Lee. Introduction to Smooth Manifolds. Springer Science & Business Media, 2003. ISBN 978-0-387-95448-6. Google-Books eqfg/ijQceYC.
[30] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.
[31] Zhuchun Li, Yi Liu, and Xiaoping Xue. Convergence and stability of generalized gradient systems by tojasiewiez inequality with application in continuum kuramoto model. Discrete & Continuous Dynamical Systems, 39(1):345, 2019.
[32] Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang. KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent back- proec--pppggation... In International Conference Machine Learning, pages
PMLR, 2018.
[33] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint arXiv:2101 17, 2021.
[34] Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Value-function-basse sequential minimization for bi-level optmizatiion arXiv preprint arXiv:2110.04974, 2021.
[35] Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- gradient-based bilevel opti- mization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34, 2021.
[36] Stanislaw Lojasiewicz. Sur les trajectoires du gradient d'une fonction analytique. Seminari di geometria, 1983:115-117, 1982.
[37] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[38] Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. IEEE transac- lions on pattern analysis and machine intelligence, 34(4):791-804, 2011.
[39] J Martunez-llfar IS Meza-Sarmiento, and R Oliveira. Topological classification of simple morse bott functions on surfaces. Real and complex singularities, 675:165-179, 2016.
[40] Benoît Merlet and Thanh Nhan Nguyen. Convergence to equilibrium for discretizations of gradient-liks like flows riemannian manifolds. Differential and Integral Equations, 26(5/6): 571-602, 2013.
[41] loannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. arXiv preprint arXiv: 1605.00405 2016.
[42] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737-746. PMLR, 2016.
[43] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-Learning with Implicit Gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, d'textquotesingle Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32 (NeurIPS). Curran Associates, Inc., 2019.
[44] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In Inter- national conference on machine learning, pages 1530-1538. PMLR, 2015.
[45] Rex Clark Robinson. An introduction to dynamical systems: continuous and discrete, vol-
ume 19. American Mathematical Soc., 2012.
[46] Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
[47] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intel- ligence and Statistics, pages 1723-1732. PMLR, 2019.
12

---

[48] Rahul Singh. Maneesh Sahani, and Arthur Gretton. Kernel Instrumental Variable Regression. arXiv:/906.002) 00032 [es, econ, math, stat), June 2019. URL http:// wttp:/i..rr/abb///9/9
00232. arXiv: 1906.00232.
[49] H.F. Von Stackelberg. MurkformundGieccheevvch Springer, 1934.
[50] Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse. Implicit regularization in overparameterized bilevel optimization. In ICML Beyond First Order Methods Workshop,
2021.
[51] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint 1r 2018.
[52] Wei Wang, Yuan Sun, and Saman Halgamuge. Improving mmd-gan training with repulsive 2018.
loss function. arXiv preprini
[53] Wolfram Wiesemann, Angelos Tsoukalas, Polyxeni-Margarita Kleniati, and Berę Rustem. Pes- simistic bilevel optimization. SIAM Journal on Optimization, 23(1):353-380 2013.
[54] Mengwei Xu and Jane Ye. A smoothing augmented lagrangian method for solving simple bilevel programs. Computational Optimization and Applications, 595333333337, 2014.
[55] Ye and XY Ye. Necessary optimality conditions for optimization problems with variational inequality constraints. Mathematics of Operations Research, 22(4):977-997, 1997.
[56] JJ Ye and DL Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9-21 27, 1995.
[57] JJ Ye, DL Zhu, and Qiji Jim Zhu. Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM Journal on optimization, 7(2):411-507, 1997.
[58] Alain B Zemkoho. Solving ill-posed bilevel programs. Set- Valued and Variational Analysis, 24(3):423 448, 2016.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how answer these questions. For each question, change the default [TODO] [Yes], [No]. or [N/A]. You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. Please do not modify the questions and only use the provided macros for your answers. 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/answers 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? [N/A]
(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 all theoretical results? [Yes]
(b) Did you include complete proofs of all thcoretical 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)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent 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 identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(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]
14


Reviews:
[{"review_id": "zhfQsEJkwuZ", "reviewer": "Reviewer_tW4t", "summary": "The paper analyses bilevel optimization problems with a non-convex lower level problem through the concept of a selection map that chooses a particular solution to the lower problem. They use this notion to define a new selection map based on gradient flows and analyze the resulting games and the differentiability of the selection using a new set of tools in Morse theory. They finally use the analysis to propose an algorithm for differentiating through the inner problem even when the unrolled optimization of the inner problem is solved for a finite number of steps.", "questions": "I think my comments under the weaknesses section are addressable and would appreciate the authors making amends along those directions.\n\n**Minor Comments**\nMinor Typo : line 266 : knew -> known\n\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The paper is well written and was comprehensible even for a practitioner like me without much prior knowledge about the specific theoretical tools used to analyze such problems. It also provided a nice overview of the existing approaches which I really appreciated.\n2. As a practitioner, I think the primary contribution of the paper was showing that the rough equivalent of the implicit function theorem is actually the theoretically sound approach to take even in the case where the inner problem is non-convex (which is what we used to do even otherwise, but it’s very useful to actually have a theoretical justification for it ;) ) under reasonable assumption. To my knowledge this is the first paper showing this. \n**Weaknesses**\n1. Although, I realize that it’s probably unreasonable of me to expect experiments from a theory paper, I would have appreciated some experiments showing the practical impact of applying the gradient correction on some toy problems. \n\n", "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": "LpvQL3bpT3D", "reviewer": "Reviewer_gXUJ", "summary": "The paper studies the nonconvex inner problem bilevel optimization, proposed algorithm for such a problem, and theoretically show the asyptotically convergence. ", "questions": "How to understand the UL in (BGS)? We also have the variable of $y$ and the minimization is only taken in $x$.\n\nIn Definition 1, 1.Criticality, is it $\\partial_y g(x, \\phi(x, y)) = 0$? Moreover, is self-consistency needed?\n ", "limitations": "The paper lack numerical verifications, and I am doubt about the setting of selection map, my inituition is that it is a mapping from $\\mathcal{X}$ to $\\mathcal{Y}$.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides the comprehensive study of the problem and the result is complete.", "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": "KfQgVxE5wUX", "reviewer": "Reviewer_YZdt", "summary": "This paper studies bilevel optimization. The authors show that existing algorithms is subject to approximation errors. The authors introduce a simple correction to these algorithms for removing the errors.", "questions": "1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the \"Unrolled Optimization Scheme\"\n2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?\n3. Any concrete example to show the other algorithms issue would be much better.\n4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.", "limitations": "1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the \"Unrolled Optimization Scheme\"\n2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?\n3. Any concrete example to show the other algorithms issue would be much better.\n4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: A good background survey of bilevel optimization. The writing is reasonable.\n\nWeakness: 1. It says that many existing algorithms for bilevel optimization suffer from approximation errors. But it only analyzes the \"Unrolled Optimization Scheme\"\n2. Step 9 in Algorithm 1 is using approximation, which is not precise. How can one implement it?\n3. Any concrete example to show the other algorithms issue would be much better.\n4. It only solves the bilevel optimization to stationary point and is not able to solve it to global optimality.", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Dx6l7MeUwea", "reviewer": "Reviewer_oofy", "summary": "Bilevel optimization problems present an ambiguous model when the lower-level problem has multiple solutions. Typical ways to deal with this ambiguity are to consider either the so-called \"optimistic\" or \"pessimistic\" versions of the problem. In contrast, this paper proposes the use of a selection map to resolve the ambiguity. Under certain conditions, the authors show the selection map is differentiable which they claim makes the model amenable to numerical computation.", "questions": "What do the authors mean by their notation for the BGS problem? Should the $y$ variable in the selection map in the upper-level problem be interpreted as a kind of \"initial condition\" or \"state variable\"?", "limitations": "Not applicable", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are related to the technical rigor of the work. The results look reasonable and as would be expected under the specified conditions, though I did not check the proofs. The weaknesses of the paper are that the notation is unclear and, more significantly, that the relevance of the selection map model is questionable. \n\nThe authors present the pessimistic-BG problem using non-standard notation of separately presenting an upper-level and a lower-level problem. The typical notation is to write a single optimization problem where the lower-level problem is included as a constraint in the upper-level problem. The authors' notation is understandable to readers with familiarity with bilevel optimization, but their notation would be unclear to readers not familiar with bilevel optimization.\n\nHowever, the notation that the authors use to present the selection map within the BGS problem is unclear. As currently written, the authors' notation is unclear, and the resulting model does not resolve the ambiguity that they seek to resolve. The authors' notation does resolve the ambiguity if an additional assumption, which is not explicitly stated in the paper, is made -- specifically that the $y$ variable within the selection map is a kind of \"initial condition\" or \"state variable\".\n\nRegardless of the above issue about the meaning of how the selection map is used, there is questionable relevance of this model of using a selection map to resolve ambiguity in bilevel optimization problems with lower levels that have non-unique solutions. The reason this model is questionable is that depending on how this selection map is chosen the results of the model can be completely different, and so the selection map approach does not really resolve any ambiguity in which lower-level solution is used in the upper-level problem. The authors present no evidence that this would be a meaningful model. Even if the authors provide evidence that the model is meaningful, it is questionable that this represents an important or major contribution. Based on my understanding of the authors' unclear notation, their idea of using a selection map is equivalent to merely defining a different (parametric) objective function for the upper-level problem. As such, the authors' problem is equivalent to an optimistic bilevel optimization problem with a different (parametric) objective function. The technical results are also arguably: not surprising, not particularly difficult to derive or prove, and not interesting.", "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