Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling
Authors: Junyi Li
Heng Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: sampling
bilevel optimization
Primary area: optimization

Abstract: Bilevel Optimization has experienced significant advancements recently with the introduction of new efficient algorithms. Mirroring the success in single-level optimization, stochastic gradient-based algorithms are widely used in bilevel optimization. However, a common limitation in these algorithms is the presumption of independent sampling, which can lead to increased computational costs due to the unique hyper-gradient structure in bilevel problems. To address this challenge, we study the example-selection strategy for bilevel optimization in this work. More specifically, we introduce a without-replacement sampling based algorithm which achieves a faster convergence rate compared to its counterparts that rely on independent sampling. Beyond the standard bilevel optimization formulation, we extend our discussion to conditional bilevel optimization and also two special cases: minimax and compositional optimization. Finally, we validate our algorithms over both synthetic and real-world applications. Numerical results clearly showcase the superiority of our algorithms.

Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling
Junyi Li and Heng Huang
Department of Computer Science, Institute of Health Computing
University of Maryland College Park College Park, MD, 20742
junyili iiy i, ai ai@gmail. com, henghuargghh@gmai.cccmm com
Abstract
Bilevel Optimization has experienced significant advancements recently with the introduction of new efficient algorithms. Mirroring the success in single-level optimization, stochastic gradient-bai baaseett-baedddtde algorithms are widely used in bilevel opti- mization. However, common limitation in these algorithms is the presumption of independent sampling, which can lead to increased computational costs due to the complicated hyper-gradient formulation of bilevel problems. To address this challenge, we study the example-selection strategy for bilevel optimization this work. More specifically, we introduce a without-replacement sampling based algorithm which achieves a faster convergence rate compared its counterparts that rely on independent sampling. Beyond the standard bilevel optimization for- mulation, we extend our discussion to conditional bilevel optimization and also two special cases: minimax and compositional optimization. Finally, we validate our algorithms over both synthetic and real-world applications. Numerical results clearly showcase the superiority of our algorithms.
Introduction
Bilevel optimization 51 47 has received a lot of interest recently due to its wide-ranging applicability in machine learning tasks, including aaper--rrrmeter optimization [39], meta-learning (57) and personalized federated learning [46]. A bilevel optimization problem is type of nested two-level problems as follows:
min h(x) (z, Me)) s.t. Vo arg min g(,, y),
vERd
which includes an outer problem f(x: y) and a inner problem g(r, y). The outer problem f(x y) relies the solution yz of the inner problem g y). Eq. ①1 can be solved through gradient descent: Tt-1 = Ft. - 1/ (a with be the stepsize and Vh(Iz, be gradient at the state xy. Specially, the
gradient Vh(x) [7 is function of the inner problem minimizer Va. first order derivatives Vaf(a, v). Vz y). V Vyg(i, (x, y) and second order derivatives Vayg(E, y). V Vzag(z, y). In particular, yz can be solved though gradient descent: yt++1 = y/ 7 V V2g yt) with y be the stepsize and V V1 yr) be gradient at the iterate (I), In the standard setup. the outer and inner problems are defined over two datasets D. {Er, E [m]] and D, ( [n]]. respectively:
1 Σ f(x,v: v:))), g(r, v)
1 Σ gl (z))
f(x,v) =
Naturally, we sample from the datasets estimate the first and second-order derivatives in the hyper-gradient formulation. And to guarantee convergence, previous approaches require the examples
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparisons of the Bilevel Opt. & Conditional Bilevel Opt. algorithms for finding an c-stationary point. We include comparison with stochastic gradient descent type of methods and more comprehensive comparison including other acceleration methods can be found in Table 2 of Appendix. An e-stationary point is defined as [Vh(2]] S 6. Go(S,e) and Gclg, e) denote the number of gradient evaluations w.E.L [(x,,) y) and g(x; y); (V e) denotes the number of Jacobian- vector products: HV (g. 6) is the number of Hessian-vector products. m and n are the number of data examples for the outer and inner problems, in particular, n is the maximum number of inner problems for conditional bilevel optimization. Our methods have a dependence over example numbers (mox (m, ), q is a value decided by without-replacement sampling strategy and can have value in 10, 1] (A herding-basee
permutation [33] can let 0).
Setting
Algorithm
Go(f.e)
G)(a.))
(9.
H)
BSA (77
O(e-t)
Ole
Ole O
TTSA 22
B.O.
StocRiO 25
SOBA 9
O
O
AIDATT 25
Ofonar (1,, nije (mmaz((m N6).
Ofmaar fon, n) Ollmar((m mlyfe
Ormarr(n (m, nie
O'maz (m, m)e (mmoz mifee"
WiOR-BO(Ours)
Ofmoaa(m niple"
DL-SGD
28
O +)
Ole O
Ole Ole
Ole O O (ms, vi) 9
Cond. B.O.
RT-MI MC
23
O
WIOR-CBO (Ours)
ni))"
A(mar(m,
Ofn(maz((m. m9j60
be mutually independent 25 even at the same state (z, v). For example, two different examples Si and (2 are sampled to estimate V2g(z, y) and Vyag(z,y), respectively. This leads to extra computational cost in practice. Indeed, two backward passes are required to evaluate V= y) and fz, y), while five backward passes are needed to evaluate Vgg(z, y). yz,g(x, y) and V y) for a given state of y). In contrast, one backward pass are needed to evaluate the former and two backward passes for the latter if not sampling independently for each property. This leads to notable computational cost difference for the current large- scale machine learning models (4]. Therefore, it is beneficial to explore other example-selection strategies beyond independent sampling. More specifically, we aim to answer the following question in this work: Can we solve the bilevel optimization problem without using independent sampling?
Although example-selection is under-explored for bilevel optimization, it has been well studied in the single level optimization literature
For single level problems: min f(x) =
EE= (x;; Ez), we iteratively perform the stochastic gradient step x++1 = 2t - -n Ex), where the sample gradient is used to estimate the full gradient and the example & is sampled according to some order. More specifically, the sampling schemes are roughly divided into two categories: with- replacement sampling and without-replacemmnt sampling. Traditional stochastic gradient descent typically employs with-replacement sampling ensure an unbiased estimation of the full gradient in each iteration. In contrast, the without-replaceen sampling has biased estimation at each iteration. Despite this, when averaging the gradients of consecutive examples, replace-t sampling can approximate the full gradient more efficiently (34). In fact, any vermutation-basee without- replacement sampling has that the gradient estimation error contracts at rate of O(K 3) [34] where K is the number of steps, while stochastic gradient descent only has a rate of O(K 1) Inspired by the properties of without--eplacement sampling demonstrated in the single-level optimization, we design the algorithm named WiOR- -O (and its variants) which performs without-replacemen sampling for bilevel optimization. Naturally, WiOR-BO does not require the independent sampling as in previous methods. In fact, our algorithm enjoys favorable convergence rate. As shown in Table WiOR-BO converges faster compared with their counterparts (e.g. StocBiO (25] using independent sampling- Actually, WiOR-BO gets comparable convergence rate with methods using more complicated variance reduction techniques (e.g. MRBO (52). In Table 2 we perform a more comprchensive comparison with other variance reduction techniques and in Section Clof Appendix, we further compare WiOR- BO with these methods.
The contributions of our work can be summarized as:
1. We propose WiOR-BO which performs without-samplingg to solve the bilevel optimization problem and converges to an e stationary point with a rate of O(E 33. This rate improves over the O(e- rate of its counterparts (e.g- stocBiO 25 using independent sampling.
2. We propose WiOR-CBO for the conditional bilevel optimization problems and show that our algorithm converges to an e stationary point with a rate of O1e- This rate improves
over the 0G) rate of its counterparts (e.g. DL-SGD 233 using independent-sampling
2

---

3. We customize our algorithms to the special cases of minimax and compositional optimization problems and demonstrate similar favorable convergence rates.
Notations. V (V.) denotes full gradient (partial gradient, over variable x), higher order derivatives follow similar rules. [n] represents sequence of integers from to n. O(-) is the big notation, and we hide logarithmic terms.
2
Related Works
Bilevel Optimization has its roots tracing back to the 1960s, beginning with the regularization
method proposed by [51), and then followed by many research works [14] 47 43 555). In the field of machine learning, similar implicit differentiation techniques were used to solve Plyper-paramett Optimization [28 6 [2]. Exact solutions for Bilevel Optimization solve the inner problem for each outer variable but are inefficient. More efficient algorithms solve the inner problem with a fixed number of steps. and use the "back-propagation through time' technique
compute the hyper- 26
gradient 1 35
30 are introduced to perform the outer and inner updates alternatively. Besides, other aspects of the bilevel optimization are also investigated: [23] studied type of conditional bilevel optimization where the inner problem depends on the example of the outer problem; [53] studied the Hessian-free bilevel optimization and proposed an algorithm with optimal convergence rate; [32) proposed an efficient single loop algorithm for the general non-convex bilevel optimization; 54 studies the bilevel optimization in the federated learning setting.
16
40 451. Recently, single loop algorithms [17
22
25
Sample-selection in stochastic optimization has been extensively studied for the case of single level optimization problems 12. 3 19 38). Beyond the with-replacement sampling adopted by SGD,
various rithout-replacement strategies were also studied in the literature. The random-reshufflin strategy shuffles the data samples at the start of each training epoch, and its property was first studied in [42 via the non-ummmutative arithmetic- geoomerre mean conjecture and followed by [20] 19. 36 studied the shuffling- strategy, where the data samples are only shuffled at the start of the training once; [ investigated data echoing where one data sample is repeatedly used. Quasi-Monte
Carlo sampling is also applied in stochastic gradient descent [ 34 Recently, [34 33 proposed to use average gradient error study the convergence of various example order strategies and then proposed a herding-basee sampling strategy [50) to proactively minimize the average gradient error.
3 Without-Repacement Sampling in Bilevel Optimization
In this work, we focus on the following finite-sum bilevel optimization problem:
min h(x) = flz,
1 Σ
faz ((x,zziEd) E.), s.t. y2 arg min g(z, v) = - (2)
arggmin
yERd
where both the outer and the inner problems are defined over a finite dataset, and we denote them as D. = {Ei, E [m]} and D, = [Cj.j [n]}] respectively. Under mild assumptions, the hyper- gradient of hx())) is:
Vh(c) = v, yx) V Vayg( yn Mn, U2 = V Vyzg(a, yz) - (x, Mn)
Our objective is to minimize h(x) by exploiting Eq. 33 with examples from D., and D) each step. More specifically, for a given example order x denoting the following example-selectinn sequence {47 E ) and {cT Dr} for E [T], where T' denotes the length of the sequence and can be arbitrarily large. We then perform the following update steps iteratively for E [T]:
Vt+1 1 = Yt 7/ V Vyg(r,, Dei )
(4a)
Vyl(E,, Mei E7) It+1 = It - 1 (V. (x,, ye 57 Vzgg(Er, Mri C." )
We+1
Pr g yei G7 )u.
(4b)
(4c)
where Eq. 4 adopts the single-loop
30 update. More specifically. Eq. 4a performs gradient
descent to estimate the minimizer yx: Eq. 4b) performs gradient descent to estimate u, defined in Eq. (3) and Eq. 44) perform the gradient descent step given the estimation of yı and ut.
3

---

Algorithm 1 Without-Repllccmmen Bilevel Optimization (WiOR-BO)
1: Input: Initial states z². uf and uy; learning rates hheee [1], E [R]] == lcm(na denotes the least common multiple of m and n.
2: for epochs r = 1 to R do
3: Randomly sample 1/m permutations of outer dataset and concatenate them to have {57, i
[4]]. sample // permutations of inner dataset and concatenate them to have {CT i E [4]]
4: Set yo = y/ -- un = P.(un and zó = x²
5: for 0 to I do
6:
v4 yf- - Vo vi: (F); uff1 = un - P. (o vo((2),01:55)
7: 4+ x - n/ (V vi - V (t:
8: end for
9:
end for
Note that each step I, we pair of examples (57, (7) estimate the involved properties and require only three backward passes, i.e. ( yr: 57) ), Vg(z,, ye; (e) and V(V yt, 52) (.") In contrast, if we independently sample examples for each property, seven backward passes needed. For large-scale machine learning models where pack-propagation is expensive, our method can lead significant computation saving practice.
Equation 44) is independent of the specific order of samples. It can accommodate both with- replacement and without- replloemet sampling strategies. In particular, consider two most uidely-used without--relaaemeen sampling methods: random-reshuffting and shuffle-once. For random-resten rostum-rsshufiing, we set T = R x lem n), where (em(m,n1 n) denotes the least common mul- tiple of m and n and R is a constant. More specifically, we generate R x lcm(m,,)) n)/m random permutations of examples in D,, then concatenate them to get {4T E DD,,, and we follow similar procedure to generate {GE- E ). In algorithm 1
we show our WiOR-BO algorithm for solving Eq. 2 with random-reshufllig sampling. Note that in Line 4 of Algorithm I P.(-) is the projection operation to an t-size ball and we perform projection to make be bounded during updates. Shuffle- once another widely used without-replacemmet sampling strategy, where single permutation is generated and reused for both Du and D,, and we can modify Line 3 of Algorithm| to incorporate shuffle-once. Finally, compared independent sampling-bass based algorithm such as stocBiO [25), we require extra space to generate and store the orders of examples, but this cost is negligible compared memory and computational cost of training large scale models.
3.1 Conditional Bilevel Optimization
In Eq. (2). assume the outer dataset D., and the inner dataset DD independent with each other. However, it is also common in practice that the inner problem not only relies on the outer variable x, but also the current outer example. This type of problems is known as conditional (contextual) bilevel optimization problems (23) in the literature and we consider the finite setting as follows:
m
min Mxx) = [(x, #ERP
(a, (5)) (.),ss...... (())) arg min g (5)) (x,
Σ
gla, us Seca))
veRd
Tig. j=1
(5)
Note that in Eq. (5) the outer problem is defined on finite dataset D, (Si, E [m]]] and for each example & E D',. we have inner problem g(E.) y) defined on dataset Dr.e= = (Seudi j [m
The hyper-gradient of Eq. (5 is:
m
Vh(x)=
Vzf(z.vf :2: V V (5:) (I, u )uf)) us ( (z,
(x.8x))-( -1 of(f:;; yer Ei),
m
(6)
The key difference of Eq. 6 with Eq. is that v and uf: are defined for each example & E D,,- To minimize h((r)) Eq. (5) we assume a sample order æ denoting the following example selection
sequence as 1E5 E Du, t []]. where I" denotes the example sequence length and can be arbitrarily

---

Algorithm 2 Without-RRepacennen Conditional Bilevel Optimization (WiOR-CBO)
1: Input: Initial state z², learning rates {1% J. E [mm], [R]]
2: for epochs r = 1 to R do
3: Randomly sample a permutation of outer dataset to have {5, E [m]] and set 26 = Zim or
2o if
4: for = 0 to m - do
5: Initial states y and u², learning rates (nj,P])1 E [mx], E (S).
6:
for 8 to 5 do
7:
Sample permutation of inner dataset to have (Sg.g.u [n:]] set vo vn,1 and
" = (P.(, or 1/ū = yo and ug = un if
8:
for j = 0 to - do
9:
i = V2 75 V sE,r;
10:
" +1 = " ( uf: E. Vyf(ot.0;
11:
end for
12:
end for
13:
2 = 2 - m (V f V. (7) - Vzugei (o) )
14:
end for
15:
end for
large. We then perform the following update steps iteratively:
T(+1 2i 1/e (Vo (1re Dri [7) V Vaygei (1r, ())ue)
where dt and ùn are estimations of yer. uzz We get them by performing the following rules Ti steps over the sample order (SE E Di,g7 [Ti]]]:
Er
U0++1 Vr, The V Vug(ar, iiii G2z (2 Un
Pa (V Vggg(Te Bie S J. - - Vgf(Iee Vui E7
where both the outer variable state z; and sample द are fixed. We then set Dr = yr, and ûn un Eq. (7). Note that Eq. 7 and Eq. (8) perform double-loop update rule [23]. Since the inner problem relies the example of the outer problem, and sample & instead of reusing them as in the single loop update of Eq. 44).
compute y and usi for each new state
Note that an important feature of our algorithm is that we select samples based on example order each step instead sampling independently. Similar to the unconditional bilevel optimization, various example orders can be incorporated. For random-reshuffling, we set T Rm with R be a constant. Then we generate random permutations of examples in D,, and concatenate them to get the example order {57 E Du, t E [.]]. Similarly, we concatenate S random permutations of the inner dataset Di.s, to get {<TT.,, E Di.ez 4 E [Ti}}} with sequence length Ti x rig, We summarize this in Algorithm 2 and denote it as WiOR-CBO. We slightly abuse the notation to replace ng; with n, in the inner loop update for better clarity.
3.2 MiniMax and Compositional Optimization Problems
Our discussion of without-replacemmnt sampling for bilevel optimization can be customized for two important nested optimization problems: compositional optimization and minimax optimization problems, as they can be viewed as a special type of bilevel optimization problem. Suppose we let the outer problem only rely on y, set the inner problem as g(x, y) 2 lly r(=)]l2. Consider the finite case of fvv and rzz), we have the following compositional optimization problem:
min M(x) = ZER
Σ (((()):))))))))))))))))))))()))) = 1=1
r(:; ())
Then we can derive the hyper-gradient as: Vh(x) (or))=Vr((<)e)) V.r(x)u,, where u. we have Vyg(E, y) compositional optimization problem using without-replacemmnt sampling AAloriihhm Appendix). Similar to the SCGD algorithm 49), we track the exponential moving average of the inner state
(r meanwhile, to get an algorithm for
r(x). Then we can instantiate Algorithm
5

---

besides we also track the exponential moving average of inner gradient (the update rule of u in Algorithm
Next, similar to the unconditional case, the conditional compositional optimization problem can be specialized from the conditional bilevel optimization problem Eq. (5) to have:
112
min x ERP
h(x)
(a; Ce
(10)
m
and we can instantiate Algorithm 2 in the special case of Eq. TT) get Algorithm@ the Appendix).
The minimax optimization can also be viewed as a special type of bilevel optimization. More specifically, if we have g(x, y) = - f(z, 4) in Eq. (2. then we get the following minimax problem:
min h(x) = xERP
max f(z, Ex)
(1I)
BERd
In the special case of Eq. TTI. the hyper-gradient Vh(x) in Eq. 3 degenerates to Vh(z) = v., Uz) due to the fact that vzf Un) -V Vog(E, Vr) 0 by the optimality condition. Meanwhile, we have Vyg(2, y) = - (z, y). As a result, we can simplify Algorithm to get alternative update algorithm for minimax optimization using without-replacement sampling (Algorithm{4)) i in the Appendix). Note that due to the linearity of minimax problem w.E.f examples, the conditional case for minimax optimization degenerates to the unconditional case. [11 also considers the withoutt-eplacemeet sampling for the minimax problem, however, they focus on the soreee--ooooe----oonyy-oo--
and two-sided Polyak-Lojasiewwrs settings, in contrast, our WiOR MiniMax can be applied to vonconvex-strongly -oocavee concave setting.
Theoretical Analysis
In this section, we provide theoretical analysis of our algorithms. We first state some assumptions: Assumption 4.1. Function far y: 5) E Da, is possibly non-convex, L-smooth and has Cj- bounded gradient w.r.f. the variable y-
Assumption 4.2. Function g(x, y: S).5 DD, is u-strongly convex w.r. y for any given v, and L-smooth. Furthermore, V Vzyg(I, yi () and Vy yi () are Lipschitz continuous with constants Lay and Ly" respectively.
Assumption 4.3, For all examples & E Du and states (z, y) E RDd there exists an upper bound such that the sample gradient errors satisfy f ys (.) f y)1l A.
Assumption 4.4. For all examples i E Dj and states (a. y) E RR+d there exists an upper bound such that the sample gradient errors satisfy [[Vg(z, y: ()) Vg(a, S A and V2 GG V V29(I, y)1l < A.
As stated in The assumption and 4.2 we consider the wen-coovex--trongy--oo-- optimization problems, this class of problems widely studied in bilevel optimization litera- ture 117 25 AAssumttio 4.3 and 4.4 guarantee that the example gradients are good estimation of full gradient and is widely used in the analysis of single-level finite-sum optimization prob- lems (36). Note that as the syper-gradiemt (Eq. 3 involves second order derivatives, Assumption 4.4 also requires that the second order example gradients have bounded bias.
bilevel
We next make the following assumptions about the example selection sequence. We assume (&7 Du, t E [T]) and { E D E [T]} satisfy:
Assumption 4.5. Given sequences of samples: {EF DDu [T]} and (ST Di, E [T]), assume there exists some constants a, C such that for any step and any interval k > 0, we have:
+ T
(((2,)))''' k-
and similar bounds hold for Vg and 42g (See Appendix B.1 for the full version of this assumption.)

---

Assumption 4.5 measures how well the sample gradients upproximate the full gradient over an interval on average. Similar assumptions are used study the sample order in single level optimization 1 and C = A based on order (e.g. random-reshuffing and shuffle-once), we can show the assumption holds with = 2 and C = max max(m, n)) x A. Note that the C' depends on the number of samples m (n), this dependence can be reduced to (max(m, n))u.s for sufficiently small learning rates [34 (37. More recently, [33 proposed herding- -based algorithm which explicitly optimizes the gradient error in Assumption 4.5 and shows that we can reach a = 2 and = (AA).
problems 33 If samples are selected independently at each step, we get
Assumption
3 and 4.4 For any permutation-bast
Bilevel Optimization. We are ready to show the convergence of Algorithm | Firstly, we denote the following potential function G, == 9 = hhxx))))))))))))))))) + Qy 3/ Yz,, 1|2 + dullu, Uzz 112, where By and du are constants that relates to the smoothness parameters of h(z)) Then we have:
Theorem 4.6. Suppose Assumptions 4. 14.4 are satisfied, and Assumption 4.5 5 satisfied with some and C for the example order we use Algorithm We choose learning rates th = 17, " c1T). Pt = C2T) and denote T = R x I be the total number of steps. Then for any pair of values (E, k) which has T E k and 1 S 1. we have:
kLa"
1 R-1
Σ
2A Vh(oke))
+ =2
E
kEn
where C1, C2. Lo, L. are constants related to the smoothness parameters of h(x), A the initial sub-optimality, R and I are defined in Algorithm
To reach stationary point, we choose 1 and for (E,k), we choose: E <Loa and k
422c2
1/a
which means we need to choose the number of epochs It = - 12 10447/0
Specially, we choose examples independently at each step, we have C = and a = 1, then we need T = O( (A) steps to reach an c-stationary point. This recovers the rate of stocBiO algorithm [25] and SOBA [9. Next, if we use some permutation- based witbout--eplacemmet sampling strategy witch has C' = (max(m, 78 8 A (q E [0, 1)) and = 2, then we need T ((mmxx(m, n)) $)) In particular, by adopting a herding- based permutation as in [33, we get q = O, and our WiOR-BO strictly outperforms the independent sampling- bassed stocBiO and SOBA algorithms.
Conditional Bilevel Optimization. Next, we study the convergence rate of Algorithm 2 Assumptions 4.3 and 4.4, we need the bias of sample hyper-gradient be bounded too:
Besides
Assumption 4.7. For all examples & E D, and states E RP, there exists an upper bound A such that the sample gradient errors satisfy Vh( E,) Vh(x)] $ A.
We also augment Assumption 4.5 to include the case of (1x)) (Seem Appendix B. for more details.). Then we are ready to show the convergence rate, we use the potential function G. h((+)) and have:
Theorem 4.8. Suppose Assumptions 4.1 4.4 and 4.7 are satisfied, and Assumption 4.5 is satisfied with some a and C for the example order we use in Algoritimm 2 We choose learning rates т) = skL
Tt 7 256kLx' Pt - 512kLx and denote T R m be the total number of outer steps and Ti = 5x x max) be the maximum inner steps. Then for any pair of values (E, k) which has T E and Ti Et k, have:
KEn + C.
8A
kpp D. Cg(11 )
kuY 2
E Dy + (C')
E
where Cu. Cy. C. L are constants related to the smoothness parameters of h(x), An. A. Dy are the initial sub-optimality, R and S are defined in Algorithm
1/a
To reach stationary point, we choose: F
1287 and A
2(C' 2
and Fa
(llo((- Then the sample complexity of Algorithm is EE we omit the logarithmic term E.. Specially, if we choose examples independently at each step, then we have sample complexity O(e steps for an e-stationary point. This recovers the rate of DL-SGD algorithm (23]. Next, if we use some permutation-baset without-replacemeet sampling strategy,
where
7

---

then we have sample complexity ([mmx((m, 2 which can match the state-of-ar art algorithm RT-MLMC [23] if we choose an example order with 33
MiniMax and Compositional Optimization. As special cases of Bilevel Optimization, we can also show that Algorithm 3 Algorithm and Algorithm
( converge under similar rate. Please Corollary B B.21 221e and Corollary B.20 for more details.
Applications and Numerical Experiments
In this section, we verify the effectiveness of the proposed algorithm through synthetic invariant risk minimization task and two real world bilevel tasks: Hyper-Data Cleaning and reyper-reprseentation Learning. The code is written in Pytorch. Our experiments were conducted on servers equipped with 8 NVIDIA A5000 GPUs. Experiments are averaged over five independent runs, and the standard deviation is indicated by the shaded area the plots.
WAR-CB (O)
VION CBO 1501
5.1 Invariant Missmmiinmizzaiion
(SRL
Validation Loss
In this section, we consider synthetic invariant risk mini- mization task [21] More specifically, we perform logistic regression over a set of examples {(G, b,), E [M]} with be the input and
ca
the target. However, does have
access to e but a set of noisy observations {eg.i. E n;} for each e.. learn the coefficient x between and we optimize the following objective:
100
1200
1002
2400
Number of Hyper-tteration
m
min
log(1 + (xp(-bby!""))
ZERP
Figure 1: Comparison of different sam- pling strategies for the Invariant Risk- Minimization task.
1=1
ni
S.t. 2/
arg min
yERd
This is a conditional bilevel optimization problem and we can solve it using our WiOR-CBO We generate synthetic data to test the effects of different sample order (sample generation process is described in Appendix AD.. More specifically, we compare independent-sampling (WiR-CBO), shuffle- once (WiOR-CBi (SO)) and mndom-reshufffin (WiOR-CBO (RR)). As shown in Figure the two without-replacemmnt sampling methods outperforms the independent sampling one.
5.2 Hlyper-Date Cleaning
In the Hyper-Data Cleaning task, given noisy training dataset whose labels are corrupted by noise, meanwhile, we have a validation set whose labels are not corrupted. Our target is then using the clean validation samples to identify corrupted samples in the training set. More specifically, learn optimal weights for training samples such that a model learned over the weighted training set performs well the validation set. We can formulate this task bilevel optimization problem (Eq. (2). mathematical formulation of the task is included in Appendix [A]
Dataset and Baselines. We construct datasets based MNIST 22 For the training set, we randomly sample 40000 images from the original training dataset and then randomly perturb a fraction of labels of samples. For the validation set, we randomly select 5000 clean images from the original training dataset. our experiments, we test our WiOR-BO algorithm (Algorithm [ with the shuffle-once (WiOR-BOS -O--OO and random-reshufling (WiOR-BO-RE, BO-RR) sampling: additionally, also consider the following non-adaptive bilevel algorithms as baselines: reverse [16), stocBiO (25), BSA 177, AID-CG [18), MRBO [52]. VRBO 52 and WiR-BO (the variant of our WiOR-BO using independent sampling, which is similar to the single loop algorithms such as SOBA M. AmIGO and FLSA (30). We perform grid search for dyper-paramend
and report the best results.
We summarize the results in Figure the figure, we compare the validation loss and Fl score w.r. both Hyper-iterations and running time. As shown in the figure, the two variants of our algorithm WiOR BO-SO and WiOR-BO-RR get similar performance and they both outperform other baselines. In particular, note that WiR-BO differs with WiOR-BO-SO (RR) only over the example order, but the

---

Figure 2: Comparison of different algorithms for the Hyper-data Cleaning task. The top two plots show validation error/F1 score Number of Hyper-lterateen Iterations and the bottom two plots show validation error/F1 score vs Running Time. The fraction of the noisy samples is 0.6.
Parniy
Tamiigg
Juning
Suring
Kurnin Time
Junnig
Figure 3: Comparison of different algorithms for the Hyper-Repressenttion Task over the Omniglot Dataset. From Left to Right: 5-way-1-shot, 5-way-5-shot
20-way-5-shot
later converges much faster in terms of running time, this is partially due to less umber of backward passes needed by without-replacemmnt sampling per iteration.
5.3 Hyper-Representatee Learning
In this section, we consider Hypee-represeentation learning task. In this task, we learn hyper- representation of the data such that linear classifier can be learned quickly with small number of samples. We consider the Omniglot (27) and MinilmageNet [41] data sets. This task can be viewed as conditional bilevel optimization problem (Eq. (2) and mathematical formulation of the task is included in Appendix A
Dataset and Baselines. The details of the datasets are included in Appendix A and we consider N-way-K-shin -hsot classification task following 48 In our experiments, we test our WiOR-CBO (Algorithm 2). using the shuffle-once (WiOR-BO-SO) and random-reshufflng (WiOR-BO-PH sampling. Besides, we compare with the following baselines: DL-SGD (23) and RT-MLMC (23]. Note that our WiOR-CBO can also use independent sampling, and it has similar performance as DL-SGD, We perform grid search of hyyer-parameteer for each method and report the best results.
We summarize the experimental results for the Omniglot dataset in Figure and we defer the results for MinilmageNet to the Appendix A As shown in the figure, our WiOR-CBO SO/RR outperforms DL-SGD and is comparable to the tate-of-the-ae art algorithm RT-MLMC.
6 Conclusion
In this work, we investigated example-selection of bilevel optimization. Beyond the classical independent sampling, we assumed an example-order based on without-replacement sampling. such as random-reshuffli
and shuffle-once. We proposed the WiOR-BO algorithm for bilevel optimization and show the algorithm converges to e-stationary point with rate O After that, we also discussed the conditional bilevel optimization problems and introduced an algorithm with convergence rate of O(e-1). As special cases of bilevel optimization, studied the minimax and

---

compositional optimization problems. Finally, we validated the efficacy of our algorithms through one synthetic and two real-world tasks; the numerical results show the superiority of our algorithms.
Acknowledgments
This work partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBI 2405416,
CCF 2348306, CNS 2347617.
References
[1] M. Arbel and J. Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:2111.14580 2021.
[2] L.. Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition, pages 421 Springer, 2012.
[3] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):22-311, 2018.
[4] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray,
B. Chess, Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners, 2020.
[5] A. Buchholz, F. Wenzel, and S. Mandt. Quasi-monte carlo variational inference. In International Conference on Machine Learning, pages 668 677. PMLR, 2018.
[6] D. Chen and M. T. Hagan. Optimal use of regularization and cross-validation in neural network modeling. In IJCNN 999. International Joint Conference Neural Networks. Proceedings (Cat. No. 99CH36339), volume 2, pages 2275-1280. IEEE, 1999.
[7] H. Cho and C. Yun. Sgda with shuffling: faster convergence for nonconvex-p {VL} minimax optimization. arXiv preprint arXiv:2210.059993 2022.
[8] D. Choi, A. Passos, C. J. Shallue, and G. E. Dahl. Faster neural network training with data echoing. arXiv preprint
2019.
[9] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprini arXiv:2201. 2340, 2022.
[10] M. Dagréou, T. Moreau, S. Vaiter, and P. Ablin. A lower bound and near-optimal algorithm for bilevel empirical risk minimization. In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 82-90. PMLR, 02-04 May 2024.
[11] A. Das, B. Schölkopf, and M. Muchlebach. Sampling without replacement leads faster rates in finite-sum minimax optimization, 2022.
[12] C. B. Do, C.-S. Foo, and A. Y. Ng. Efficient multiple hyperparameter learning for log- linear models. In NIPS, volume 2007, pages 377-384. Citeseer, 2007.
[13] J. Domke. Generic methods for optimization based modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[14] M. C. Ferris and O. L. Mangasarian. Finite perturbation of convex programs. Applied Mathe- matics and Optimization, 23 23))22633373, 1991.
[15] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1 1126-1135. JMLR. org, 2017.
10

---

[16] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient- gradient-based based hyperparameter optimization. In Proceedings of the 34th International Conference on Machine Learning- Vooumee 70, pages 1165-1173. JMLR. org, 2017.
[17] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint 1:Xiv:880200224: 2018.
[18] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748-3758. PMLR, 2020.
[19] M. Gürbüüzaalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuflling beats stochastic gradient descent. Mathematical Programming, 186:49-84, 2021.
[20] J. Haochen and S. Sra. Random shuffling beats SGD after finite epochs. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2624-2633, PMLR, 09-15 Jun 2019.
[21] L.. He and S. P. Kasiviswanathan. Debiasing conditional stochastic optimization. arXiv preprint ar04v:2304. /0613, 2023.
[22] M. Hong, H.-T. Wai. Z. Wang. and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05/700 2020.
[23] Y. Hu, J. Wang, Y. Xie, A. Krause, and D. Kuhn. Contextual stochastic bilevel optimization, 2023.
[24] Huang, J. Li, S. Gao, and H. Huang. Enhanced bilevel optimization via bregman distance. Advances in Neural Information Processing Systems, 35:28928-28993 2022.
[25] K. Ji, J. Yang, and Y. Liang. Provably faster algorithms for bilevel optimization and applications to meta-learning. arXiv preprint arXiv:2010.07962, 2020.
[26] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via
arXiv preprint arXiv:2112.07:367, 2021.
[27] B. Lake, R. Salakhutdinov, J. Gross, and J. Tenenbaum. One shot learning of simple visual concepts. In Proceedings of the annual meeting of the cognitive science society, volume 33, 2011.
[28] J. Larsen, L. K. Hansen, C. Svarer, and M. Ohlsson. Design and regularization of neural networks: the optimal use of a validation set. In Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, pages 62-71. IEEE, 1996.
[29] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11)::278-2222 1998.
[30] J. Li, B. Gu, and H. Huang. fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7426-7434, 2022.
[31] J. Li, F. Huang, and H. Huang. Communication-effiitn federated bilevel optimization with global and local lower level problems. Advances in Neural Information Processing Systems, 36, 2024.
[32] R. Liu, Z. Liu, W. Yao, S. Zeng, and J. Zhang. Moreau envelope for nonconvex bi-level optimization: A single-loop and hessian-free solution strategy, 2024.
[33] Y. Lu, W. Guo, and C. M. De Sa. Grab: Finding provably better data permutations than random reshuffling. Advances in Neural Information Processing Systems, 35:8969-8981, 2022.
[34] Y. Lu, S. Meng, and C. De Sa. A general analysis of example-selection for stochastic gradient descent. In International Conference Learning Representations (ICLR), volume 10, 2022.
11

---

[35] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient braseent-based hyperparameier optimization through reversible learning. In International Conference on Machine Learning, pages 2113- 2122, 2015.
[36] K. Mishchenko, A. Khaled, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 09-17399-13320) 2020.
[37] A. Mohtashami, S. Stich, and M. Jaggi. Characterizing & finding good data orderings for fast convergence of sequential gradient methods, 2022.
[38] L. M. Nguyen, Q Tran-Dinh, D. T. Phan, P. H. Nguyen, and M. Van Dijk. A unified convergence analysis for shuffling -tppe gradient methods. The Journal of Machine Learning Research, 22(1):9397-994) 9440, 2021.
[39] T. Okuno, A. Takeda, and A. Kawana. Hyperparameter learning via bilevel nonsmooth opti- mization. arXiv preprint arXiv:/806.0151 1806.01520, 2018
[40] Pedregosa, Hyperparameter optimization with approximate gradient. arXiv preprint 1602.0355 2016.
[41] S. Ravi and H. Larochelle. Optimization model for few-shot learning. In International conference on learning representations, 2017.
[42] B. Recht and C. Re. Toward noncommutative arithmetic-geonee geommerrc mean inequality: Conjec- tures, case-studies, and consequences. In S. Mannor, N. Srebro, and R. C. Williamson, editors, Proceedings of the 25th Annual Conference Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 1.1-11.24, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
[43] S. Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-66) 06040066622200 2017.
[44] I. Safran and O. Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[45] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back-propagation for bilevel optimization. arXiv preprint
10667, 2018
[46] A. Shamsian, A. Navon, F. Fetaya, and G. Chechik. Personalized federated learning using hypernetworks. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9489-9502. PMLR, 18-24 Jul 2021.
[47] M. Solodov. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2):227, 2007.
[48] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pages 3630-3638, 2016.
[49] M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):419-44, May 2016.
[50] M. Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual Interna- tional Conference on Machine Learning, pages 1 1121-1128, 2009.
[51] R. A. Willoughby. Solutions of ill-posed problems (an tikhonov and vy arsenin). SIAM Review, 21(2):266, 1979.
[52] J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. arXiv preprint ar0iv:2/06.0 246.49,, 2021.
[53] Y. Yang, P. Xiao, and K. Achieving -1.55) complexity in hessian/jacobian-fre stochastic bilevel optimization, 2023,
12

---

[54] Y. Yang, P. Xiao, and K. Ji. Simfbo: Towards simple, flexible and Conmunication-efficiii efficient federated bilevel learning. Advances Neural Information Processing Systems, 36, 2024.
[55] M. Ye, B. Liu, S. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach, 2022.
[56] P. Yu, J. Li, and H. Huang. Dropout enhanced bilevel training. In The Twelfth International Conference on Learning Representations, 2023. 20233
[57] I. Zintgraf, K. Shiarli, Kurin, K. Hofmann, and S. Whiteson. Fast context adaptation via meta-learning. In International Conference on Machine Learning, pages 7693-7702, PMLR, 2019.
13

---

A
More Details for Numerical Experiments
In this section, we introduce more details of the experiments.
A.1 Invariant Kisk-Minimization
The data generation process is as follows: we first randomly sample ground truth xx, then we randomly generate m = 1000 input variables c, and calculate the ground truth label b = cr, then for each Cj we generate a set of also add L2 regularization term of strength 0.1 for the outer problem. During trainging, we use both the inner and outer learing rates of 0.001.
100 noisy observations by adding Guassian noise of scale 0.1. 1. We
A.2 Hyper-Data Cleaning
The formulation of the problem is as follows:
min h(x) = f(x, ZERP
O
eval
N(vat)
n=l
Nicr)
s.t. U2 = arg min g(z y) =
Σ In (y: (1h
yERd
(etr) In the above formulation, we have a pair of (noisy) training set {st Jnm1 and validation set (Erat) (ruu)) and we denote the model by O. Note that yæ is the model learned over the weighted training set. We fit model with fully connected layers for the MNIST dataset. We also use La regularization with coefficient 10-3 to satisfy the strong convexity condition. In the Experiments, we choose inner learning rate (7, p) 0.1 and outer learning rate 1000.
Jn=1 and Fn, n E [N(tr)] are weights for training samples, y is the parameter of model,
Ncdi Tea
Time
Buaning Time
Surnng Time
Figure 4: Comparison of different algorithms for the Hyper-Reprrseentaion Task over the Minilma- geNet Dataset. From Left to Right: 5-way-1-shot, 5-way-5-shot, 20-way-1-shot, 20-way-5-shot,
A.3 Hyper-Representttion Learning
Neat
min h(x)) = f(I,yz) rEB
Ozz, vl (T));
Nval
n=1
1=1
N
s.t. v (T)) arg min (Ta) (I, = Ntr
1
Σ O(a,ve
vERd
In the above formulation, have N tasks and each task Tn is defined by pair of training [etr J= and validation set [ggal) Nyal Ji=l
e defines the model, is the parameter of the backbone
14

---

model and is the parameter of the linear classifier. In summary, the lower level problem is to learn the optimal linear classifier y given the backbone z, and the upper level problem is to learn the optimal backhone parameter 2.
The Omniglot dataset includes 1623 characters from 50 different alphabets and each character consists of 20 samples. We follow the experimental protocols of [48) to divide the alphabets to vrann/valiaaiion/eestt with 33/5/12, respectively. We perform N N-way-K-shhe specifically, for each task, we randomly sample N characters and for each character, we sample K samples for training and 15 samples for validation. We augment the characters by performing rotation operations (multipliers of 90 degrees). We use 4-layer convolutional neural network where each convolutional layer has 64 filters of x [T]]. For the MinilmageNet, it has 64 training classes and 16 validation classes. Similar to Omniglot, we also perform the N-way-K- K-shot classification. We use a 4-layer convolutional neural network where each convolutional layer has 64 filters of 3x3 [[5] for experiments. For the experiments, we use inner learning rates 0.4 and outer learning rates 0.1 for Omniglot related experiments and inner learning rates 0.01 and outer learning rates 0.05 for MinimageNNet-rlateedd experiments. We perform 4 inner gradient descent steps and set Kmaz 6 for the RT-MLMC method. The experimental results for the MinilmageNet dataset is shown in Figure 4
classification, more
B Proof for Theorems
In this section, we provide proof for the convergence results in the main text. First, we restate all assumptions needed in our proof below:
Assumption B.1 (Assumption 4.1). The function f(z, y) is possibly non-convex and uniformly
L-smooth, iee. for any T1, Z2 E X, yı, y2 RRR,aay then we have:
any E E Du. Denote 21 (x1, v1), 22 = U2).
((2i8) < (z2; + (V)(zz, - x2) + - - -
or equivalently: [=);();;)) (22; < E||=1 =2|1- We also assume for any x E X' and any y E Id, and we denote (z. y), then we have 1[ s Cy.
Assumption B.2 (Assumption 4.2). Function 9 y) is uniformly j-strongly convex wen y for any given x and uniformly L-smooth, i.e. for any V1, 3/2 E Id and Ç E Dr, we have:
v):)) 2 v2,,,12() + (V Vugla, u2i (), y22 yn) b l1/2 2 11?
/
and we have:
L 2 || 2211?
((21i)) 2 g () +
+ (Vg(22) (), 22)
equivalently: || [)(;;;)) V OlI < D||=| =2|1- Furthermore, we have V Vayg(E, y) and Vygg(z, y) are Lipschitz continuous with constant Lay and b22 respectively, i.e. we have: |IV myg(< (21; {) V (2y <)ll < Lmnl|= =22l and {)>g(<); V () < ||= - 22ll-
Assumption B.3 (Assumption 4.3). For all examples & E D. and states (I, y) E RD+d there exists an outer bound A such that the sample gradient errors satisfy f E.) - v f(x,))] I A.
Assumption B.4 (Assumption 4.4). For all examples C E D; and states (x. y) E Rdd there exists an outer bound A such that the sample gradient errors satisfy [V y: (.) Vz 3) || < A and |[V'(æ, yi (.) V²g(a, y) S A.
Assumption B.5 (Assumption 4.7). For all examples & E D2 and states x E R?, there exists an upper bound A such that the sample gradient errors satisfy |/Vh(z: vh(z)]l A.
Assumption B.6. Given two sequences { E Du,t constants
[T]} and {लT
Dr,t t
E [T]]. we assume there exists some
a. C such that
for any step t and any k > V Vf(a,,
0, we have:
1l D (2
Bill
< k- | - Vg(Ie, Mri (7) - Vo(ar, vrll < k-
( B: - g |
< k C²
I i
+ vh(zn:))) - vh(zi)]12 $
(Only for the conditional bilevel optimization case).
15

---

Algorithm 3 Without-Replacennt
Compositional Optimization (WiOR-Comp)
1: Input: Initial states 27. yf and ulj; learning rates {1% PE 7 J, E [4], [R]. I = lem(m, n).
2: for epochs r = -1 to I2 do
3: Generate sample order sequence { and {(r) for é [4] as Line of Algorithm !
4: Set 3ó = y/ un = P.(u7 and zó = z =--
5: for 0 to 1 - do
6: Vi+1 (1 Do + trr,, (rr(s,,F)): u44 = (1 D.) + +VV
7: 2 x mi Vr(at )u;
8: end for
9:
end for
Algorithm 4 Without-Replacemneee MiniMax Opt. (WiOR-MiniMan)
Input: Initial states 2 y learning rates frt. m i [m], e [R].
2: for epochs r = 1 to R do
3: sample a permutation of outer dataset have {CT i E [m]];
4: Set yo Vnn and 25 2
5: for 0 to m do
6: V++ vf 7. V v [x (f
7: .+ x o V V. V M.
8: end for
9:
end for
B.1 Proof for Bilevel Optimization Problems
Suppose we define:
Voyg(z,)) Then we have Vh(x) = ( Vn). Furthermore, we have following proposition:
(<r = - x VV Vogg(( w0l V (x,
Proposition B.7. Suppose Assumptions 4. and 4.2 hold, the following statements hold:
a) is Lipschitz continuous in x with constant of g(x,y).
where k
L is the condition number
b) (+1;;)) - ( ya)ll < f.2(110] - -22 + I1 y2ll?), where î. (
c) h(x) is smooth in x with constant i.e. for any given 11, D2 E X, we have Vh(x22 Vh(=1)] < D||>2 zıll where L = O(K²).
This is a standard results in bilevel optimization and we omit the proof here.
The main technique we use to analysis the convergence of Algorithm [ is aggregated analysis, in other words, we perform analysis over a block of length instead of the more common per step analysis in stochastic bilevel optimization. Note that this technique is essential in analyzing without- rephbut-te sampling for single-level optimization problems, and we extend them to the bilevel setting. More specifically, suppose the total number of training steps T = R x 1, where R and are denoted in Algorithm []
then we consider a block training steps [t, t + k] for t E [T - k). Furthermore, we denote: 7. = Σttk-1 Tr: and D. = 1 Ettk-i n7V;; 7t Etth- 7r and wh 1 E4th-1 ToWi; = 1 Pr. and qr
de
1 ( PrYr, where
De
Vt Vzf yes Ec) V 2nng (Tr, Mii Mis::t))uuu G)u,, We V Vug(o,,6 Ge) and ge Vygg(Te,3 Mis G) V V Me; E.). In particular, we denote ra (u) as:
Tz (w) 2" Vegg(,,))))) VyJ(n, y
by assumption it L smooth and μ strongly convex. is straightforward see that u, arg min (u), where u, is defined in Eq. 33) Finally, in the proof, we consider the general
wegd
case of different orders for all involved example derivatives. In other words, we have {Er,), (6.2).
16

---

Algorithm 5 Without-Replacemeet Conditional Compositional Optimization (WiOR-CComp)
1: Input: Initial state z², learning rates {1% J. E [m]]r [R]]
2: for epochs r = 1 to R do
3: Randomly sample a permutation of outer dataset to have {5T é E [m]] and set 26 = Zim or
2o if
4: for = 0 to m do
5: Initial states y and u², learning rates
E [mx], 8 E (S).
6:
for 8 to 5 do
7:
Sample permutation of inner dataset have (Sg,g, [ns]], set vo yhol and
" = (u, or yd = Yo and u = uo if 1.
8:
for j = 0 to do
9:
i = (1 - 25)13 + ff SE,)):
10:
u = (1 -0j)u} + P3 V
11:
end for
12:
end for
13: sf+1 = xo - 1/ VrSi (x))
14:
end for
15:
end for
v). Vyag(a, y). V vxz y) respectively. The two orders used by Algorithm is a special case of the proof and practically appealing as they can reuse computation as we discussed the introduction.
1G (Sr2) and (Gr,) for vyJ(z. y). Vaf v)gg,a
I
Lemma B.8. For r > 1 1 O, the bias of E Vr (Mr- (1? | Pr (Vra, (wr) 4r )1
and EE 7r ( Sr.1) (x))ll are bounded by Eq. (15). Eq. (16 and Eq. (17
Proof. First for EE (u= - vh(xz))11 we have:
1r ( - 11
Σ 77 (urf(Ie Blae) V Vz Vo.Jur (22f(z7,31i5n) V Veyg(EF, Ue: (F: (+33)=)))1
2|
Σ 1/ a Mn.) (rra Σ
1r (V Vayg(Er Mer Mer)un Vayg(Er, Mri (r,)) 1|2
F=t
$ 2/
Σ
1r -oa
407 7/7 V Vanggeerr 12)
+ 41
Σ
Σ 1/ Vayg(ar, vs.) V Vayglet, U+i Gr.a)) I|²
112
T-1
$ 2|
Σ
1) (Vd((rr - (a. 4L m
Σ
Mr -
(((x,,-))]
7=t
n=t
4C²
Σ
(Vaaggle Vz.) - (.g
yf:
(12)
T=1
For the first and the third terms above, we have:
1F
Vafless V2.) - Vul Uri (+i))))
T=1
vel12 + 3T. (T.
2+112 + 3|l Σ 7F
(Vz((r..v) (6
(13)
17

---

and
Σ Th (o)g(zr.Bo.) - T=l
T-1
S 3l (m) (1yz,
3ell² + 3 ay Σ 71 - 2+ 2+12 311 Σ
1/ (Vay((Ft, V Vagg(Tr, yei Sr,3)) 1?
7mrt
(14)
Combine Eq 13 and (4) with Eq. 122 and denote L3 (L2 + 21: 0 to have:
7+ (u+ Vh(xx))11
< (T)) - 11F+617m
Σ
M+ 1|
+1' | - well3 18++817 8L. Σ 77 I|ue ur
Tmm
120
+ 61 Σ
7/ ( (Vaf(Ie.)))
Σ
7= 7 (Vayg(IEs (1) - V Me
Mes SF,s)
122
T=t
7=t
(15)
Next, for the term
|E Px( (Vr., (u+) - 4=) we have:
Σ pr (Tr, =²
(F. (ogg(Fe..e))a Vyf Var)) ||?
PF
2
Pr (Vy - (..
T-1
2
Σ
Pt
P=1
T-1
$ 2 Σ
Pr VI (r.
407 T-1
+ +4|
Σ
v -o
pr (V (V V Vgrg(E,, br:
(r:f((,v:G... 212
112
7=1
21
Σ
Pr (Vyf( - Vr: 4L p.
pr - -
F=1
4C2
Pr (V V (og(o,,
T=t
18

---

The first and the third terms can be bounded similarly as in Eq.
13 and Eq.
14
and denote
2 C7
1.2 (1.2
yx
then have:
1
Σ Pf Vrn (u+) - (7) q=) 1
T-1
& (11(00))111400 - well? + 6L207
pr 2a 2+12 + 4L' pt
Σ
Prllue - =rl?
T=t
T=1
120
+ 6/| Σ PT((V (Vo Me
Pr V (220(2))8))
Vo Mei 62)
7=1
1=1
(16)
Finally, for / (V (v (z 3:)) we have:
(Vog(er. ST.1) -
2
Σ Br. v Vog( Uc, 1r.
1=t
+
Σ Y+ St.1 (.)(,,,))))11
< 2LL
Σ
J-|1zr =ell2+ 2/1 Σ yr (Vg(ee, - (r.
(17)
n=t
7=t
This completes the proof.
Lemma B.9. For all t 2 0 and any constant >> 0, suppose 2T. the iterates generated satisfy:
+
(14+4) M(..)) [h(x;)11 10.11 +L,77elluee
vell + 3ビ3
Σ 1111= 2z
+ 4L2 カ-ルー1
4L 1/ - uell
Σ
7r 1|1 - 1r11
+ -11
Σ
(V v1) - Val
Tr
1/c
6C7
||
Σ nr (Vayg(Dr, vi) Veyg(Fe, Mei Sr, 112
Proof. By the smoothness of f. we have:
h(x++)) S (((x))) + (Vh(2,), T4th -x,) -
1itk - x
2
= -h(a))) n/ (Vh())), 01)) + T.
||
2
( h((x))
1
[x:))
)|
| Vh(azt) -1z112
17t
TL
||
2
2
( 7/
+ ntt Vh(xz)
h(m)))
|Vh(2))]
1211
|
(18)
2
2
4
19

---

where equality (a) uses (),6) 2 |||a|1 + ||6] ||a b|l3] (b) follows the assumption that
t 1/2L. Next, for the third term, by using Eq. [5]. we have:
++
1/ [Vh(zz) 2.11²
3L37 11y..
yell + 3
Σ
1/- 1 2,
(+k-1
+
2 Uxe - -ell2 + 4L2
Σ
17 111 u1r1
T=1
+ -1
Σ
Th (V - V v Mei (r,
1/1
T=t
6C2
[+k=1
Th (Zzg( v.) V Vaug(ee, yti Sr 33)) ||
T=t
where 13 = (1,2
212,, 07 1²a
This completes the proof.
Lemma B.10. When To. 31.
1.
the error of the inner variable yt are bounded through Eg.
Proof. then by proposition B.19 and choose 7/ < 4E. we have:
1lue+* yz, 12 s (1 117 Ilve Uz, 11
45: 11 Vo9(I1,))) wwell V 010211
2
Furthermore, by the generalized triangle inequality, we have:
11 Nr.+e
1 112
(1+
Ilye++ - Yxs 11 + (1+
+
118leen yaall
4
5x2
$ (1 +
Ilyc+
Vo 112
|x4 12+2112
4
11
$ (1
1
Ilye Vz211 - ||
22
311122+
5x2
1 F2+x|12
4
1r:
10L #
10
Σ 7r 1| 2, 1|
7r
Vyg(arr vc)
Vng(Ees Mei Sr. [1
f
(19)
where the second inequality due to 7 <
1 < and uses Eq.
17
This completes the proof.
TL
1 Lemma B.11. When Ps IL, the error of variable u, are bounded through Eg. 20
Proof. suppose we choose P. < 1. then we have:
1Pct }1( un, (p:)² | Vr,, (u))12 2 4p: Vra, (u.) qel
|4411 11 5(11 1
P
20

---

Furthermore, by the generalized triangle inequality, we have:
|1444 M 11 S (1
uPr U1 Un,1" 112 + (1
+
4
I|lurrex -Uz, 12
4
P4Pt
Uxz 112 5î.2
- (1 +
PPt
1 Ie++a1?
up:
+ 5L2
S (1
pPr
Ux )||u
1
Pi
Vr (u+)122
100e - F1+1||
pPc
30L20
3002
t+h-1
Pr P+||2: - 21112+ 20L
f+--1
11
vr1l2
Σ
Σ
Prllu ur
14
#K-1
30
Σ
Pr
(V, Mr) Vf (f Vei br.
p.tt
60C
l+k-1
(V be) - V g 91: (r))
(20)
p
1 and Eq. [6). This completes the where the last inequality, we use the condition that Po < 47. proof.
Lemma B.12. Suppose itt S min 96L7 32L*c7 1281 64L"c3 9613e) then the drift of 2 (0r, and u, can be bounded as in Eq. (25) and Eq. (24).
Proof. We first have:
122,
1+11
1|2 < 2|
Σ
?7 (v+
7=1
7=1
1+112 1lve
YoW+ 112
2/1
Σ
7/ (V,g(0z.. yr: (F,1) - Vog(ze, - +
will
7=1
F=1
7-1
[|u 11
Σ
Prqxll 212 2|
Σ
Pt (gr
Vrz (u)) 2(pp) (ut)
(21)
For the term 2| 2, 12, we have || - 2y 11 ||,, - - 2 |/ yr1 11 Combine Eq. 21 with
Eq. and (17). sum over [t, + k 1] and use Proposition B.18 have:
++k-1
1
2
(127, + 41.2 75) || - 27 l12)
T=1
+ 2
Vh ///(xxz))1 + u. V Vyg(zz y1)1
+ 12 (
?1 vell2 + 161. an ( | Mure - uel
1+k11
1-1
+ 16T.
Σ 17
Σ
1=1l4 w=))
7=
7=1
24C?
+ 127m11222-0 02 +
k2
2-2=-22 4m07222-a
2
21

---

By the fact that 7 S + + ki we have:
b+R-1 b+k-1
111120 2+11
(12L](7)) 11 + 41 7c - 2+11
7=t
n=t
+ // V ) - 27 V V Dtlll
+ (7t >11mm>11mm - 3/ll2 + 16L (Th I uzll
1+k-1
+ (7))
Σ 11, - ur 1|
7=t
24C7
+ 12 22 C +
Mhl 2 C² 4ii (22) n²
For ||u, ur|l² 11? we combine Eq. 21 with Eq. (16) and sum over t + k 1] and use the fact
that T <t k to have:
k-k-1
Σ
1r Mrllu 1-112 (7)
(u))l (pe) -vell
7=t
e4k-1
12L37ppp
Σ
Prl1z 21
8882
Σ
Pr 111e ur
24C711
12
2
22kk-a0
(23)
12
Suppose we have 7 = 01
20k1s M1: Pr c2/) = 40n and set:
(i:)2 min
96L2 3212c 1287. 64T2ch 96L3e²
Then we combine Eq.
22 and Eq.
23 to have:
(+k-1
Σ
Tr 1r ur
< (cx
Vr,, (w:)) 4m [V)(z))]
4c
V.,g 1:)1
7=t
48C² + (24 +
48cC7
+ 807 + 24c +
2
(24)
n²
n²
and
64
Σ 1r|1 - 4c Vrz, (u:)]1 + 477 Vh(x:)11 4c7
V V
48C?
48c3C²
+ (24
8ct + 24
+
k
2-
(25)
1
11a
This completes the proof.
Suppose we define the potential function g(():
G. = h(xx)) + o 601l - yns 2 + @ullu: Uzz 1|
where du 32LLm Ft, by = 8L. and L 960k 13 3.3.
p4Pt
Theorem B.13. Suppose Assumptions 4. 4.4 are satisfied, and Assumption 4.55mp satisfied with some We choose learning rates nte 1), Y C1T).
and C for the example order 1 be the total number of steps. Then for any pair of values (E, k) which
in Algorithm [
p = C2 and denote
has T = E x k and 1) < ELo'
we have;
E-1
1
2A kEn
Σ
2
E
where C12 C2. Lo. 1. are constants related the smoothness parameters of h((x), A the initial sub-optimality, R and I are defined in Algorithm 7
22

---

20 n
Proof. First combine Lemma B.9 Lemma B.11 and use the condition that 7
P: 40kLm, and by the assumption about gradient error:
4e, 13(h))
16cz (7:)
Gi*k Ge S
Tt 2
vh(xz)]?²
IV VoD(
[Vrr (2e)l2
m lM vell - -AL Iun, uell
(960k² L2n + +3ス2n + 80x² Lgg+t ((3))>11 +
1|
2+ 12
(640n² (640k2L22,, + ++412n ur11
6C9
80L3
1920n² C7
1/hh--a0²
+ (3
+ 960k2 2 +
(26)
112
n22
112
1/t
Suppose we denote 13 = (960k² 2 13 +
3
+ 80k²
L3
640k2 L +
4L2), and set:
1
L
16L
13
L
( min
16L3
cip2LL
48
8L3
and we bound the terms
|Ma, U4 2| and || 2+ through Lemma B.12 to have:
4
48c]
get* - 9r S 1/ [h(x)))]1 + (24 +
+ 807 + 24c2
+
12
2
112
6C7
3012
1920k C7
1h
n2222 C2
+ (3 +
+
4² + 960k2 +
122
12
Next suppose we set Li < 1, then we have:
4SC? Gi#k - 91 S [h(ra)]12 + (24+ +
48c3C²
11
+
8c7
+ 24c +
2
122
6C
8003
1920k 2 C2
m/ 22
3 +
+
+ 960k2
122
112
112
ilt
For ease of notation we denote 1 = (24 +
48C²
+ 8cf
+
+4cc3
480g +
+ +
6C
801.
+ 9600k2
1²2
1920x 209 then we have:
222n222-a
Gi+k 9. S - [V(x)))1
Sum the above inequality over E phases to have:
Tkk [h((zee)11 < Go- GUE
La L k2 C2
Tike.
E
L mheh 2
$ S +
+ Ar
+
iike
we define An h(xx))()))))))))) h the initial sub-optimality of the function, A, = 1150 yao Il2 as the
initial sub-optimality of the inner variable estimation, A, = ||240 Uzz 2|2 as the initial sub-optimality of the hyper-gradient estimation. Then suppose we choose T/t = ri be some constant, then we have:
km
Vh(Ixe))1 An + o.A, + A.A. L'ER--a CC2n
23

---

Divide by kEn/2 on both sides to have:
E-1
Σ
[h(zke)]
KEn (An A,Ay + +.A..) - - kack C²
E c=0
Suppose we choose the largest kLo satisfied, then we have:
such that the conditions of Lemma B.9 Lemma B.12 are
E
20. (A+0, + ).) + + C2
Σ
(h((zee)
E
E
Then to reach e-stationary point, need to have:
4 1/a
4 and k 2
E
e2
1 2+2//o
in other words T Ek
This completes the proof.
B.2 Proof for conditional bilevel optimization problems
In this section we study the convergence rate of Algorithm 2
Lemma B.14. For all t 0 and any constant k 0, suppose TJ- IT. the iterates generated satisfy:
kn 8
km 1
4x (1920 + 96 * 2413)
48L;
h(I+4K) S h(xx))
[h(x))1
3(1+
n²
kpp / ) + (2i2 + 4 2,nn2
kpp y BiAu
+ 12nkI2
2
2
Proof. By the smoothness of f. follow similar derivation as in Eq. 18). have:
[IVh(x=))] Tt Vh(aa) 12 Te ||:.11
Mx++k) s h(xx))
In particular, for the term Er 1 (Uz Vh(x;))) we have:
(h((z)) - =1
(Vh(x,) - vM(xn(+)) 12+ +3]
Σ Vh((n(+) - ++(++(+))]1 + +3| Σ 7= [h(I=i v4) 12
F=t
3
Me (Vh(a)) Vh(mn&)) + mp
Σ 1/ ||
pallaz--00 - 2=|1²² + 30%
T1 Vh((z;<>) - 11
(27)
For the third term, we follow similar derivation as in Eq. (1)-Eq. (5). we have:
[[(V((rri++) - -v+) 12
= <I](Vol(Ir: v - V 2z (Ir, wh., Jus; - (xr - V Vang ft (Fr. Ur,
11
< <2ii1lus; Vr.1.112 + 1 ur 11
(28)
where it (I.2 212,07)
Combine Eq. 17 and Eq. 28
have:
++ 1
h((++)) S h((x))
πt [h(a;))1= 17,
Th
1
3
(Vh(z,) - vh(zi;+))) ?
2
2
37,2 6+k-1
h+-1
+
Σ
n Øt 1|
Σ
n-
Vo. 112 + +61.21165 u. 112)
2
T=1
(29)
24

---

For the term Σ - 17 1/1121 10,l-==111=_ by Eq. 27 and Eq. 28
we have:
|00 - 2z
2 1 21
Σ 17 (v+ vh(xz))] 2(m)) 2 Vh
$ 6|
Σ
!F (Vh(zz) vh(ar:++)||| m.
1/ 20 |=
7=1
7=1
r-1
+ 6.
Σ
1/r (2L - yr,Ti 112 1 ur. + 2( 2
1=t
++
S 61 20ck2-n00
+ 6T.21
Σ
1/ x2 x+|1
(
+ Gî
Σ
(2
Vr,T. 11? + 112 m1 2(7)) 2(
Multiply 7/r on both sides and sum over [t, + k 1). we have:
r+k-1
t4k-1
(1 11-67- (T))
Σ
nr mrll 2.11²² s 6(1)) )
Σ
(2i.
Ur.TI 112 112 41,3 ur 113)
7=1
+ +
6
By the condition that < 47. we have:
*
Σ Mr 82
x-1 11 12)))
Σ
1/
(2i VF.T 112 -T.2 u=.r.112)
4
(xx))1
127
(30)
Combine Eq.
30 with Eq. 29 then we have:
t+k-1
M((44) S h(x.))
2 (Z (/(z>))
Th ||0,
+
3
Σ 7=1
nr (Vh(z)) vh(zi;)))) ||
2TT.
f+k-1
181. 1182" + (1+ 12.3))2
Σ
(3i. ソ7.m 122 6I.211u5; u-
7r
πt Vh((t))) )1 N1 10,1112 +
3 -12k2 C
< (xxs)
h4k-1
Σ Th (6ūilb Vr 112 12L u. u. 1: 113)
(31)
where the second inequality uses the conditions that i7. <
1 4L. By Lemma B.16 we have:
km 8
- Kt 4
4k (19203 + 96 244.3)
4822
M(x11) S h(x))
|0..112 + 3(1 +
)kk
C
n22
u22
12nkLL
( m. 3nk(213 + 4 96* 3.)x
kp 2
/
(32)
2
where A, and A, denotes the upper bounds of the initial estimation errors of yo and Ug This completes the proof.
Lemma B.15. Suppose we have Ft <
2T. and Pt
1 then Er= 21 11 3i and
2T.
E + Py Ilu uy 112 can be bounded in Eq. 33 and Eq. 334
25

---

Proof. We first bound
Σ/
+ 11'=
Np 11yp - -vll?, in fact, we have:
-111
1'-1
11 yr 112
Σ
7p
up 112
s 211
Σ "p ( 1'=i
Vug(z, (1)(11))))1++ + ) ViVVy((z,)) w)ll
1-1
$ 1 11
7ip lup - -ill2 + 2 ) V vo (1)2 + 41l
Σ
(V v
2 (2, v)) -Vus( w1)
7p
P=1
P=
1+
$ 4l
Σ
mp 1lup - sel1 +
+ 47222-a
P=1
Multiple ' both sides, and then sum 1' in 1 + h 11. we have:
H+--1
E
H ler y012 s gfc..w00 w)ll+ 48m7 2
Since have F2
we have:
14k-1
Σ
W llur - uill 17544(10 4(7)) w)l 87nf
(33)
F-1
Next for E1-
Pr llue up 112, we have:
(-1
(-1
||4 - ur 1| =
Σ 0p9p
12 1155 21 Σ
pr pp(1 (ap Vra(u))]1 + +2 ( Vr.(u))1
P=
P=1
< 121
Plly - yn + +LL2
Σ P=1
Pp Ily - up 12 + ) (1 (w))l
1-1 Σ P=1
24C7
+
pp (V)=g(z, - v y (x, vm.
12
4
24C7
< 1213(p:))llue - yn + 8L2 pt
Σ
pp 11 up 112 + 2
122 22
Multiple Pr on both sides, and then sum /' in [1,1 + k 1]. we have:
1+k1
24C7
(1-8L'p) P
Σ
Pe 11u
ur 1r 1 12 - yn 11 2 + 2(p)) (r)((1)11
4² pipi 2
d'=1
Since we have #t
2L we have:
1+h-1 1
48C²
Pr |1y ur 1 < 24L 11y vn + --m.-
+ 4²2 pupp (34)
Lemma B.16. When 7o <
128 and P. < 250 the error of the inner variable and the variable
1
ii are bounded through Eq. and Eq. (36)
Proof. Since the outer iteration & is fixed for each inner loop, we omit and & in the notation for clarity. Furthermore, we assume performing the updates to y and u separately in Algorithm 2 Although the alternative updates in Algorithm 2 is appealing in practice we can reuse V. V.g for
26

---

yggg, update first and a next can avoid treating complicated higher order terms. Follow similar
derivation of Lemma B.10 if T
< AL we have:
| 1ol2 s (1
1622
llye Vell
IV
[vg((,,))1
2
1+k-1
I+k-1
+ 8L
T'
Ilve - well
8
Σ
" (Vog(a, Vyg(o, mi 4r ||
t'=l
I'=l
Combine with Eq. 33) and use the condition that 7
L s7. we have:
T281.
llu+* Uzll2 (1 1*
V Vog(r, Il + 64 02 8 2² C²
2 Ill v=
Suppose we perform E, rounds, then by telescoping. we have:
lly 3z112 SPS50 (1 -
kur Fa I1vo y=ll
24k -4
E
Σ
(1 kip )
, (0--0-00 k272
V Vug(ar yekk yok)), )1?
n2
4
(35)
Next, follow similar derivations in Lemma
B.11 and choose Po 41. then have:
[|44 - uzl1? S (1
14Pt
)|uu - u
(pt)2
(vr((u))
2
(pe
11ve - yn 11
2
48C7
14k-1
+ 16LK
Σ
Pr -
Σ
Pr (Vygg(,vv)) V -0
Uni (r):
p
(=1
1'=1
Combine with Eq.
34 and the condition that Pt 250T.
41. we have:
||4μ Uz 2 < (1 uPt
1|u - un (pt)²
4 VV
(4))12
48L3(p))
1t - Vn 112
9607
k2 C2
we perform Es rounds, then by telescoping, we have:
|lz uzll S
kipp
Fi Fil/u0
1x112+
1920302k
9116 42
1ly 3211
2
1t
kppp )
k2p² (
(-
+
Σ
V VVrTz(uek)
(36)
2
This completes the proof.
Theorem B.17. Suppose Assumptions 4.1 4.4 and 4.7
4.7are are satisfied, and Assumption 4.5 is satisfied with some a and for the example order we use in Algorithm 2 We choose learning rates 1 SkT. it 7 256kIxx Pt and
m be the total number of outer steps max(n:) be the maximum inner steps. Then for any pair of values (E, k) which has T = E k and Ti = F₁ x k we have:
512kLx and denote
Σ
E-1 [V((Tt))1
8An
KEn + C.
kpp B C₁
kuY y + (C')20*
where Cu Cg. C, are constants related to the smoothness parameters of h(t), An Au A, are the initial sub-optimality, R and S are defined in Algorithm
Proof. First, by Lemma B.14 we have:
kn
[h(2z)) kn |lell +3(1+ 4k (19207 + 96 * 24i33
48
h((144) S h(xz))
n 02
412
112
kppp ) A. + 3n + 4x 96 11)(1 (1-
kpp y A
12nkLI
2
2
27

---

Sum the above inequality over E phases to have:
km E-1
An + 12nkEL2 kue A. +3nk + 96x 26)
ky7 ) D
Vh(aae)]1
2
+ 3F + 41921 + 96 * 24L3)
4872
1 C²
11a
n²
Divide by kEn/8 on both sides to have:
8An [h(
+ 96L kpp Er A, 24((2 + = 96xxx
kp7 k D.
kEn
2
4n² (192C) + 96 2413) 24(1+ +
487,
k 0²
112
112
By the condition
<
1
<
128kLx
and p 256kLx we choose
8kī
256kLx and
p
512kL then have:
1
64L
kpp B1 A. + 244
kyr y Ay
967.2
+ +4* 96x2
E
E
2
4x (192C? + 96 * 2443)
4882
+ 24(11
+
b -
122
Then to reach e-stationary point, need have:
E 128LA and kn
48C²
4k 4k92192)
+ 96 24[3)
48i2 112
112
and E Ollog(( This completes the proof.
Proposition B.18. Given Assumptions 4.4, Assumption and Assumption hold, then
we have: I 7+ (V Uz.) ) V Va Mr: 122 S -2 for any S +
The same upper bound is achieved for other properties: Vh(w), faf( y). Vyg(( 3). V Vy=g(z,8) V Vayg(E,V) v)
Proof.
This proposition can be adapted from Lemma 2 of 34
Proposition B.19. Suppose have function g(y), which is L-smooth and p-strongly-comvex, then suppose शे. the progress made by one step of gradient descent is:
11 - v-1 -
s (1- (1- 1
VV 1 (1)0)111 + 4 [ - will
-
where y is the minimum of g(y) and we have update rule ys41 = 7wa-
Proof. First, by the strong convexity of of function g(v), we have:
o(v") 2 g(v)) Vyg(w)). ve) + / Ily" yell
g(m)) Vyg(()). v141) (V,g(u)), w041 3e) + 1 "1y" 20l1
(37)
2
Then by L-smoothness, we have:
2 1 vell g(v4+1) g(vr) (V Me+1 -2
(38)
28

---

Combining the 37 with 38 we have:
voll2 L
s(v") (((++1) + (V Vyg(ve) v- ve) 7 v.g(())) (((v))),p m²)
2 "1l00
-llt+1 Bell
2 g((+1)) + +2110011 2 11 2y) 2 - 2
2/1u: wl Vug(ve)12 (wor - -vr)
2
+ (v)((1)) - w,,y" - }1 + "1 "Iæ"" vell?
T,7
2 ||we|1?
2 (((++1) + 1/ In?
2 ||w0 11 2 + 7
V Vvg(ve))
? l|u
+ (wi, Vug(vi)]12
ye)
2
2
+ (V - wr, 1² - Ue) + 2
l vel1
By definition of y", we have gvv) 2 ( Thus, we obtain
0 2 L
2 2 well + 2 | V,
7 | Seer-Vaght Vog(Be)12 (we, 38 - Me)
2
2
+ (w)l wt, y n1) + 2 11y" -eel2
(39)
Considering the outer bound of the second term (Vng(ve) - we, 1¹ - ye). we have
(V well? + 1 "lle* 1el12
Vvg(v)) wt. y² ye) S 1
Combining with Eq. 39
0
7 L
2 2 )lwwel 2 + 2
I1 ()((())11?? ) vog(ve)1 1
+weer 10" -Ve)
+ 41 1ly ye 1
By 1 = Jt - your, we have:
Ilue+1 - / 11y, - -u4 - 1²12 = 11ye y²1 27/w1r 81 y²) + 7² 3/21weel] wwel1
$ (1 /4)
1lve 2²12 - -0----111
L |wll + (7² + 22
(ig((( well
2
Then since we choose
1 1 we obtain:
1 101--11122 < (1
1 2
2- Ilue 3-12-
2 [oV(ll1 + 47 Vyg(ve) - will
This completes the proof.
Corollary B.20. For Algorithm and Algorithm 4 suppose Assumptions (the bounded gradient assumption is not required for the minimax problem) and conditions are satisfied in Theorem 4.6 to reach an e-stationary point, we need O(c-A) examples they are sampled independently, while ((max(m,, 33) if some
based without-replacemene sampling is used.
Corollary B.21. For A suppose Assumptions and conditions are satisfied as in Theorem to reach an 6-stationary point, we need O(c-9) examples if they sampled independently. while ((max(m, p)) if examples are sampled following some random- random-permunn pernutatio-mm-beeeecce without- replacement sampling.
It is straightforward to derive the above corollaries from Theorem 4.6land Theorem proof here.
4.8
we omit the
C Comparison of WiOR-BO with Other Acceleration Methods of Bilevel Optimization
In this section, we compare our algorithms with other variance reduction based algorithms for bilevel optimization. For the unconditional case, WiOR-BO obtain the same O(e-3) rate as STORM-base
29

---

Table 2: Comparisons of the Bilevel Opt. & Conditional Bilevel Opt. algorithms for finding
an c-stationary point. An e-stationary point is defined as VVh(>)] I c. Gc(f.c and Gelg. c) denote the number of gradient evaluations w.r.I. f(x,y) y) and g(r, JV denotes the number of Jacobian-vector products; HV (g, e) is the number of Hessian-vector products. m and n are the number of data examples for the outer and inner problems, in particular, is the maximum number of inner problems for conditional bilevel optimization. Our methods have a dependence over example numbers (max (m,, n2 q is value decided by without-replacemmnnt sampling strategy and can have value in [0, 1] (A herding-basse permutation [33]
can let 0).
Setting
Algorithm
Ge(f.c)
Gelg.c)
(g.
(V.g.c)
117
Ole
Ofe 9
O +
B.O.
TISA 22
Ole-9)
Ole
Ole
Ole
StocBiO
Ole
Ofe
Ole
SOBA 9
O(-
O
O
Ole
O(e
Ofe
Ole
VRRO 14
O(e-))
O(e
O(e
Ole
SABA g
O(maz(m, n33/9,
O(mazz(n (m,, 2/3 9)
O (m, n)2/3
O (m, m)2/8g 2)
SRBA 110
Obnazim, ?
O(maz(nn, 1/9--2
Olmaaron, 1/2
Of (mt, ma) 12---
WiOR-BO(Ours)
O((mar(mm x3]
(lmarion, nl)f
Oimarzfon nlf9e
Ol (mmar(m,
DI-SGD
O(:
O
Cond. B.O.
KE-MLMC A3
O O( (m, 10)))
Ole
Ole O mi)
WiOR-CBO (Ours)
Ol(maztm, Pi)
O(n(maz (n, 2)
algorithm MRBO 22 while is slower than SVRG-type algorithms which have 0(n2e-2) such 9 and SRBA [0]] This relationship is similar to that for the single level optimization problems. However, SGD-type algorithm, WiOR-BO is much simpler to implement in practice compared to STORM-based and
as VRBO (2). SABA
algorithms. More specifically, WIOR- BO has fewer hyper-parameterr (learning rates for inner and outer problems) tune compared to MRBO, which has six independent typer-parameterd and the optimal theoretical convergence rate achieved only the complicated conditions among of [52] are satisfied, and this requires significant effort in practice. Next, CRBO/SABA evaluates the full syper-gradient at the start of each outer loop, where we need to evaluate the first and second order derivatives over all samples in one step, which is very expensive for modern ML models (such as the transformer model with billions of parameters). In contrast, our WiOR-BO never evaluates the full gradient. Note that the inner loop length / = lem (emm(m, n)) is analogous to the concept of "epoch" single level optimization: where we go over the data samples following a given order, but at each step evaluate gradient over mini-batch of samples. The practical advantage of our WiOR-BI BO is further verified by the superior performance over MRBO and VRBO in the Hyper- Data Cleaning Task.
are satisfied in Theorem
30

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide detailed discussion of our proposed algorithms in the section 'Without Replacement Sampling in Bilevel Optimization', and followed by theoretical and numerical studies in the subsequent sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our theoretical analysis based on set of assumptions and we discuss their limitations at the start of the section 'Theoretical Analysis'.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: Assumptions and Proofs are included the 'Theoretical Analysis' section in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: we clearly discuss the experimental settings in detail section 'applications and numerical experiments'
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: the datasets used in experiments publicly available and we include the code implementation in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc)
aublic//uidde//Coeetuuiiiss
www.sssinnoooiyylooooooool for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtp:/cccppppgguuuaiaeeeaecc Ctteeee//ooSSSSSSSSS.Se.a www.ssssiicgcyooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Most of the experimental details can be found in Section 5, while the rest is included in the AppendixAA A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The numerical experiments in the paper are averaged over 5 independent runs and we report the mean and standard deviation (shadowed area).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We state the compute resource to run our experiments at the start of Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://wwripp..cpcuuuttttttttta
Answer: [Yes]
Justification:
We follow all of NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work related to the theoretical aspect of Machine Learning. The topic of the paper, bilevel optimization, has many applications in machine learning. So there are some potential societal consequences of our work when our algorithms are applied various machine learning tasks, but none which we feel is directly related to our algorithm.
34

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All the datasets used in our experiments are publicly available
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "sIBR8gJZhH", "reviewer": "Reviewer_1Xqw", "summary": "The paper introduces a new algorithm called WiOR-BO, which leverages without-replacement sampling to achieve faster convergence rates compared to traditional independent sampling methods. The algorithm is applied to standard bilevel optimization, conditional bilevel optimization, and specific cases such as minimax and compositional optimization problems. The authors provide a theoretical analysis demonstrating that WiOR-BO achieves a significantly improved convergence rate over existing methods. Empirical validation on synthetic and real-world tasks, including hyper-data cleaning and hyper-representation learning, shows the superior performance and computational efficiency of the proposed algorithms.", "questions": "1. Comparative Benchmarks: The paper provides empirical validation, but could the authors include more comprehensive comparisons with state-of-the-art methods, especially in dynamic environments? How does the proposed method perform in cases where data distributions shift over time?\n2. Computational Efficiency: While the method reduces the number of backward passes, how does it scale with very large datasets or high-dimensional data?\n3. Hyperparameter Tuning: Could the authors elaborate on the process of selecting hyperparameters, such as learning rates and other tuning parameters? Specifically, are there any strategies employed to avoid overfitting during hyperparameter tuning? Additionally, how sensitive is the performance of the algorithm to these hyperparameter choices, and have the authors conducted any sensitivity analyses to assess this? Addressing these points could provide more clarity on the robustness and practical implementation of the proposed algorithms.", "limitations": "Are there any specific limitations that the authors anticipate in applying this method to different domains or tasks? What future directions do the authors envision for improving the algorithm, particularly concerning hyperparameter tunning, adaptivity and scalability?", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "By employing without-replacement sampling, the algorithm effectively reduces the number of necessary backward passes, leading to substantial computational savings. This is especially beneficial in large-scale machine learning models where back-propagation can be expensive. The algorithm's design allows for simultaneous updates of upper and lower-level parameters, improving convergence rates and computational efficiency compared to traditional methods. Additionally, the theoretical guarantees provided on convergence offer a robust foundation for its application, making the algorithm a valuable tool for tasks such as hyperparameter optimization and data cleaning. Its ability to utilize a finite subset of data without replacement ensures reduced variance in gradient estimates, enhancing the stability and reliability of the optimization process.", "weaknesses": "The authors have selected learning rates and other tuning parameters to optimize performance, but they do not report any sensitivity analysis regarding these choices. This lack of analysis leaves open questions about the robustness of the algorithm's performance under different parameter settings. Additionally, there is no provided methodology or algorithm for efficiently selecting these parameters without the risk of overfitting to the validation set, which could undermine the generalizability of the results.\n\nFurthermore, the proposed algorithms are designed under the assumption of a static dataset, which restricts their applicability in scenarios where data arrives sequentially, such as in dynamic or online learning environments. This limitation could be mitigated by extending the algorithms to handle streaming data or datasets that evolve over time, making the methods more versatile and applicable to real-world situations where data distribution may change. Addressing these issues would enhance the robustness and broader applicability of the proposed solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending your valuable time reviewing our manuscript and provide insightful feedbacks. We provide our responses to your comments below:\n\n**Hyper-parameter Tuning**. Our algorithms include three hyper-parameters: the outer learning rate $\\eta$, the inner learning rate $\\gamma$ and the learning rate of variable $u$: $\\rho$, and they are easy to tune and robust to specific choices of hyper-parameters. More specifically, we use **grid search** (as stated in the manuscript) to perform hyper-parameter tuning, which is a standard practice used by optimization literature [1,2], furthermore, we use the loss over a hold-out validation set as the metric for tuning and adopt the early stoping technique. Take the hyper-data cleaning task as an example, we search $\\eta$ in {1, 10, 100, 1000, 10000}, $\\gamma$ in {0.001, 0.01, 0.1, 0.5, 1} and $\\rho$ in {0.001, 0.01, 0.02, 0.05, 0.1}. Similar to the behavior of the learning rate in SGD for single-level problems, the performance initially improves as we increase the learning rate, and it will start to diverge beyond a certain point.  In the following experiments, we perform ablation studies to the learning rates for our WiOR-BO algorithm over the hyper-data cleaning task, where show the validation loss vs Number of Hyper-iterations:\n\n**Table 1**: Ablation Study over $\\gamma$  ($\\eta = 1000$ and $\\rho = 0.1$)\n\n| $\\gamma$ \\ Iters  | 1    | 500  | 1000 | 2000 |\n|---|------|------|------|------|\n| 0.05 | 3.543 | 0.555 | 0.303 | 0.256 |\n| 0.1  | 3.154 | 0.501 | 0.239 | 0.157 |\n| 0.2  | 2.948 | 0.511 | 0.253 | 0.177 |\n\n**Table 2**: Ablation Study over $\\eta$  ($\\gamma = 0.1$ and $\\rho = 0.1$)\n\n| $\\eta$ \\ Iters  | 1    | 500  | 1000 | 2000 |\n|---|------|------|------|------|\n| 100 | 3.238 | 0.656 | 0.465 | 0.256 |\n| 1000  | 3.154 | 0.501 | 0.239 | 0.157 |\n| 10000 | 3.014 | 0.544 | 0.335 | 0.208 |\n\n**Table 3**: Ablation Study over $\\rho$  ($\\gamma = 0.1$ and $\\eta = 1000$)\n\n| $\\rho$ \\ Iters  | 1    | 500  | 1000 | 2000 |\n|---|------|------|------|------|\n| 0.05 | 3.239 | 0.571 | 0.329 | 0.213 |\n| 0.1  | 3.154 | 0.501 | 0.239 | 0.157 |\n| 0.2 | 2.961 | 0.518 | 0.378 | 0.228 |\n\nAs shown by the results in Tables 1 to 3, the best performance is achieved with $\\eta=1000$, $\\gamma=0.1$, and $\\rho=0.1$. The performance with other hyperparameter settings is also comparable.\n\n**Computational Efficiency**. We can discuss the influence of dataset size and model size based on the convergence rate. As stated in Table-1 of the manuscript, WiOR-BO has convergence rate of $max(m,n)^q\\epsilon^{-3}$ and WiOR-CBO has rate of $max(m,n)^{2q}\\epsilon^{-4}$. Note that the convergence rate is measured by the number of gradient queries and our convergence results show that this number is not affected by the model size, however, the cost of one gradient query indeed increases as the model size increase; as for the dataset size, the convergence rate of our model has a dependence of $max(m,n)^q$, where $q$ is a constant that relates to the without-replacement sampling strategy we use. For shuffle-once, we have $q=1$; for random-reshuffling, we have $q=0.5$, and if use the GraB algorithm in [3] (which is based on a herding and balancing), $q=0$.\n\n**Dynamic Environments**. In our manuscript, we focus on the finite-sum setting (i.e. over a static dataset), which is a standard setting in modern machine learning [4], and we also believe it is a suitable setting to study the effect of example correlation effect (due to without-replacement sampling) to the convergence of bilevel optimization. While the dynamic environment setting is an interesting extension, it is beyond the scope of this manuscript and warrants a separate, dedicated study.\n\nFinally, in terms of the limitation, since the convergence results are based on various regularity assumptions to the outer and inner problems, real world tasks might not hold these assumptions. As for the future direction,  we can study the effect of without-replacement sampling under other assumptions, in this manuscript, we consider the nonconvex-strongly-convex class of functions, and we could extend our analysis to other classes of functions, furthermore, the reviewer's advice to consider dynamic environments is also possible.\n\nReferences:\n\n[1]. Yang, Junjie, Kaiyi Ji, and Yingbin Liang. \"Provably faster algorithms for bilevel optimization.\" Advances in Neural Information Processing Systems 34 (2021): 13670-13682.\n\n[2]. Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Bilevel optimization: Convergence analysis and enhanced design.\" International conference on machine learning. PMLR, 2021.\n\n[3]. Lu, Yucheng, Wentao Guo, and Christopher M. De Sa. \"Grab: Finding provably better data permutations than random reshuffling.\" Advances in Neural Information Processing Systems 35 (2022): 8969-8981.\n\n[4]. Johnson, Rie, and Tong Zhang. \"Accelerating stochastic gradient descent using predictive variance reduction.\" Advances in neural information processing systems 26 (2013).", "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": "", "extra_scores": {}}, {"review_id": "tIxCUGS4Cz", "reviewer": "Reviewer_Qw9k", "summary": "This paper investigates stochastic bilevel optimization. One common practice herein is that the data samples used to calculate all the derivatives are mutually independent, which may however introduce more computational cost compared to the case where the samples are reused. Motivated by this, the authors explore stochastic bilevel optimization without using independent sampling, particularly under the without-replacement sampling scheme. Based on previous single-loop algorithm, two with-replacement bilevel optimization algorithms are proposed for standard bilevel optimization and conditional bilevel optimization, respectively, which can also be applied to several special cases. The authors show that faster convergence rates can be achieved by the proposed algorithms compared to the counterparts with independent sampling. Experiments on multiple tasks are conducted to further justify the performance of the proposed algorithms.", "questions": "1. How was the bias due to the without-replacement sampling handled in the analysis? Using window averaging? In this case, did you need to store the gradients of previous samples?\n\n2. When you compared the convergence rate of algorithm 1 with baselines, e.g., stocBiO, how did you justify that the faster convergence is because of the sampling but not the single-loop update? Given that stocBiO is not a single-loop algorithm.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea of investigating bilevel optimization without independent sampling is interesting and novel.\n\n2. Algorithms and theoretical results are provided for various setups with a faster convergence rate.\n\n3. The experimental results also clearly show the superior performance of the proposed algorithms.", "weaknesses": "1. It is not clear what the key technical contributions in the theoretical analysis are.\n\n2. As the authors claim the extension to the special cases of minimax and compositional optimization problems as a contribution, it is better to compare with the baselines in these problems.\n\n3. The presentation can be further improved. For examples, the figures in the experiments are not clear because of the small font size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending your valuable time reviewing our manuscript and provide insightful feedbacks. Our responses are provided as below:\n\n**Technical contributions**. We provide the first theoretical analysis of bilevel optimization that uses without-replacement sampling. A key insight in our analysis is to *analyze the descent of potential function over an interval of length k instead of one step*. This is important as only the amortized gradient estimation error ($|\\frac{1}{k}\\sum_{\\tau=t}^{t+k-1}\\nabla f(x,y,\\xi_\\tau) - \\nabla f(x,y)|$) of without-sampling exhibits improvement compared to independent sampling. Meanwhile, we need to carefully balance the intertwined hyper-gradient estimation, inner variable estimation error and the estimation error to $u_x$ in the analysis.\n\n**Fair-Classification Task**: we provide further experimental results over a fair-classification task [1,2], which can be formulated as a minimax optimization problem. More specifically, for a classification task with $K$ categories, the objective minimizes the maximum loss over all categories, this improves the fairness among different categories. The objective is as follows:\n\n$$ \\min_{w}\\max_{u \\in U} \\sum_{i=1}^K u_i L_i(w) - \\lambda ||u - \\frac{1}{K}||^2$$\n\nwhere $u_i$ is the weight for category $i$ and $U$ denotes the probability simplex, $L_i(w)$ denotes the classification loss over category $i$ and $w$ is the model parameter. Follow the setting in [2], we consider  T-shirt/top, Coat and Shirt categories\nin the Fashion-MNIST dataset (K = 3) and solve the objective with SGDA [3], WiOR-MiniMax-SO and WiOR-MiniMax-RR. Note that SGDA performs the minimization and maximization alternatively and differs our WiOR-MiniMax-SO(-RR) only in the sampling strategy. Be We show results in the table below, we show the training loss across different epochs:\n\n| Method \\ Epochs             | 1     | 5     | 10    | 20    | 30    | 50    |\n|---------------------|-------|-------|-------|-------|-------|-------|\n| SGDA                | 0.703 | 0.339 | 0.266 | 0.223 | 0.176 | 0.164 |\n| WiOR-MiniMax-SO     | 0.654 | 0.319 | 0.252 | 0.207 | 0.162 | 0.125 |\n| WiOR-MiniMax-RR     | 0.648 | 0.322 | 0.248 | 0.208 | 0.160 | 0.133 |\n\nAs shown in the table, our algorithms outperforms SGDA, which demonstrate the efficacy of using without-replacement sampling.\n\n*Responses to Reviewer Questions*\n\n*Q1: How was the bias due to the without-replacement sampling handled in the analysis? Using window averaging? In this case, did you need to store the gradients of previous samples?*\n\n**A1**: We do not need to store the gradients of previous samples, and the window averaging is solely for analysis purpose. For example to bound the estimation error of $\\nabla_x f(x_t, y_t; \\xi_{t})$ to $\\nabla_x f(x_t, y_t)$, we bound the following term $||\\sum_{\\tau=t}^{t+k} (\\nabla_x f(x_\\tau, y_\\tau; \\xi_{\\tau}) - \\nabla_x f(x_t, y_t))||^2$ and this term can be further broken into two sub-terms: $||\\sum_{\\tau=t}^{t+k} (\\nabla_x f(x_t, y_t; \\xi_{\\tau}) - \\nabla_x f(x_t, y_t))||^2$ and $||\\sum_{\\tau=t}^{t+k} (\\nabla_x f(x_\\tau, y_\\tau; \\xi_{\\tau}) - \\nabla_x f(x_t, y_t; \\xi_{\\tau}))||^2$. For the first term, the error decrease as $k$ increase (as we will go through more samples due to without replacement sampling), while for the second term, it is equivalent to bound $||(x_\\tau, y_\\tau) - (x_t, y_t)||^2$ by the smoothness assumption and this variable drift term can be bounded by tuning the value of learning rates.\n\n*Q2: When you compared the convergence rate of algorithm 1 with baselines, e.g., stocBiO, how did you justify that the faster convergence is because of the sampling but not the single-loop update? Given that stocBiO is not a single-loop algorithm.*\n\n**A2**: The rate improvement is indeed due to the without-replacement sampling strategy. SOBA[4] also adopts a single loop update rule, but this algorithm also obtains the same $O(\\epsilon^{-4})$ rate as stocBiO.\n\nFinally, thanks for your review again. We will also carefully polish our presentation, including the font sizes in the figures suggested in your review.\n\nReferences:\n\n[1] Nouiehed, Maher, et al. \"Solving a class of non-convex min-max games using iterative first order methods.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[2]. Huang, Feihu, Xidong Wu, and Zhengmian Hu. \"Adagda: Faster adaptive gradient descent ascent methods for minimax optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n[3]. Lin, T., Jin, C., and Jordan, M. (2020a). On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083–6093. PMLR.\n\n[4]. M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXiv:2201.13409,2022.", "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": "", "extra_scores": {}}, {"review_id": "5mqb0isaMr", "reviewer": "Reviewer_sRYA", "summary": "This paper improves the computational inefficiencies in bilevel optimization algorithms that rely on independent sampling. It proposes a novel without-replacement sampling-based algorithm, which achieves a faster convergence rate than existing methods.", "questions": "Please refer to weaknesses.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper develops independent sampling for bilevel optimization, which save the large number of backward passes and improve the convergence rate. Experimental results show the good results compared to other bilevel baselines.", "weaknesses": "- The paper claimed that \"Compared to independent sampling-based algorithm such as stocBiO, we require extra space to generate and store the orders of examples, but this cost is negligible compared to memory and computational cost of training large scale models.\" Is there any empirical result to show the memory costs?\n\n- Projection is applied to $u_i^r$, but I found other bilevel papers (such as StocBio, BSA) don't use that. Is there any intuition or explanation about that?\n\n- In Algorithm 2, the generation of $\\\\{\\zeta_{\\xi_t^{\\pi}, t_l}^{\\pi} \\in \\mathcal{D}_{l, \\xi_t^{\\pi}}. t_l\\in [T_l]\\\\}$ is not very clear. It seems that there are $S\\times n_i$ samples for inner loops given a outer sample $\\xi_i$. How do you execute the permutation for the inner dataset.\n\n- In experiments, what is the best hyper-parameters for each baselines, such inner and outer learning rates?\n\n- What are the details of data sampling for other baselines? For other baselines, they usually need the independent training and validation set for upper and lower-level update, how did you construct data for them?\n\n- Typos: Line 107, $w_x$ should be $u_x$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending your valuable time reviewing our manuscript and provide insightful feedbacks. Our responses are provided as below:\n\n*W1: The paper claimed that \"Compared to independent sampling-based algorithm such as stocBiO, ... computational cost of training large scale models.\" Is there any empirical result to show the memory costs?*\n\n**R1**: In our algorithms, we maintain the permutation of example indices. For example, in the Hyper-Data Cleaning Task: we have 40000 training examples and 5000 validation examples and we store the permutations with numpy.uint16 data type and this leads to memory cost of 90KB. Meanwhile, the GPU memory related to training neural network is around 20.07MB, which is roughly 200 times greater than the memory used to store the index permutations. Note that for large scale neural networks, this ratio will be larger. Additionally, the permutation process is executed on the CPU and does not consume expensive GPU memory.\n\n*W2:Projection is applied to $u$, but I found other bilevel papers (such as StocBio, BSA) don't use that. Is there any intuition or explanation about that?*\n\n**R2**: Note that our algorithms perform single loop update, i.e. update $x_t$, $y_t$ and $u_t$ alternatively; in contrast, stocBiO and BSA are double loop algorithms, where for each $x_t$, they use a loop to estimate $y_{x_t}$ and the corresponding hyper-gradient, and there is no variable $u_t$ involved. Recall that  $u_t$ is used to estimate the solution of the quadratic problem in hyper-gradient computation, i.e. $u_x =  \\nabla_{y^2} g(x, y_x)^{-1} \\nabla_y f(x, y_x)$ and we only apply projection operation to $u_t$, therefore, stocBiO and BSA does not need the projection. In fact, this projection operation guarantee $u_t$ is always bounded during the update and is essential in the analysis. The projection operation can be found in recent single loop bilevel algorithms such as SRBA in [1].\n\n*W3: In Algorithm 2, the generation of is not very clear. It seems that there are  samples for inner loops given a outer sample. How do you execute the permutation for the inner dataset.*\n\n**R3**: As we state in line 149-150 of main text, for the inner dataset, we concatenate $S$ random permutations of the inner dataset $D_{l,\\xi_t^{\\pi}}$ to get {$\\zeta_{\\xi_{t}^{\\pi}, t_l}^{\\pi} \\in D_{l,\\xi_t^{\\pi}}, t_l \\in [T_l]$} with a sequence length $T_l = S\\times n_{\\xi_i}$. To put it simply, for each given outer example $\\xi_{t}^{\\pi}$, we go through its corresponding inner dataset $S$ rounds, and for each round we go through the inner dataset following a random permutation.  Finally, we correct a typo in the Line 7 of Algorithm 2: it should be {$\\zeta_{\\xi_i, j}^{\\pi}, j\\in[n_{i}]$} instead of {$\\zeta_{\\xi_i, j}^{\\pi}, i\\in[n_{i}]$}.\n\n*W4:In experiments, what is the best hyper-parameters for each baselines, such inner and outer learning rates?*\n\n**R4**: For the invariant risk minimization task: the inner and outer learning rates are 0.001; for the hyper-data cleaning task: reverse, stocBiO, BSA, AID-CG, WiR-BO, WiOR-BO-SO, WiOR-BO-RR use inner learning rate 0.1 and outer learning rate 1000, WiR-BO, WiOR-BO-SO, WiOR-BO-RR set $\\rho = 0.1$; MRBO uses $d=10$, $m=500$, $c_1=0.9$, $c_2=0.9$, $\\gamma=500$, $\\lambda=0.2$; VRBO uses $q=5$, $\\alpha=1000$, $\\beta=0.2$; for the hyper-representation learning task: for the Omniglot dataset, the outer learning rate is 0.1, the inner learning rate is 0.4, $\\rho = 0.002$; for the MiniImageNet dataset, the outer learning rate is 0.05, the inner learning rate is 0.01, $\\rho = 0.002$, for the RL-MLMC baseline, we set $K_{max} = 6$.\n\n*W5: What are the details of data sampling for other baselines? For other baselines, they usually need the independent training and validation set for upper and lower-level update, how did you construct data for them?*\n\n**R5**: In our empirical implementation, we use a dataloader class to handle example sampling. For our algorithms, the dataloader returns examples following the order of a permutation, while for other baselines that require independent sampling, the dataloader will randomly sample a mini-batch of samples (sample indices) from the whole dataset.\n\n*W6: Typos: Line 107 $w_x$, should be $u_x$.* \n\n**R6**: We will correct this typo and carefully proofreading our manuscript.\n\nReferences\n\n[1]. Dagréou, Mathieu, et al. \"A lower bound and a near-optimal algorithm for bilevel empirical risk minimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "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": "", "extra_scores": {}}, {"review_id": "geOlM0EoLg", "reviewer": "Reviewer_TL81", "summary": "This paper introduces new algorithms that leverage without-replacement sampling to enhance bilevel optimization. The main contributions are:\n1. Introducing more practical bilevel optimization algorithms using without-replacement sampling.\n2. Providing comprehensive theoretical analysis demonstrating improved convergence rates and efficiency.\nNovel Algorithms: Introduces simpler, more practical bilevel optimization algorithms using without-replacement sampling.\n3. Validating the effectiveness through applications in hyper-data cleaning and hyper-representation learning.", "questions": "Line 71: Please use $O(\\cdot)$ to denote the big O notation and $\\tilde{O}(\\cdot)$ to indicate that logarithmic terms are hidden.\nLInes 131, 536, etc.: Some formulas exceed the line width.", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's strengths can be summarized as follows:\n\nOriginality: The paper introduces a novel application of without-replacement sampling for bilevel optimization, presenting a fresh and practical approach in contrast to traditional methods.\n\nQuality: The research exhibits high quality through rigorous theoretical analysis and comprehensive comparisons with existing methods, showcasing superior performance and efficiency.\n\nClarity: The paper is well-structured and clearly written, effectively communicating complex concepts and providing detailed explanations and results.\n\nSignificance: The proposed methods significantly enhance process efficiency.", "weaknesses": "1. Why are the upper bounds the same in Assumptions 4.3, 4.4, and 4.7?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending your valuable time in reviewing our manuscript and provide insightful comments. \n\nFirstly, about the upper bound in Assumption 4.3, 4.4 and 4.7, we assume a common bound due to the following reasons. Note that these assumptions measure similar properties, namely the sample estimation error of first or second order derivatives, using a unified bound can simplify the analysis and makes the final convergence bound obtain simpler constant factors. In fact, we can assume different upper bounds, but the convergence rates are not affected.\n\nNext, We want to thank you for your advice and will use $\\tilde{O}(\\cdot)$ to indicate that logarithmic terms are hidden. Furthermore, we will adjust the equations so that they can fit into the line width.", "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": "", "extra_scores": {}}, {"review_id": "2EYIVH0Nta", "reviewer": "Reviewer_H8tq", "summary": "This paper proposes WiOR-(C)BO for without-replacement sampling algorithms for (conditional) bilevel optimization. The authors prove the convergence rate for both algorithms under regular assumptions, which are improved upon existing works on the complexity of $\\epsilon$.", "questions": "1. The paper regards the special cases as one of the main contributions. Can the special cases be fully covered by the general cases? Are convergence results or algorithms for these cases different from what we could achieve by applying the general case?\n2. How is $p$ (or $q$) in the convergence rate determined? If it can be forced to 0 by using certain sampling strategy, why not directly use that strategy? Will it contradict with other assumptions?\n3. Why should we use without-replacement sampling rather than with-replacement sampling? I'm asking because I believe SOBA with moving average and with-replacement sampling has a better convergence rate of $\\mathcal{O}(\\epsilon^{-2})$ under regular assumptions. Please correct me if I'm wrong.\n4. Can you compare the emprical performance with SOBA?", "limitations": "The limitations are stated as assumptions.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The assumptions are standard and the convergence rates are better than existing results.\n2. The empirical behaviors are better than compared algorithms.", "weaknesses": "1. The improvement from order $\\mathcal{O}(\\epsilon^{-4})$ to $\\mathcal{O}(\\max\\\\{m,n\\\\}^p\\epsilon^{-3})$ is not as great as stated to be $\\mathcal{O}(\\epsilon^{-3})$. If we can easily ignore the existence of $m$ and $n$, why not calculate the true gradients and Hessian matrices (instead of stochastic estimates) all time and reach a $\\mathcal{O}(\\max\\\\{m,n\\\\}\\epsilon^{-2})$ rate of SOBA? Please clarify the influence of term $\\\\{m,n\\\\}^p$ so that the degree of improvement is clearer. If $p$ can be forced to 0 without additional assumptions, the result will be better.\n2. The $p$ values in both $\\mathcal{O}(\\max\\\\{m,n\\\\}^p\\epsilon^{-3})$ for bilevel optimization and $\\mathcal{O}(\\max\\\\{m,n\\\\}^{2p}\\epsilon^{-4})$ for conditional bilevel optimization are not clear. Please clarify how $p$ is determined. By the way, the authors should have used another character since $p$ has already been used as the dimension of $x$.\n3. The motivation of using without-replacement sampling is not solid. In the introduction section, the author stated that using without-replacement sampling achieves more accurate gradient estimations than with-replacement sampling. However, SOBA implemented by with-replacement sampling can achieve $\\mathcal{O}(\\epsilon^{-2})$ complexity which is better than $\\mathcal{O}(\\epsilon^{-3})$. Could you give some explanations on this?\n4. The novelty in algorithmic design is limited. It looks quite like a direct combination of SOBA and natural without-replacement sampling strategies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending your valuable time reviewing our manuscript and provide insightful feedbacks. Our responses are provided as below:\n\n**Convergence Rate of SOBA**. We first want to clarify that SOBA [1] has convergence rate of $O(\\epsilon^{-4})$ under the notation of our manuscript. In fact, the $\\epsilon$-stationary point in our manuscript is defined as $\\|\\nabla h(x)\\| \\leq \\epsilon$. Note that the SOBA paper uses an alternative definition of $\\|\\nabla h(x)\\|^2 \\leq \\epsilon$. \n\n**The value of $p$**. Our WiOR-BO has convergence rate of $O(max(m,n)^p\\epsilon^{-3})$, note that this rate is strictly better than the $O(\\epsilon^{-4})$ rate of stocBiO, BSA and SOBA. As for the value of $p$, it relates to the specific example order we choose. More specifically, in Assumption 4.5 (i.e. how well the consecutive example gradients approximate the true gradients), we have the constant $C = \\max(m,n)^pA$. For shuffle-once, we have $p=1$, for random-reshuffling, we can show $p=0.5$, while for the GraB algorithm~[2], we can reach $p=0$.  In our experiments, we consider the random-reshuffling and shuffle-once, as for the GraB algorithm, although it has favorable property that $p=0$, we need to store at least one gradient (also Hessian in the bilevel case), and this leads to $O(d^2)$ extra space, which is expensive for large scale neural networks.\n\n**Comparison with other Methods**.  In Table 1 of the manuscript, we compare WiOR-BO with methods such as stocBiO, BSA, and SOBA, which all adopt SGD-like updates. Our algorithm differs from these methods in the sampling strategy. The faster convergence rate of our algorithms demonstrates the efficacy of using without-replacement sampling. Then in Table 2 of the Appendix, we include more algorithms, some of them obtain faster convergence rate than WiOR-BO, yet this is achieved by using some form of **variance reduction technique**. For example, SABA ($O(max(m,n)^{2/3}\\epsilon^{-2})$)  is based on SAGA, SRBA ($O(max(m,n)^{1/2}\\epsilon^{-2})$) is based on SARAH, while MRBO ($O(\\epsilon^{-3})$) is based on STORM. However our algorithm still demonstrates favorable empirical advantages over these variance-reduction enabled methods. In fact, WIOR-BO has  fewer hyper-parameters (learning rates for inner and outer problems) to tune compared to MRBO, which has six independent hyper-parameters, and the optimal theoretical convergence rate is achieved only if the complicated conditions among hyper-parameters are satisfied in Theorem 1 of the MRBO paper are satisfied, and this requires significant tuning effort in practice. Next, SRBO/SABA evaluates the full hyper-gradient at the start of each outer loop, where we need to evaluate the first and second order derivatives over all samples in one step, which is very expensive for modern ML models (such as the transformer model with billions of parameters). In contrast, **our WiOR-BO never evaluates the full gradient**. Note that the inner loop length $I = lcm(m,n)$ is analogous to the concept of \"epoch\" in single level optimization: where we go over the data samples following a given order, but at each step we evaluate gradient over a mini-batch of samples. The practical advantage of our WiOR-BO is further verified by the superior performance over MRBO and VRBO in the Hyper-Data Cleaning Task. \n\n**Novelty**:  Without-replacement sampling is widely used in practice in model training including bilevel optimization. However, most existing literature for bilevel optimization assumes the independent sampling assumption to simplify the analysis. To the best of our knowledge, our WiOR-BO (WiOR-CBO) is the first without-replacement sampling bilevel algorithm with theoretical guarantee.\n\n*Responses to Reviewer Questions*:\n\n*Q1: The paper regards the special cases as one of the main contributions. Can the special cases be fully covered by the general cases? Are convergence results or algorithms for these cases different from what we could achieve by applying the general case?*\n\n**R1**: Due to space limitation, the convergence results of the minimax and compositional cases are deferred to Corollary B.20 and Corollary B.21 in Appendix. For the compositional case, we can directly apply the analysis of bilevel optimization and get the same convergence rate. For the minimax case, we need to remove the bounded gradient assumption, i.e. $\\|\\nabla_y f(x,y, \\xi) \\| \\leq C_f$ as this assumption conflicts with the assumption of $\\mu$-strong convexity with respect to y. Once this assumption is removed, we can follow the same analysis used in bilevel optimization to establish the convergence rate for the minimax case.\n\n*Q2: Can you compare the emprical performance with SOBA?*\n\n**R2**: In the Hyper-Data Cleaning task, we have compared with SOBA in the name of WiR-BO.  We use the name WiR-BO as there are several single loop bilevel algorithms such as AmIGO [3] and FSLA [4] in the literature. We also compare with variance-reduction enable methods: MRBO and VRBO.\n\nFinally, we want to thank the reviewer once again. If anything remains unclear, please do not hesitate to let us know.\n\nReferences\n\n[1]. Dagréou, Mathieu, et al. \"A framework for bilevel optimization that enables stochastic and global variance reduction algorithms.\" Advances in Neural Information Processing Systems 35 (2022): 26698-26710.\n\n[2]. Y. Lu, W. Guo, and C. M. De Sa. Grab: Finding provably better data permutations than random reshuffling. Advances in Neural Information Processing Systems, 35:8969–8981, 2022.\n\n[3]. M. Arbel and J. Mairal. Amortized implicit differentiation for stochastic bilevel optimization,2021.\n\n[4]. J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36,pages 7426–7434, 2022", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces WiOR-BO, a new algorithm that leverages without-replacement sampling to enhance the efficiency of bilevel optimization. The method is designed to address the limitations of traditional SGD-type bilevel algorithms, which rely on independent sampling. WiOR-BO is applicable to standard bilevel optimization, conditional bilevel optimization, and specific cases such as minimax and compositional optimization problems. The authors provide theoretical convergence guarantees and demonstrate the algorithm's effectiveness through empirical validation on multiple tasks.

Pros:

Novel Application: Introduces without-replacement sampling to bilevel optimization, a relatively unexplored area that offers potential benefits in terms of computational efficiency.
Theoretical Contribution: Provides a comprehensive theoretical analysis, demonstrating improved convergence rates compared to existing methods.
Empirical Validation: Strong empirical results on various tasks, showing the effectiveness of the proposed algorithms.
Practical Relevance: The proposed method offers a practical alternative to existing bilevel optimization algorithms, particularly in large-scale machine learning scenarios.

Cons:

Limited Novelty in Algorithmic Design: The method is perceived as a direct combination of existing techniques (e.g., SOBA) with without-replacement sampling, limiting the novelty.
Unclear Theoretical Advantage: Despite the theoretical contributions, the actual advantage of the proposed method over deterministic and stochastic SOBA remains unclear, especially when considering both gradient and Hessian terms.
Complexity Considerations: The improvement in convergence rates is not as significant as initially claimed, leading to questions about the overall theoretical superiority of the method.
Presentation Issues: The clarity of some figures and explanations in the paper could be improved, particularly in terms of technical details and parameter settings.

Thins that should be addressed when preparing the final version of the paper.

-  There are lingering concerns about the theoretical advantage of the proposed method over existing methods like deterministic and stochastic SOBA, particularly in terms of the trade-off between gradient and Hessian complexities.

-  While the empirical results are strong, the theoretical justification for why the proposed method is preferable in all scenarios remains insufficiently addressed.

The paper offers a meaningful contribution to bilevel optimization, particularly through its introduction of without-replacement sampling. However, the novelty and theoretical justification of the method require further clarification. The empirical results are compelling, but the paper would benefit from additional theoretical insights and clearer presentation of its advantages over existing methods. These issues can be addressed when preparing a camera ready version.
Decision: Accept (poster)