A framework for bilevel optimization that enables  stochastic and global variance reduction algorithms
Authors: Mathieu Dagréou
Pierre Ablin
Samuel Vaiter
Thomas Moreau
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bilevel opitimization
stochastic optimization
non-convex optimization

Abstract: Bilevel optimization, the problem of minimizing a value function which involves the arg-minimum of another function, appears in many areas of machine learning. In a large scale empirical risk minimization setting where the number of samples is huge, it is crucial to develop stochastic methods, which only use a few samples at a time to progress. However, computing the gradient of the value function involves solving a linear system, which makes it difficult to derive unbiased stochastic estimates.
To overcome this problem we introduce a novel framework, in which the solution of the inner problem, the solution of the linear system, and the main variable evolve at the same time. These directions are written as a sum, making it straightforward to derive unbiased estimates.
The simplicity of our approach allows us to develop global variance reduction algorithms, where the dynamics of all variables is subject to variance reduction.
We demonstrate that SABA, an adaptation of the celebrated SAGA algorithm in our framework, has $O(\frac1T)$ convergence rate, and that it achieves linear convergence under Polyak-Lojasciewicz assumption.
This is the first stochastic algorithm for bilevel optimization that verifies either of these properties.
Numerical experiments validate the usefulness of our method.

A framework for bilevel optimization that enables stochastic and global variance reduction algorithms
Mathieu Dagréou Inria, CEA
Pierre Ablin CNRS
Université Paris-Saclay Palaiseau, France
Université Paris- Paris-Dauphine, PSL-Uniivrsity Paris, France
mathieu dagreou@inria.fr
pierre..blin@cnrsss
Samuel Vaiter CNRS
Thomas Moreau
Inria, CEA
Université Côte d' Azur, LJAD
Université Paris- Paris-Saclay
Nice, France
Palaiseau, France
thomas www.au@inria...... fr
Abstract
Bilevel optimization, the problem of minimizing value function which involves the arg-minimum of another function, appears in many areas of machine learning. a large scale empirical risk minimization setting where the number of samples is huge, it is crucial to develop stochastic methods, which only use few samples time to progress. However, computing the gradient of the value function involves solving linear system, which makes it difficuul to derive unbiased stochastic estimates. To overcome this problem we introduce a novel framework, in which the solution of the inner problem, the solution of the linear system, and the main variable evolve at the same time. These directions are written as a sum, making it straightforward derive unbiased estimates. The simplicity of approach allows us to develop global variance reduction algorithms, where the dynamics of all variables is subject variance reduction. We demonstrate that SABA, adaptation of the celebrated SAGA algorithm in our framework, has ((+) convergence rate, and that it achieves linear convergence under salyak-t.ojasciewicz assumption. This is the first stochastic algorithm for bilevel optimization that verifies either of these properties. Numerical experiments validate the usefulness of our method.
Introduction
Bilevel optimization is attracting more and more attention the machine learning community thanks its wide range of applications. Typical examples are hyperparameters selection [5, 38, 17, 6]. data augmentation [1 42), implicit deep learning [3] or neural architecture search [33]. Bilevel optimization aims at minimizing function whose value depends the result of another optimization
problem:
min h(x) F(= (x),,,,,,, such that ="<x) rER
(xx E arg min G(z,x) ZEEP
(1)
where F and G are two real valued functions defined on RR x Rdd. G called the inner function, F the outer function and is the value function. Similarly, is the inner variable and r is the outer variable. In most cases, the function z" can only be approximated by an optimization algorithm, which makes bilevel optimization problems challenging. Under appropriate hypotheses, the function h is differentiable, and the chain rule and implicit function theorem give for any x E IRd
Vh(z) F (x) + V G(z*(x)) x)e"
(2)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where v (a) E R' is the solution of a linear system
0 ('(x)= = - (V]())))))( Vi
(3)
In the light of (2) and (3), it turns out that the derivation of the gradient of h at each iteration is cumbersome because it involves two subproblems: the resolution of the inner problem to find an approximation of x (x) and the resolution of a linear system to find an approximation of of v*()..
makes the practical implementation of first order methods like gradient descent for (1) challenging.
As is the case in many machine learning problems, we suppose in this paper that F and G are empirical means:
Gradient norm
10-2
1 F(2, = Σ F), G(2,z)
= n2 Σ G((2,z)
10-7 7
10-12 12
SABA
SOBA
This structure suggests the use of stochastic methods to solve (I). For single-level problems (that is, classical optimization problems where one function should be min- imized), using Stochastic Gradient Descent (SGD; [41, 7)) and variants is natural because individual gradients are straightforward unbiased estimators of the gradient. In the bilevel framework, want to develop algorithms that make progress on problem (1) by using only a few func- tions F2 and G; time. However, since Vh involves the inverse of the Hessian of G, building such stochastic algorithms is quite challenging, one of the difficulties being that there is straightforward unbiased estimator of h.. Still, in settings where m or are large, where computing even a single evaluation of F G is extremely expensive, stochastic methods are the only scalable algorithms.
100
200
300
400
Iterations
Figure Convergence curves of the two proposed methods on toy prob- lem. SABA is stochastic method that achieves fast convergence on the value function.
Variance reduction [27, 13, 43, 15, 12] is a popular technique to obtain fast stochastic algorithms. In single-level setting, these methods build an approximation of the gradient of the objective function using only stochastic gradients. Contrary to SGD, the variance of the approximation goes to 0 as the algorithm progresses, allowing for faster convergence. For instance, the SAGA method [13] achieves linear convergence if the objective function satisfies a Sallyak-Eojasciewicz inequality, and O O convergence rate on smooth non-convex functions [40]. The extension of these methods to bilevel optimization is natural idea to develop faster algorithms. However, this idea is hard to implement because is hard to derive unbiased estimators of Vh, let alone variance reduction ones.
Contributions. We introduce novel framework for bilevel optimization in Section 2, where the inner variable, the solution of the linear system (3) and the outer variable evolve jointly. The evolution directions are written sums of derivatives of Fj and G,, which allows us to derive simple unbiased stochastic estimators. In this framework, we propose SOBA, an extension of SGD (Section 2.1), and SABA (Section 2.2), extension of the variance reduction algorithm SAGA [13]. In Section we analyse the convergence of our methods. SOBA is shown to achieve infegr B[][V\(<=")133 = ((ogg(T)TT) with decreasing step sizes. We prove that SABA with fixed step sizes achieves +. E E|| [(( O(+). SABA is therefore, to the best of knowledge, the first stochastic bilevel algorithm that matches the convergence rate of gradient descent h. We also prove that SABA achieves linear convergence under the assumption that satisfies a Solyykk-Lojasciewice inequality. To the best of our knowledge, SABA is also the first stochastic bilevel algorithm to feature such property. Importantly, these rates match the rates of the single level counterparts of each algorithm in non-convex setting (SGD for SOBA and SAGA for SABA). Finally, in Section 4, provide extensive benchmark of many stochastic bilevel methods on hyperparameters selection and data cleerncl and illustrate the usefulness of our approach.
Related work. The bilevel optimization problem has strong history in the optimization community. taking root in game theory [45]. Gradient trasient-bbsed algorithms solve (1) can be mainly classified in two different categories depending on how Vh is computed, by automatic or implicit differentiation.
Since the solution of the inner problem =² (xx) is approximated by the output of an iterative algo- rithm, it is possible to use automatic differentiation [46, 31] to approximate Vh(xr). It consists in differentiating the different steps of the inner optimization algorithm see [4] for a review - and has been applied successfully to several bilevel problems arising in machine learning [14, 16]. One

---

of the main drawbacks of this approach is that it requires to store in memory each iterate of the inner optimization algorithm, although this problem can sometimes be overcome using invertible optimization algorithms [34] or truncated backpropagation [44].
The use of the implicit function theorem to obtaín (2) and (3) is known as implicit differentiation [5]. While the cost of computing exactly (2) can be prohibitive for large scale problems, Pedregosa [38] showed that we can still converge to stationary point of the problem by using approximate solutions of the inner problem and linear system (3), if the approximation error gocs to 0 sufficiently quickly.
The complexity of approximate implicit differentiation has been studied in [20]. Ramzi et al. [39] propose to reuse the computations done in the forward pass to approximate the solution of the linear system (3) when the inner problem is solved thanks to guasi-Newtoon method.
In the last few years, several works have proposed different strategies to solve (1) in stochastic fashion. A first set of methods relies on two nested loops: one inner loop to solve the inner problem with stochastic method, and one outer loop to update the outer variable with approximate gradient direction. In [19, 26, 9] the authors use several SGD iterations for the inner problem and then use stochastic Neumann approximations to get an estimate solution of the linear system, which provides them with an approximation of Vh used to update x. The analysis of this kind of method was refined by Chen et al. [9], allowing achieve the same convergence rates as those of SGD. The convergence of the hypergradient when using stochastic solvers for the inner problem and the linear system has been studied in [21]. Arbel and Mairal [2] replace the Neumann upproximation by SGD steps to estimate (3). Other authors have proposed single loop algorithms, alternating steps in the inner and the outer problem. Hong et al. [24] propose to perform Neumann approximations of the inverse Hessian and use single SGD step for the inner problem. It was refined in [23] and [47] where the optimization procedure uses a momentum acceleration. Other variations around this idea include [25, 28, 10, 22, 30j. We refer to Table in appendix for detailed comparison of these methods.
The set of integers between and (included) is denoted [m]] For f :e x Rd - R, we denote (z, a) its gradient w.r.t. the jth variable. The Hessian of f with respect to the first variable is denoted f2, E RPxp, and the dross-derivatives matrix is V2, f(, x) E Raxr, If is a vector, ||e|]| is its Euclidean norm. If M is matrix, [| is its spectral norm. A function is said to be I-smooth, for I, 7 0, if it differentiable, and its gradient is I--Lipschit
Notation.
Proposed framework
In this section, we introduce our framework in which the solution of the inner problem, the solution of the linear system (3) and the outer variable all evolve at the same time, following directions that are written as a sum of derivatives of F3 and G,. We define
Algorithm 1 General framework
Input: initializations 2n E RP, xp E Rdd Un E RR, number of iterations T, step size sequences (0') and (7*) do
for 0, 0...., T
D2(2, V=G(z,
(4)
Update 8: 2 2+1 = x² - p''D'
D,(2,0,z) V
21F(2,2)
(5)
Update v: u11
v² D
Update æ; x++1 = x² DD
D2(2, = G2, + (2F(2,
(6)
where D DJ and D', are unbiased esti- mators of D=(2", o²,x")) Do(2", v v²)
These directions motivated by the fact that we have Vh(x) = (x u" (x)),), with 2*(x) (x) the minimizer of G(-, x) and o (z) the solution of "T)((=")),,))) = - F2F (z),z). x). When x is fixed, approximate 2" by doing a gradient descent G, following the direction D2 (2, v, xr). Finally, when 2 and x are fixed, we find 2² by following the direction - -D, U, 2). which corre- sponds gradient descent devoted to the study of the global dynamics where the three variables =, v and x evolve at the same time, following stochastic approximations of D2, D, and Dz. The next proposition motivates the choice of these directions.
and (, v² x*).. end for
- 3 (V; G(2, z)v, u) + FV, x), v). The rest of the paper is
Proposition 2.1. Assume that for all E Rd, G(+,z) is strongly convex. If (z, v, is zero of (D., D., Dz), then 2 = 2n (x)x,, -= (z) and Vh(z)= 0.
We also note that the computation of these directions does not require to compute the matrices Gz, and V2,G(z, G(2 we only need to compute their product with vector, which can be computed at cost similar to that of computing gradient.
3

---

The framework we propose is summarized in Algorithm 1. It consists in following a joint update rule in (z, v, 2) that follows directions D D and D that are unbiased estimators of Dz, D,. Da- The first and most important remark is that whereas Vh cannot be written as a sum over samples, the directions D2, Dy and D2 involve only simple sums, since their expressions are "linear" in F and G:
D,(2,0,))= + E ViGi(z,z), D,(2, E (2, I Eド= (2,)(2,2) w (2,,( the Eラ (2,)(
(8)
It is therefore straightforward to derive unbiased estimators of these directions. In [30], the authors considered one particular case of our framework, where each direction is estimated by using the STORM variance reduction technique (see [12]). Taking a step back by proposing the framework sum- marized in Algorithm I opens the way to potential new algorithms that implement other techniques that exist in stochastic single level optimization. In what follows, we study two of them.
2.1 First example: the SOBA algorithm
The simplest unbiased estimator obtained by replacing each mean by one of its terms chosen uniformly at random, akin to what is done in classical single-level SGD. We call the resulting algorithm SOBA (StOchastic Bilevel Algorithm). To do so, we choose two independent random indices i E [n]] and j E [m]] uniformly and estimate each term coming from G using G; and each term coming from F using F,. This gives the unbiased SOBA directions
D' = VIGi(z',
(10a)
D' = Vi j'))'= + VIEA(E",a") D = V o')'"' + (2F3(2t,
(10b)
(10c)
This provides with a first algorithm, SOBA, where we plug Equations (10a) (10c) in Algorithm 1. We defer its analysis to the next section. Importantly, we use different step sizes for the update in (z, v) and for the update in x. We use the same step size in z and in u since the inner problem and the linear system have similar conditioning, which is that of Vi G(2,, The need for a different step size for the outer and inner problem clear: both problems can have different conditioning.
An important remark for SOBA is that all the stochastic directions used are computed at the same point 2', of and z' with the same indices (t. The update of 2, V and x can thus be performed in parallel instead of sequentially, benefiting from hardware parallelism. Moreover, this enables to share the computations between the different directions. This is the case in hyperparameters selection where G, x²- = 6((2, dz)) + _| with d, a training sample, and E that measures how good is the prediction (z, d.). In this setting, we have V (,G](z,x) x) = (, dd) + x= and G,, (2) = ("( (r, d.)d, The prediction (z, d,) can thus be computed only once to obtain both quantities. For more complicated models, where automatic differentiation is used to compute the different derivatives and Jacobian- vector products, we can store the computational graph only once to compute at the same time (2,, z), V G2, and V G2 x Z)U, requiring only one backward pass, thanks to the R technique [37].
Finally, like all single loop bilevel algorithms, our method updates at the same time the inner and outer variable, avoiding unnecessary optimization of the inner problem when x far from the optimum.
2.2 Global variance reduction with the SABA algorithm
In classical optimization, SGD fails reach optimal rates because of the variance of the gradient estimator. Variance reduction algorithms aim at reducing this variance, in order to follow directions that are closer the true gradient, and to achieve superior practical and theoretical convergence.
In our framework, since the directions D., D. and Dz are all written as sums of derivatives of Fj and G, it is easy to adapt most classical variance reduction algorithms. We focus on the celebrated SAGA algorithm [13]. The extension we propose is called SABA (Stochastic Average Bilevel Algorithm). The general idea is to replace each sum in the directions D by a sum over a memory, updating only one term at each iteration. To help the exposition, we denote y (z, xr v) the vector of joint variables. Since we have sums over and over j. we have two memories for each variable: w/ for E [r] and ü. for j E [m], which keep track of the previous values of the variable y.

---

At each iteration f, we draw two random independent indices i E [n] and j E [m]] uniformly and update the memories. To do so, we put w y and w = w for i' * i, and w = =y' and By ui. for j' # j. Each sum in the directions D is then approximated using SAGA-like rules: given functions 6y for i' E [n], we define Siø, w|; = (:(w ) dr(w;)) + Er= or (wb)) This is an unbiased estimators of the average of the Ø's since E, [ w|
With a slight abuse of notation, we call Vi Ge the sequence of functions (y G2, and V2 GV the sequence of functions (y + V (2) We define the SABA directions
D SIV G, w|i
(1aa
D SiV Gu, w|i + FI W1}
(11b)
D = SIV Gu, w|| SIV2F, زال
(11c)
These estimators are unbiased estimators of the directions Dz. Dr and Dg. The SABA algorithm corresponds Algorithm where we use Equations (1 to (1lc) as update directions. When taking step size y O in the outer problem, hereby stopping progress in z, we recover the iterations of the SAGA algorithm on the inner problem. In practice, the sum in S is computed by doing a rolling average (see Appendix B for precision), and the quantities (x(w() are stored rather than recomputed: the cost of computing the SABA directions is the same as that of SGD. It requires an additional memory for the five quantities, of total size x + (n + m) x (p + d) floats that can be reduced by using larger batch sizes. Indeed, if bm and bout are respectively the inner and the outer batch sizes, the memory load is reduced to n p + (na ms) x (p x d) with 7s b and m which are smaller than the number of samples. This memory load can also be reduced my bent in specific cases, for instance when G and F correspond to linear models, where the individual gradients and Hessian-vector products are proportional to the samples. In this case, we only store the proportionality ratio, reducing the memory load to 3n + 2m floats. Like for SOBA, the computations of the new quantities db (w(+) are done in parallel, thus benefiting from hardware acceleration and shared computations. Despite this memory load, using SAGA-like variance reduction instead of STORM as done in [30, 47, 28] has the advantage to bring the variance of the estimate directions to zero, enabling faster ) convergence.
In the next section, we show that SABA is fast. It essentially has the same properties as SAGA: despite being stochastic, it converges with fixed step sizes, and reaches the same rate of convergence as gradient descent on h.
3 Theoretical analysis
In this section, we provide convergence rates of SOBA and SABA under some classical assumptions. Note that, unlike most of the stochastic bilevel optimization papers, we work in finite sample setting rather than the more general expectation setting. Actually, SABA does not make any sense for functions that don't 't have finite sum structure. However, we stress that SOBA could be studied in a more general setting to obtain the same bounds as here. Also, the finite sum setting still interesting since doing empirical risk minimization is very common in practice in machine learning. The proofs and the constants in big-O are deferred in Appendix C.
3.1 Background and assumptions
We start by stating some regularity assumptions on the functions F and G. Assumption 3.1. The function F is twice differentiable. The derivatives F and 2 are Lipschitz continuous in (2, .) with respective Lipschitz constants L and L3.
Note that the above assumption is typically verified in the machine learning context, egg. when F is the ordinary least squares (OLS) loss or the logistic loss.
Assumption 3.2. The function G is three times continuously differentiable on R2 Rd. For any x E Rd, G( ((x)) is pt-strongly convex. The derivatives VG, V²G and V are Lipschitz continuous in (2, x)) with respective Lipschitz constants L Lb and Lg.
Strong convexity and smoothness with respect to z of are verified when G is a regularized least- squares/logistic regression with a full rank design matrix, when the data is not separable for the
5

---

logistic regression. Moreover, the strong convexity ensures the existence and uniqueness of the inner optimization problem for any I E R..
Assumption 3.3. There exists CF
such that for any we have [=)) < Cf.
This assumption, combined with the strong convexity of 2.),))). shows boundedness of v². This assumption holds, for instance, in the case of hyperparameters selection for a Ridge regression problem. Note that in Assumptions 3.1 and 3.2, assume more regularity of F and G than in stochastic bilevel optimization literature (see for instance [19, 24, 26, 21). It is necessary to get the smoothness of v² which will allow to adapt the proof of Chen et al. [9] and get tight convergence rates. The following lemma gives us some smoothness properties of the considered directions that will be useful to derive convergence rates of our methods.
Lemma 3.4. Under the Assumptions 3.1 to 3.3, there exist constants Lg Ly and Ly such that [D, < 1 - 2" (=))) [2,
< 1 (x)] + 1| - (x))) and
(2((2, ? & =2 2" (z)]l² + - (z)
In first order optimization, a fundamental assumption on the objective function is the smoothness assumption. In the case of vanilla gradient descent applied to a function f. it allows to get a convergence rate of ||V [(²")| in O(1/T), i.e. convergence to stationary point [36]. The following lemma proved by Ghadimi and Wang [19, Lemma 2.2] ensures the smoothness of ht
Lemma 3.5. Under the Assumptions 3.1 to 3.3, the fanction h is L L for some L 0.
The constant L is specified in Appendix C.3. As usual with the analysis of stochastic methods, we define the expected norms of the directions V = [B[]] D' V = Ei]l D [2] and V = EE[ D [2] where the expectation is taken over the past. Thanks sum of the variance of the stochastic direction and the squared-norm of the unbiased direction. For SOBA, use classical bounds on variances like those found for instance in [24]:
variance-bice decomposition, they are the
Assumption 3.6. There exists Bz. B. and Bz I I B1 + || v', x')13) and EMI where E, denotes the expectation conditionally to (2", "'' x²).
such that for all
B2 + [|Do v x²,x)))13))
For SOBA and SABA, need to bound the expected norm of D For SABA, this assumption allows to get a the same sample complexity as SAGA for single level problems.
Assumption 3.7. There exists B2 such that for all t, E,,1 D [|3] S B².
Assumptions 3.6 and 3.7 are verified for instance, if all the G, and ViG; have most quadratic growth, and if F has bounded gradients. They are also verified if the iterates remain in a compact set. Note that do not assume that G has bounded gradients, this would contradict its strong-convexity. Finally, for the analysis of SABA, we need regularity on each G2 and Fj:
Assumption 3.8. For all E [n] and j E [m], the functions VG VFJ Gi and V G. are Lipschitz continuous in (z, r).
3.2 Fundamental descent lemmas
Our analysis for SOBA and SABA is based on the control of both 6 = =1 (xx))) and & E']l'' 0- (a*)ll²), Strong convexity of G and smoothness of 2n (2) and e (z) allow obtain the following lemma by adapting the proof of Chen et al. [9]. In what follows, we drop the dependency of the step sizes p and y & for clarity.
Lemma 3.9. Assume that x2 < min
L
L
p. We have:
4
8.+1 < (1
PPG
8- + +22p + 1 + B
22
E Dz D2 "",,v",="))
4
p
8e+1 < (1
PHG
8¹ + Buupo _ + +2p² V² + Bux 2 V2' + +3 +3_,, 22
Dx v xP)
8
p
where Boz = Bux = 3L2, 3
SL2 3
1622 L, is the maximum between the Lipschitz
nG
nG
constants of z" and v" (see Lemma C.I), Boz
- pG + LG),, Lae and Loz are respectively
the smoothness constants of 2" and v".

---

We insist that this result is obtained in general for Algorithm with arbitrary unbiased directions. We can therefore invoke this lemma for the analysis of both SOBA and SABA. We use the smoothness of h to get the following lemma, which is similar to 19, Lemma l].
Lemma 3.10. Let h = E[h(a')) and g' = EIl Vh Vh(=")11? )|P].
We have
T. 11 + ? 1 8)) +
7 D h+1 $ h' 20¹ 2
2 7 V
If 2f 2x²) v² 1* (x*). that is dz. d, both cancel and D ut ,t,x²) Vh(a*), we get an inequality reminiscent of the smoothness inequality for SGD on h.
3.3 Analysis of SOBA
The analysis of SOBA is based on Lemmas 3.5 and 3.9. We have the following theorem, with fixed step sizes depending the number of iterations:
Theorem 1 (Convergence of SOBA, fixed step size). Fix an iteration T and assume that Assumptions 3.1 to 3.7 hold. We consider fixed steps pz vT and 7" Ept with p and & precised in the appendix. Let (1)))21 the sequence of outer iterates for SOBA. Then,
As opposed to [24], do not need that the ratio م goes 0, which allows to get complexity (that is, the number of call to oracles to have an e-stationary solution) in O( better than the Ō ) they have. Also, note that this rate is the same the one of SGD for non-convex and smooth objective [18, 8]. We obtain a similar rate using decreasing step sizes:
Theorem 2 (Convergence of SOBA, decreasing step size). Assume that Assumptions 3.1 to 3.7 hold. We consider steps p' = pt and 7¹ = Ep. Let x' the sequence of outer iterates for SOBA. Then,
inf (h(2 = ((lo((T)T=))
As for SGD, SOBA suffers from the need of decreasing step sizes to get actual convergence because of the variance of the estimation each directions. On the other hand, the analysis of SABA leverages the dynamic all three variables, resulting in fast convergence with fixed step sizes.
3.4 SABA: a stochastic method with optimal rates
In what follows, we denote N n + m the total number of samples. The following theorem shows Ó(N convergence for the SABA algorithm in the general case where we only assume smoothness of h. Our analysis of SABA is inspired by the analysis of single-level SAGA by Reddi et al. [40].
Theorem (Convergence of SABA, smooth case). Assume that Assumptions 3.1 to 3.3 and 3.7 to 3.8 hold. We suppose p =p N and = Ep. where p' and & depend only on and G and are specified in appendix. Let x the iterates of SABA. Then,
T M T
EIIV (N3T-1)
To prove the theorem, the idea is to control the distance from the memory to the current variables. We define 5 = Σi= Ily w + 1 E Ily' - 1 In appendix, we show that we can find scalars Φ., Φz, Φ. > 0 such that the quantity L = he' + St + 0 + 6.6%, satisfies L++ < L 3g. Summing these inequalities for t = 1... T and using the fact that L' is lower bounded demonstrates the theorem.
Note that the step sizes are constant with respect to the time, but they scale with N- As consequence, the sample complexity is O(N 3(N3e =1= which is analogous of the of SAGA for
7

---

non-convex single level problems [40]. This is better than the sample complexity of Algorithm 1 with full batch directions, which O(Ne )) Hence, with SABA, we get the best of both worlds: the stochasticity makes the scaling in N of the sample complexity goes from N in full batch mode to N for SABA, and the variance reduction makes the scaling in goes from e for SOBA to e for SABA. Our experiments in Section confirm this gain.
Furthermore, if we assume that h satisfies convergence. Recall that h has the PL property if there exists 14 > 0 such that for all x E Rd. 2 2/V/((=)]1 2 pm. (h(x))) h²) with h" the minimum of h.
Dolyak-Lojasiewice (PL) inequality, we recover linear
Theorem 4 (Convergence of SABA, PL case). Assume that h satisfies the PL inequality and that Assumptions 3.1 to 3.3 and 3.7 to 3.8 hold. We suppose = p'N- and 7 Ep'N-', where pl and & depend only on F and G and are specified in appendix. Let x' the iterates of SABA and c' A min (Mh, I with P' specified in the appendix. Then,
B(h"] - h' = (1
h- CO)
where C is a constant specified in appendix that depends on the initialization of z, v, x and memory.
The proof is similar to that of the previous theorem: we find coefficients 6.. Oz Or such that L = ht + o.S² + Φ262 + Φ,,6 satisfies the inequality L (1 d'7)c', which is then unrolled. Note that in the case where we initialize and with 29 = = (x²), ), v0 v" (*()), and the memories wp = wo, wP = w for all j. the constant C cancels and the bound simplifies to E[h(=") hi S (1 (M(=)) h*).
Just like classical variance reduction methods in single-level optimization, this theorem shows that our method achieves linear convergence under PL assumption on the value function. To the best of our knowledge, our method the first stochastic bilevel optimization method that enjoys such property. We note that the PL hypothesis is more general than psa-stonn convexity of h it is necessary condition for strong convexity.
We see here the importance of global variance reduction. Indeed, using variance reduction only on and SGD on æ would lead to sub-linear convergence in z. This would be the case even with perfect estimation of 2 (x)) Similarly, using variance reduction only on x and SGD lead to sub-linear convergence in 2, and hence x. Using global variance reduction with respect to each variable as we propose here is the only way achieve linear convergence. We now turn to experiments, where we find that our method is also promising from a practical point of view.
would
4 Experiments
Here we compare the performances of SOBA and SABA with competitor methods on different tasks. The different methods being compared are stocBiO [26], AmiGO [2], FSLA [30], MRBO [47], TTSA [24], BSA [19] and SUSTAIN [28]. A detailed account of the experiments is provided in Appendix B.
4.1 Hyperparameters selection
The first task we perform is hyperparameters selection to choose regularization parameters on (
f logistic regression. Let us denote ((drrain . ( and ((d)a), .y s the training and the validation sets. In this case, the inner variable 0 corresponds to the parameters of the model, and the outer variable to the regularization. The functions F and G of the problem (I) are the logistic loss, with e² penalty for G. that is to say ((O,A) = 11222 -m ((y) yal (dtal, 0)) and G(O, A) n Σ (Pyy.riin (dtrain 0)) + Eh= e>x where (²))) log(1 4). We fit binary classification model on the 2 dataset. Here, 49 990, m 91 701 and p = 22.
The suboptimality gap is plotted in Figure 2a for cach method. The lowest values are reached
3 SABA. Moreover, SABA the only single-loop method that reaches a suboptimality below 10
SOBA reaches a quite high final value but slightly better than TTSA and FSLA. The gap between
'The code of the benchmark available at https: http:::///tttbbb// com wwwp:///ewwooo//beeeeeieieeeeeee wwwpehhhpppteeeccmr...... biieeelbbbllllleeeeeee and the results are displayed in https: /tap::////bccopttt github. wtw.i//eete/eeenceeieeeeeeeeeeee bilevel. html. https: / /wwww csie. ntu, edu. wttptttttt//////t/ettttttttttttt http:cchhhh/illooooooooa/aaaaaaa
html
8

---

MRBO
StoCEIO
Optimality M(ce)
Text ercee
SUSTAIN
SABA
FSLA
50BA
AmiGO
SOBA FULL BATCH
Time [[a]]
Time [sxc]
(a) Logistic regression
(b) Datacleaning
Figure 2: Comparison of SOBA and SABA with other stochastic bilevel optimization methods. For each algorithm, we plot the median performance over 10 runs. In both experiments, SABA achieves the best performance. The dashed lines are for one loop competitor methods, the dotted lines are for two loops methods and the solid lines the proposed methods. Left: hyperparameter selection for t penalized logistic regression on IJCNII dataset, Right: data hyper-clcaning on MNIST with p 0.5 corruption rate.
SOBA and SABA highlights the benefits of variance reduction: it gives us a lower plateau and the fixed step sizes enable faster convergence.
4.2 Data hyper-cleaning
The second task we perform is data hyper-cleaning introduced in [16] on the MNIST dataset. The data patitioned into training set (ditain,, y/ y validation set (dyal, y ) and a test set. The training set contains 20000 samples, the validation set 5000 samples and the test set 10000 samples. The targets y take values {O.... ..... 9} and the samples æ are dimension 784, Each sample in the training set is corrupted with probability p: sample is corrupted when we replace its label yı by a random label {0, ..... 9). Samples the validation and test sets are not corrupted. The goal of datacleaning is to train multinomial logistic regression on the train set and learn weight per training sample, sa
that should go to for corrupted samples. This is formalized by the bilevel optimization problem vfraai)) + 1+ where l the cross entropy loss and a is the sigmoid function. The inner variable is a matrix of size 10 x 784, and the outer variable À is a vector in dimension Altrain 20000.
(1) with F(B, A)
-i=1 L(Odpal, ))a and G(e, A) >
n (A:)
For the estimated parameters during optimization, we report Figure 2b the test error, i.e., the percent of wrong predictions the testing data. We use for this experiment a corruption probability p = 0.5. In general, the error decreases quickly until it reaches a final value. We observe that our method SABA outperforms all the other methods by reaching faster its smallest error, which is smaller than the ones the other methods. For SOBA, it reaches a lower final error than stocBiO and BSA. In appendix, we provide other convergence curves, and find that for higher values of p. SABA is still the fastest algorithm to reach its final accuracy. Overall, we find that among all methods, even those that implement variance reduction (that is FSLA, MRBO, SUSTAIN, SABA), SABA is the that demonstrates the best empirical performance.
5 Conclusion
In this paper, have presented framework for bilevel optimization that enables the straightforward development of stochastic algorithms. The gist of our framework is that the directions in Equations (4) to (6) are all written as simple sums of samples derivatives. We leveraged this fact to propose SOBA, an extension of SGD to our framework, and SABA, an extension of SAGA to our framework. which both achieve similar convergence rates as their single level counterparts. Finally, we think that our framework opens a large panel of potential methods for stochastic bilevel optimization involving techniques of extrapolation, variance reduction, momentum and so on.
Acknowledgments and Disclosure of Funding
We thank Othmane Sebbouh, Zaccharie Ramzi and Benoît Malézieux for their precious comments. The authors acknowledge the support of the ANER RAGA BFC. SV acknowledges the support of
Phttp:/ /httpn//yann.. Lecun. www./unccooeeeeeeooooeeeeeeeeeee wxdp/mnsst/

---

the ANR GraVa NAR-18-CE40-ORR This work is supported by a public grant overseen by the French National Research Agency (ANR) through the program UDOPIA, project funded by the ANR-20-THIA-0011--0 and DATAIA convergence institute (ANR-17-CONV-00033)
References
[1] Zeeshan Akhtar, Amrit Singh Bedi, Srujan Teja Thomdapu, and Ketan Rajawat. Projection- Algorithm for Stochastic Bi-level Optimization, preprint ArXiv 21 1
[2] Michael Arbel and Julien Mairal. Amortized Implicit Differentiation for Stochastic Bilevel Optimization. In International Conference on Learning Representations (ICLR), 2022.
[3] Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep Equilibrium Models. In Advances in Neural Information Processing Systems (NeurlPS). Curran Associates, Inc., 2019.
[4] Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in Machine Learning: A survey, Journal of Machine Learning Research, 18(153): -43, 2018.
[5] Yoshua Bengio. Gradient-Baser Optimization of Hyperparameters. Neural Computation, 12(8): 1189-19000 2000.
[6] Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gramfort, and Joseph Salmon. Implicit differentiation of lasso-type models for hyperparameter opti- mization. In International Conference on Machine Learning (ICML), pages 810-821. PMLR, 2020.
[7] Léon Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. In Proceedings of COMPSTAT, pages 177-186. Physica-Verlag HD, Heidelberg, 2010.
[8] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale Machine Learning. Siam Reviews, 60(2):223-3) -11, 2018.
[9] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the Gap: Tighter Analysis of Alternat- ing Stochastic Gradient Methods for Bilevel Problems. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2021.
[10] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Single-Timescal Timescale Stochastic Bilevel Optimization Method. In International Conference on Arlificial Intelligence and Statistics (AISTATS), 2022.
[11] Ekin D. Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V. Le. AutoAugment: Learning Augmentation Strategies From Data. In CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 113-123. IEEE, 2019.
[12] Ashok Cutkosky and Francesco Orabona. Momentum-basse based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2019.
[13] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. In Advances in Neural Information Processing Systems (NeurIPS), volume 28, pages 1646-1654, Montreal, QC, Canada, December 2014. Curran Associates, Inc.
[14] Justin Domke. Generic methods for optimizzation-basee modeling. In International Conference on Artificial Intelligence and Statisties (AISTAT), volume 22, pages 318-326. PMLR, 2012.
[15] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near- Pear-Optimal Non- Convex Optimization via Stochastic Path Integrated Differential Estimator. In Advances in Neural Information Processing Systems (NeurIPS), 2018
[16] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165-1173. PMLR, 2017.
10

---

[17] Luca Franceschi, Paolo Frascomi, Saverio Salzo, Riccardo Grazzi. and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning (ICML), pages 3568-157. PMLR, 2018.
[18] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2331 2013. doi: 10.1137/ 120880811. 1.
[19] Saeed Ghadimi and Mengdi Wang. Approximation Methods for Bilevel Programming, preprint ArXiv 1802.02245 2018.
[20] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning (ICML), pages 3748-3758. PMLR, 2020.
[21] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Convergence properties of stochastic hypergradients. In International Conference on Artificial Intelligence and Statistics (AISTAT), pages 38344. PMLR, 2021.
[22] Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized Stochastic Variance- Reduced Methods for Multi-Task Stochastic Bilevel Optimization. preprint ArXiv 2105.02266, 2021.
[23] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On Stochastic Moving-Average Estimators for Non-Convex Optimization. preprint ArXiv 1404.14840, 2021.
[24] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A Two-Timessen Framework for Bilevel Optimization: Complexity Analysis and Application Actor-Critic, preprint ArXiv 2007.05170, 2021.
[25] Feihu Huang and Heng Huang. BiAdam: Fast Adaptive Bilevel Optimization Methods, preprint ArXiv 2/06. / 1396, 2021.
[26] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. International Conference on Machine Learning (ICML), pages 4882 4892. PMLR, 2021.
[27] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems (NeurlPS), volume 26. Curran Associates, Inc., 2013.
[28] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentun In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2021.
[29] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A Ilvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, pages 1-6, 2015.
[30] Junyi Li, Bin Gu, and Heng Huang. A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. In Proceedings of the Thirty-sixth AAAI Conference on Artificial Intelligence, AAAI'22, 2022.
[31] Seppo Linnainmaa. Taylor expansion of the accumulated rounding error. BIT Numerical Mathematics, 16(2):146-160, 1976.
[32] Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1-3):503-522 1989.
[33] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2018.
[34] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- hyperparameter opti- mization through reversible learning. International Conference on machine learning (ICMI.), pages 11222222. PMLR, 2015.
11

---

[35] Thomas Moreau, Mathurin Massias, Alexandre Gramfort, Pierre Ablin, Pierre-Antoine Ban- nier Benjamin Charlier, Mathieu Dagréou. Tom Dupré la Tour, Ghislain Durif, Cassio F. Dantas, Quentin Klopfenstein, Johan Larsson, En Lai, Tanguy Lefort, Benoit Malézieux, Badr Moufad, Binh TT Nguyen, Alain Rakotomamoniy, Zaccharie Ramzi, Joseph Salmon, and Samuel Vaiter. Benchopt: Reproducible, efficient and collaborative optimization benchmarks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[36] IU E. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Number v. 87 in Applied Optimization. Kluwer Academic Publishers, Boston, 2004.
[37] Barak Pearlmutter. Fast exact multiplication by the hessian. Neural compulation, 6(1): 147-160, 1994.
[38] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pages 737-746. PMLR, 2016.
[39] Zaccharie Ramzi, Florian Mannel, Shaojie Bai, Jean-Luc Starck, Philippe Ciuciu, and Thomas Moreau. SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models. In International Conference on Learning Representations (ICLR), 2022.
[40] Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, and Alex Smola. Fast Incremental Method for Nonconvex Optimization. In 2016 IEEE 55th Conference Decision and Control (CDC), IEEE, pages 1971-1977, 2016.
[41] Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, 2203):400-477, 1951.
[42] Cédric Rommel, Thomas Moreau, Joseph Paillard, and Alexandre Gramfort. CADDA: Class- wise Automatic Differentiable Data Augmentation for EEG Signals. In International Conference on Learning Representations (ICLR), 2022.
[43] Mark Schmidt, Nicolas Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162((-2):83-11) 2017.
[44] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated Back- propagation for Bilevel Optimization. In Artificial Intelligence and Statistics (AISTAT), pages 1723-1732, Okinawa, Japan, 2019.
[45] Heinrich von Stackelberg. Theory of the market economy. Oxford University Press, 1952.
[46] R. Wengert, A simple automatic derivative evaluation program. Communications of the ACM, (8):4634464 1964.
[47] Junjie Yang. Kaiyi Ji, and Yingbin Liang. Provably Faster Algorithms for Bilevel Optimization. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section and Section 4
(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 including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix C
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
URL)? [Yes] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/]]
13


Reviews:
[{"review_id": "yhN9m0WX-4t", "reviewer": "Reviewer_HH9R", "summary": "In this paper, the author consider a finite-sum stochastic bilevel optimization problem:\n$$\\min_x F(x,z)\\qquad s.t. \\qquad z = \\arg\\min_{z'} G(x,z')$$\nwhere $F(x,z) = \\frac{1}{m} \\sum_{i=1}^m F_i(x,z)$, $G(x,z) = \\frac{1}{n} \\sum_{j=1}^n G_j(x,z)$, and $G$ is strongly convex. \nFor $h(x) = F(x,z^*(x)), z^*(x):=\\arg\\min_{z'} G(x,z')$, it is known that the gradient of $h$ can be written as \n$$\\nabla h(x) = \\nabla_x F(x,z^*(x)) - \\nabla_{xz}G(z^*(x),x)\\nabla_{zz}G(z^*(x),x)^{-1}\\nabla_zF(x,z^*(x)).$$\nDue to the finite sum feature of the objective function, it may not be easy to estimate the matrix inverse in the above formula. However, one should notice that $\\nabla_{zz}G(z^*(x),x)^{-1}\\nabla_zF(x,z^*(x)) = \\arg\\min_v \\frac{1}{2}v^T\\nabla_{zz}G(z^*(x),x)v - v^T\\nabla_zF(x,z^*(x))$, the authors propose to update $v$ and $z$ by one step of the gradient descent while updating $x$ by one step of ``gradient descent'' where the inverse-vector product is replaced with $v$. \n\nCompared to many previous algorithms, the proposed framework is matrix-inversion free and is very convenient to incorporate the SGD or SAGA variance reduction technique. \n\nThe reviewer think the proposed framework for stochastic bi-level optimization is convenient and  flexible. Most importantly, it is conceptually simple and implementation friendly.  However, the current work also has some room to improve. For example, for a typical finite-sum/stochastic optimization problem, the efficiency measure should be sample complexity or oracle complexity, instead of the iteration complexity that is presented in this work. Finally, the sample complexity dependence of SABA on $m+n$ is linear, which is a bit confusing to me since SAGA usually improve the dependence to $(m+n)^{2/3}$.\n\nOverall, the paper does provide some novel and interesting ideas. However, the theoretical result does not justify the reason for using variance reduction. If the authors can answer this question, the reviewer is very willing to adjust to a higher rating. ", "questions": "Major issue. \n1. Please discuss the sample complexity in the paper, in particular the dependence on m and n. This is because when we use sample average approximation to construct the empirical objective function, $m,n$ are often very large (In fact they are $\\Omega(\\epsilon^{-1})$, where $\\epsilon$ is for measuring $\\|h(x)\\|^2$)\n2. The authors should carefully justify why SAGA scheme does not provide any theoretical improvement over full batch method. \n\nMinor issue. \n1. The term ``global'' in the title is confusing, I'm not sure what this global means. \n2. In the appendix, in the table that list the complexity of the algorithms, a ``)'' is missing for SABA.\n", "limitations": "NA. This is a theoretical paper. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength \\# 1: The framework is new and is conceptually simple and is very flexible to incorporate different variance reduction techniques. \nStrength \\# 2: The whole algorithm is Hessian inverse free, which is easy to implement. (Though this is not the only work that is matrix inverse free)\nStrength \\# 3: The paper is very clear and well organized. Very well-written and easy to follow. \n\n\nWeakness \\# 1: The main theorems in the main paper only discuss iteration complexity instead of sample complexity. \nWeakness \\# 2: The sample complexity in the appendix for SABA  is $O((m+n)\\epsilon^{-1})$, which seems exactly the same as the full batch deterministic version of the algorithm. Theoretically, this does not provide any advantage of using SAGA variance reduction scheme. \nI'm confused why SAGA doesn't improve the factor $(m+n)$ to $(m+n)^{2/3}$. ", "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": "PITZtkbRMtY", "reviewer": "Reviewer_AcuN", "summary": "This work studies fully single-loop stochastic algorithms for bilevel optimization problems where the inner problem is strongly convex and the inner and outer objective are smooth and given by a finite sum. In particular, it provides a unified framework where outer ($x$) and inner ($z$) variables  together with the variable used to solve a linear system in the bilevel gradient expression ($v$), evolve jointly. The authors propose 2 methods: SOBA and SABA. SOBA  updates $x, z, v$ similarly to single-level SGD and uses two-timescales decreasing step-sizes for the inner and outer variable, while SOBA uses variance reduction with constant step-sizes, similarly to SAGA, thus taking advantage of the finite-sum structure of the problem. The authors prove $O(T^{2/5})$ and $O(1/T)$ stationary point rates, where $T$ is the number of iterations, for SOBA and SABA respectively. Furthermore, SABA converges linearly to the solution when on bilevel problems satisfying the PL-condition. Experiments in optimizing one regularization parameter per feature on IJCNN1 and data hyper-cleaning on MNIST show that SABA outperforms several other bilevel methods introduced recently.\n", "questions": "I have the following questions and comments.\n\n- Authors say that the sum to compute the variance reduced gradients in SOBA is done in practice using a rolling average (Lines 177-178). Is this the case also in the presented experiments? If so it should be stated more explicitly. How is the rolling average computed exactly? I could not find details on this in the Appendix and I think they should be included. The authors should comment on the fact that this approximation is not covered by the theoretical analysis and maybe do an experiment comparing the exact and approximate average.\n\n- The authors should add the finite sum assumptions in the abstract to make it clearer, since it is not standard in the related literature on bilevel rates.\n\n- Can the analysis of SOBA be improved following [1]? The main difference between the two methods is that [1] uses a Neumann series approximation for the hypergradient, while SOBA updates the linear system variable online. What are the challenges in obtaining the rates in [1]? Explaining this could strengthen the paper.\n\n- Line 294-299: on the “real” sample complexity of SABA and SOBA in full batch mode. The authors say that the step-sizes in SABA are proportional to the inverse of the number of examples, which makes the sample complexity of SABA and SOBA using all the examples (full batch mode) equal, while empirical results show that SABA performs better. Isn’t this because the analysis does not take into account the correlations between the single sample gradients? I believe the stronger this correlation, the stronger the gap between SABA and SOBA full batch.\n\n- Plots for the experiments show how the performance varies over time. It could be interesting to see how the performance varies also in terms of the number of single sample gradients and jacobian vector products, which is not dependent on the hardware used.\n\n- The authors present rates also under the PL-condition for the outer objective. Are there some interesting bilevel applications where this condition holds? If so, an experiment under this setting could improve the paper.\n\n- Figure 1 shows SOBA and SABA performance in a toy problem. I could not find any detail on the specific problem. I suggest either to remove Figure 1 or to add some, even brief, details in the main body and/or in the Appendix. \n\n\n\nMinor:\n- Line 59 and 61: I think there should be an expectation in the inequalities for the rates. \n\n- Lines 93-96: reference to Hong et al.. Do the authors mean that only one element of the Neumann series is used? This is incorrect since they use more than one in that paper. I also found that paragraph a bit too fast.\n\n\n[1] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.\" Advances in Neural Information Processing Systems 34 (2021): 25294-25307.\n", "limitations": "Limitations are only partially addressed. The non standard finite sum assumption is properly discussed in the theoretical analysis section but could be anticipated in the abstract. The discrepancy between the theoretical and practical updates of SABA is mentioned briefly and not properly addressed (See Question section).\n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The presented framework is clean and allows to analyze fully single-loop algorithms. Previous analysis except for [1] usually did not consider updating the linear system variable online and with one descent step. Furthermore [1] directly consider variance reduction while here an analysis of a simpler algorithm (SOBA) is also provided.\n2. This is the first work exploiting the finite sum assumptions for this kind of bilevel problems and reaching the same rates as in single-level optimization.\n3. Experimental comparison is well done.  SABA is promising also in terms of practical performance. \n4. Very well written.\n\nWeaknesses:\n1. Some possible discrepancy between the proposed algorithm and how it is actually implemented: the average for the variance reduction is a rolling average in practice, and this is not covered by the theory. \n2. Rate for SOBA is not optimal and it is not clear why.\n3. Experiments are quite small in scale and can be slightly improved. No experiment under the PL-condition. No plots showing how the performance varies w.r.t. the number of single-sample gradients and hessian-vector products. \n\nSome of the points are expanded in the Questions section.\n\n[1] Li, Junyi, Bin Gu, and Heng Huang. \"A fully single loop algorithm for bilevel optimization without hessian inverse.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 7. 2022.\n\n**Post authors’ response.**\n\nThe authors have thoroughly addressed my concerns in their revision and response. In particular, concerning weakness 2, they now achieve optimal rates for SOBA under additional smoothness assumptions which are still realistic. Therefore I accordingly increased the score from 7 to 8.\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": "1lz_0UFhUw4", "reviewer": "Reviewer_wFQ9", "summary": "This paper proposes a simple framework for solving bilevel optimization. The framework involves only 3 unbiased estimation in each iteration. The authors provide theoretical convergence guarantees for both SGD version and variance reduction version based on SAGA. Experimental results are provided showing their superior performance.", "questions": "  ", "limitations": "  ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed framework is very simple and clear. The idea of simplifying solving bilevel optimization into three unbiased estimation makes the theory more intuitive and straightforward.\n2. Many theoretical guarantees are provided, which makes the statements well-supported. To my best knowledge, the convergence analysis shows optimal convergence rate under corresponding settings.\n\nWeaknesses:\n1. From what I can see, the key idea of this framework is the way of estimating the Hessian-vector product, i.e. 'v' (equation (5) in the text). However, as the authors mention in line 92, this idea is not novel.\n2. In the discussion of convergence, the comparison is made in terms of iteration complexity. But the experiments part only shows comparison in terms of running time.\n2. The experiments are only performed on one dataset for each application.\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": {}}]

Author rebuttal:

Decision: Accept