BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization
Authors: Chen Fan
Gaspard Choné-Ducasse
Mark Schmidt
Christos Thrampoulidis
Venue: NeurIPS 2023 poster (2023)
Keywords: Adaptive step sizes
bi-level optimization
convergence rates
line searches
TL;DR: Improving the practical performance of convergent stochastic Polyak step sizes and line searches, and extend them to bi-level optimization

Abstract: The popularity of bi-level optimization (BO) in deep learning has spurred a growing interest in studying gradient-based BO algorithms.
However, existing algorithms involve two coupled learning rates that can be affected by approximation errors when computing hypergradients, making careful fine-tuning necessary to ensure fast convergence. To alleviate this issue, we investigate the use of recently proposed adaptive step-size methods, namely stochastic line search (SLS) and stochastic Polyak step size (SPS), for computing both the upper and lower-level learning rates. First, we revisit the use of SLS and SPS in single-level optimization without the additional interpolation condition that is typically assumed in prior works. For such settings, we investigate new variants of SLS and SPS that improve upon existing suggestions in the literature and are simpler to implement. Importantly, these two variants can be seen as special instances of general family of methods with an envelope-type step-size. This unified envelope strategy allows for the extension of the algorithms and their convergence guarantees to BO settings. Finally, our extensive experiments demonstrate that the new algorithms, which are available in both SGD and Adam versions, can find large learning rates with minimal tuning and converge faster than corresponding vanilla SGD or Adam BO algorithms that require fine-tuning.

BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization
Chen Fan', Gaspard Choné-Ducasse', Mark Schmidt and Christos Thrampoulidis'
University of British Columbia
Ecole Normale Supérieure
CCnadda CIFAR AI Chair (Amii)
Abstract
The popularity bi-level optimization (BO) in deep learning has spurred a growing interest in studying gradient-based BO algorithms. However, existing algorithms involve two coupled learning rates that can be affected by approximation errors when computing hypergradients, making careful fine-tuning necessary ensure fast convergence. To alleviate this issue, we investigate the use of recently proposed adaptive step-size methods, namely stochastic line search (SLS) and stochastic Polyak step size (SPS), for computing both the upper and lower-level learning rates. First, we revisit the use of SL.S and SPS single-level optimization without the additional interpolation condition that is typically assumed in prior works. For such settings, we investigate new variants of SLS and SPS that improve upon existing suggestions in the literature and are simpler to implement. Importantly, these two variants can seen as special instances of general family of methods with an envelope-type step-size. This unified envelope strategy allows for the extension the algorithms and their convergence guarantees to BO settings. Finally, our extensive experiments demonstrate that the new algorithms,, which available in both SGD and Adam versions, can find large learning rates with minimal tuning and converge faster than corresponding vanilla SGD Adam BO algorithms that require fine-tuning.
Introduction
Bi-level optimization (BO) has found its applications in various fields of machine learning such
as hyperparameter optimization [14 17 30 40). adversarial training (51), data distillation [2] 53).
neural architecture search [28 39 neural-network pruning (52), and meta-learning [13 37
Specifically, BO is used widely for problems that exhibit a hierarchical structure of the following form:
min F(x) = Ex zEX
s.t.
y²(x) = argmin (g(,, yi v)].
(I)
wEY
Here, the solution to the lower-level objective becomes the input to the upper-level objective f. and in (T) the upper-level variable is fixed when optimizing the lower-level variable y. To solve such bi-level problems using maddient-basee methods requires computing the hypergradient of F, which based on the chain rule is given as [15]:
VF(x) = VnJ(I, y² (x)) Vayga,, ( V y' (V,
(x))
In practice, the closed-fome form solution (xx can be difficult to obtain, and one strategy is to run few steps of (stochastic) gradient descent on g with respect to y to get an approximation ÿ, and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

use y in places of (x). We denote the stochastic hypergradient based on ÿ as hy B) and the stochastic gradient of g with respect to y as hg. This leads to a general gradient- based framework for solving bi-level optimization [5, 19 4) SGD on y with step size B. y + hypergradient:
At each iteration k, run T (can be one or more) steps of y h.t 3 then run one step on z using the approximated
x² ah (x" y where y² y..
Based on this framework, a series of stochastic algorithms have been developed to achieve the optimal or near-optimal rate of their deterministic counterparts 77 8. These algorithms can be broadly divided into single-loop (I' = 1) or double-loop (I' > -1) categories
23
Unlike minimizing the single-level finite-sum (convex) problem
Vatcanton Loes
N Σ f(())
F(c) = min DEC N
(4)
where only one learning rate is involved when using SGD, bi-level optimization involves tuning both the lower and upper-level learning rates (5 and a respectively). This poses significant challenge due to the potential correlation between these learning rates [19]. Thus, observed in Figure I algorithm divergence can occur when either a or ,3 is large. While there is
Upper Iterations
Upper Berations
Figure 1: Results based eypee-representatioo learning task (see Sec 4 for details). Validation loss against upper-level iterations for different values of (left, = 0.005) and (right, /3 = 0.01). Unless carefully tuned, vanilla SGD--basdd methods for BO are very unstable.
considerable literature achieving faster rates in bi-level optimization 24 8. only few studies have focused on stabilizing its training and automating the tuning of a and 3
This work addresses the question: Is possible to utilize large a and without manual tuning? In doing so, explore the use of stochastic adaptive-step size methods, namely stochastic Polyak step size (SPS) and stochastic line search (SLS), which utilize gradient information to adjust the learning rate each iteration 44 22)] These methods have been demonstrated to perform well in interpolation settings with strong convergence guarantees [44] 29). However, applying them to bi-level optimization (BO) introduces significant challenges, as follows. BO requires tuning two correlated learning rates (for lower and upper-level). The bias in the stochastic approximation of the hypergradient complicates the practical performance and convergence analysis of SLS and SPS. Other algorithmic challenges arise for both algorithms. For SLS, verifying the stochastic Armijo condition at the upper-level involves evaluating the objective at new (ar, y (a:) pair, while y (a) is only approximately known; For SPS, most existing variants guarantee good performance only in interpolating settings, which are typically not satisfied for the upper-level objective in BO (22). Before presenting our solutions to the challenges above in See 2 we first review the most closely related literature.
1.1 Related Work
Gradient-Basse Bi-level Optimization
Penalty or gradient-based approaches have been used for
45 21 Here focus our discussions on stochastic gradient-based methods as they are closely related to this work. For double-loop algorithms, an early work (BSA) by Ghadimi and Wang [15] has derived the sample complexity of o in achieving an e-stationary point to be O)) but require the number of lower-level steps to satisfy T O(E 1)e Using a warm start strategy (stocBiO), Ji al. [22] removed this requirement on T.. However, to achieve the same sample complexity, the batch size of stocBiO grows as O(c-1). Chen et al. 4 removed both requirements on T and batch size by using the smoothness properties of y" (x) and setting the step sizes a and 3 at the same scale. For single-loop algorithms, a pioneering work by Hong et al. [19 gave a sample complexity of O(e -2.5), provided ar and 3 are on two different scales (TTSA). By making corrections to the variable update (STABLE), Chen et al. 5 improved the rate to O(e -2). However, extra matrix projections required by STABLE can incur high computation
solving bi-level optimization problems IT
cost 5 4. By incorporating momentum into the updates of and y (SUSTAIN). Khanduri et al.

---

100
10.
201
Ganeper Mevi
Oboccee
1e-1
10-4
Serntions 230
206
500
3030
Figure 2: Experiments on quadratic functions adapted from 229 The objective is the sum of two- dimensional functions Si ((r x²)² H, =f), where H; is positive definite and i 1,2 (see Appendix B for more details). From left to right, we show: the objective value, distance to optimum, step size, and iterate trajectories.
24 further improved the rate to O 6 Besides these single or double-loop algorithms, a series of works have drawn ideas from variance reduction to achieve faster convergence rates for BO. For example, Yang et al. [4) designed the VRBO algorithm based on SPIDER [12]. Dagréou al. 7 H designed the SABA and SRBA algorithms based on SAGA and SARAH respectively, and
demonstrate that they can achieve the optimal rate of (( ()) 9 35
Huang et al. 20 proposes to
use Adam-type step sizes in BO. However, it introduces three sequences of learning rates (ak, (kk,Bkk17 m)) that require tuning, which limits its practical usage. To our knowledge, none of these works have explicitly addressed the fundamental problem of how to select a and in bi-level optimization. In this work, we focus on the alternating SGD framework (T can be 1 or larger), and design efficient algorithms that find large a and B without tuning, while ensuring the stability of training.
Adaptive Step Size Adaptive step-size such as Adam has found great success in modern machine learning, and different variants have been pro- posed (25 38 47 31 32). Here, we limit our dis- cussions two adaptive step sizes that are most relevant to this work. The Armijo line search is classic way for finding step sizes for gradient descent 48 Vaswani et al. the stochastic setting (SLS) and demonstrates that the algorithm works well with minimal tuning re- quired under interpolation, where the model fits the data perfectly. This method is adaptive to local smoothness of the objective, which typically difficult to predict priori. However, the theo- retical guarantee of SLS in the non-interpolating regime is lacking. In fact, the results in Figure 3 suggest that SLS can perform poorly for convex losses when interpolation is not satisfied. Besides SLS, another adaptive method derived from the Polyak step size is proposed by Loizou et al. (29 with the name stochastic Polyak step size (SPS). Loizou et al. (29) further places an upper bound on the step size resulting in the SPSmax variant.
Algorithm 1 BiSLS
Input: x0, x..80. ,K T. 5, 0b,u. S0,0. n, w E (0, 1)
Output:
1: for
0, b....:K K - do
2:
y 0.0 y
3:
for 0, 0, ..... T do
44 extends to
4:
Sh reset(3, Bb,o. 17. opt)
Algorithm
5:
B line-search based on start-
ing from P
y gkit+1 yht hh.t
7: end for
y p++1 = -IT n²: ghttl xh1
9:
+- reset(a, Cb,u. n, opt)
10: while (14) based on (#*, gh+,, a. 8)
does not hold. do
11:
a *
12:
* x
(a ,aat,y"tt ybt1) or
13:
2b = kkk - -AA te (xt (otkty yltl)
14:
g++1 ==l==0 g - B ( yet))
15:
end while
16: xd+1 x a a
Similar to SLS, the algorithm performs well when the model is over- poee-paramttrieed Without interpo- lation, the algorithm converges to a neighborhood of the solution whose size depends on this upper bound.
17: end for
In a later work, Orvieto et al. (36) make the SPS converge to the exact solution by ensuring the step size and its upper bound are both non-increasing (DecSPS) ). However, enforcing monotonicity may result in the step size being smaller than decaying-step SGD and losing the adaptive features of
SPS (see Figure 3) In this work, we propose new versions of SL.S and SPS that not require monotonicity and extend them into the alternating SGD bi-level optimization framework B
3

---

075
540
17-
0250
10
Step
K0.
Hoor 2l00n
Barstion
(a) Minimum train loss vs. 76.0
(b) Train loss vs. iterations
(c) Step size vs. iterations
Figure 3: Binary linear classification on w8a dataset using logistic loss (3. Minimum train loss of decaying-step SGD and SPSB for different "6,0 ss. (b)(c) Train loss and step size against iterations, respectively. We choose с = 1 and ė = 1 for SPS and SLS respectively;
= vk + for for SLSB ; 78, vK+I
DecSPS c = and "6.6 IKTI for SPSB ē 0.1 and "b.A -
76.0
for decaying-ster step SGD. For (b) and (c), we set %6,0 = 1000 for all algorithms.
2 Summary of Contributions
We discuss our main contributions in this section, which is organized follows. First, we discuss our variants of SPS and SLS, and unify them under the umbrella of "envelope-type step-size". Then, we extend the envelope-type step size to the bi-level setting. Finally, we discuss our bi-level line-search algorithms based on Adam and SGD.
Converging SPSB and SLSB by Envelope Approach We first propose simple variants of SLS and SPS that converge in the non-interpolating setting while not requiring the step size to be monotonic. To this end, we introduce a new stochastic Polyak step size (SPSB). For comparison, we also recall the step-sizees of SPSmax and DecSPS For all methods, the iterate updates are given as Ik+1 2g 7% fa. (x*) where ig sampled uniformly from [n] {I....,1) n2 each iteration The step-sizes Th are then defined as follows:
(a
fi 7o.
SPS mAX
29
7k = min!
(5)
(r+)
1
fir (x** -
DecSPS 36
7o & 7 min
V (a**)] 17-11
4k:
(6)
Sú, (1*
li=
SPSB (ours):
min(
fig (x+*)]1 }
fy (x0)))
where fr = inf, fi(x), increasing, and 17 S f? is any lower bound.
min [ (x 14 %b.o) C₁ is non-decreasing, Y6 is non-
Unlike SPS in which 78.0 is a constant, our upper bound 7b.k is non-increasing. Also, unlike DecSPS in which both the step size and the upper bound are non-increasing (this because 7hk S G-1 0--1%-1 7-- and min Dehmae <0'0.0 } S 7 < Cu7a.o [36] Lemma IJ). we simplify the recursive
structure and do not require the step-size to be monotonic. As we empirically observe Figure 3. the step size of DecSPS is similar to that of decaying SGD and in fact can be much smaller. Interestingly, the resulting performance of DecSPS is worse than SPS despite SPS eventually becoming unstable once the iterates get closer to the neighborhood naturally behaves erratically. This is not unexpected due to small gradient norms (note the division by gradient-nome (5)) and dissimilarity between samples in the non-interpolating scenario. Moreover, note that the adaptivity of SPS in the early stage seems to be lost in DecSPS due to the monotonicity of the latter. On the other hand, SPSB not only takes advantage of the large SPS steps that leads to fast convergence, but also stays regularized due to the non- con-inceeasing upper bound 78.6 in (19). These observations are further supported by the experiments on quadratic functions given in Figure
solution and the step-size
2 where we observe the fast convergence of SPSB and the instability of SPS Furthermore,
SPSB is significantly more robust to the choice of 7h, than decaying-step SGD as shown by Figure 3a Motivated by the good practical performance of SPSB take similar approach for SLS. The

---

SLS proposed and analyzed by Vaswani et al. 44 starts with 76,0 and in each iteration ls finds the largest Nis S 76,0 that satisfies:
fig (ax The f., S fu (zx) - c- 7 VV. (xx)))
<<ē<l.
(8)
To ensure its convergence without interpolation, we replace "8,0 with appropriate non-increasing sequence kb We name this variant of SLS as SLSB Interestingly, the empirical performance and step size of SLSB are similar to those of SPSB (see Figure B). This can be explained by observing that the step sizes of SPSB and SLSB share similar envelope structures, as follows (see Lemma Appendix A):
Su (x+) 1/
SPSB : min
70,b} S 7kk = min
clV. (x+)] 7b,s), 0ce,
2eLmax
2(1 c 7b.k S 7h S min
fi (x*) - 1/2 fi, (=+)] To,k), 0 0<E<1.
SLSB: :
m T.max
Therefore, we unify their analysis based on the following generic envelope-type step size:
7 = min max(", }. 70.47, n. = min(w) 7b.kh
(9)
where w > 0, 7o.k is non non-increasing and i satisfies N1 == min To S 5h S To We show that this envelope-type step size converges at rate O 1) and O ( for convex and strongly-convex losses respectively.
VK
Envelope Step Size for Bi-level Optimization (BiSPS) We extend the use of envelope-type step sizes to the bi-level setting. The step sizes for upper and lower-level objectives of our general envelope-type method are:
Algorithm reset
Input: p. q. 1j 2
opt
Upper: ag
min maaxfau, ) 06,kk hence 01 S āg S Lb,b (10)
Output: p
Lower: BE. min { g(a", hh: - g(* vit,s:))
I: if opt then p
piVog(at, y ) ,b,,k) AI,
(11)
else if opt 2 then
where Vy+,yp is the minimizer of the function g(* : v), and CI,A, 0b,k, and S5.e are three non-increasing seeuueeesnssequunessss Note that Bo, is fixed over the lower- level iterations for a given kt therefore this equivalent to running steps of SPS to minimize the function g at each upper iteration k. However, the decrease in the upper bound fo, with & is crucial to guarantee the overall convergence of the algorithm (see Theorem 3). Starting from the general step-size rules in (T0) and (T). our bi-level extension of SPS (BiSPS) follows by setting ag in the form of SPS computed using stochastic hypergradient h4. That is,
5: else if opt = then
5
end if
f(x*, t 0) -1- ((
01,0
0bD0
0%
111
O1
Vk
Ob&
Vk
(12)
where 0n.0 S 08.0 and +1o)) is lower bound for inf [xx ++:; For computing hy.
can take similar approach previous works [1]
19 4 that a Neumann series approximation
N
h = Vaf( ; Vegg(a* , vb)
II [1 -
-
Aygla ++1 yf y o),
L
(13)
where N is sampled uniformly from [N] and N is the total number of samples. For BiSPS, we use the same sample for f(**, ,y*++; Φ) and Vzf , +++1:)) when evaluating o in (12) Interestingly, we also empirically observe that using independent samples for computing ãg and hy results in similar performance using the same sample. The optimal rate of SGD for non-convex bi-level optimization is O( without a growing batch size We show that BiSPS can obtain the same rate (see Theorem by taking the envelope-type step-size of the form TT) and (T]. We implement BiSPS according to 12p and observe that it has better performances over decaying-step SGD with less variations across different values of oo.o (see Figure 4 and note that decaying-step SGD is of the
form 06.0
vk+1
5

---

225
19-
A
243
Validation Loes
125
Upper Step Size
Lower Step Size
125
La
625
625
10k
2000
Upper Iterations
Upper Iterations
(a) Validation Loss
(b) Upper-level step sizes
(c) Lower-level step sizes
Figure 5: Results on hyper-repreesenation learning task (see Sec for details). (a) Validation loss against upper-level iterations for comparing BiSLS-Adam/SGD to fine-tuned Adam/SGD. (b)(c) Upper (left) and lower-level (right) learning rates found by BiSL For the fine-tuned Adam, the optimal lower and upper-level learning rates are (1) and O(10 respectively. BiSLS-Adam outperforms fine-tuned Adam/SGD with starting point that 5 orders of magnitude larger than the optimal step size.
Stochastic Line-Search Algorithms for Bi-level Optimization The challenge of extending SLS to bi-level optimization is rooted in the term y (zr). In fact, we realize that some of the bi-level objectives are of the form F(x) = fly (x)). That is, f does not have an explicit dependence on x in the data hyper-cleaning task [22]. This implies that when SLS takes a potential step ær the approximation of y (x) (i.e, ū(z)) also needs to be updated, otherwise there is no change in function values. Moreover, the use of approximation ((x) and the stochastic estimation error in hypergradient
would not gaurantee a step size can be always found. To this end, we modify the Armijo line-search rule be:
f(x² - -a,h githtygttii (x - anht)) S f(a", y x ) - pa 11//111112 + 5, BiSLS-Adam. (a=--xzAp Ar 1 getll A (nAi)) S sa v , pork 1/,11,,,
BiSLS-SGD
5, (14)
where p, 5 and As is a positive definite matrix such that A GR.
Valitaatoon Loss
vostdattinn Loos
Similar the single-level Adam case, the matrix Gk in the bi-level setting defined as Gg (
(22 diag(h" 7 () 3/) 25 43
Moreover, BiSLS-Adas takes the fol- lowing steps for updating the variable I: x++ x Ax mm where ++ 3im (1 - 3.) The details are given in Algorithms and 2] We denote the search starting point for the upper-level as OB. at itera- tion k. and denote it as fh at step within iteration & for the lower-level. We remark the following key benefits of resetting ab,e and & (by using Algorithm 2 to larger values with reference to ag and S (re- spectively) at each step: (1) we avoid always searching from 0b,0 or 66.0= thus reducing computation cost and (2) preserving overall non-increasing (not necessarily monotonic) trend for 0& and 9h, (improving training stability). We found that different values of all give good empirical performances (see Appendix B). The key algorithmic challenge we are facing that during the backtracking process, for any candidate oge, we need to compute g* := x² axhh and approximate y ( with g"+1 (see Algorithm [T). To limit the cost induced by this nested loop, we limit the number of steps to obtain f++ be 1.
Upper Iterations
Uppar Marations
SOYS BIGSS
10.0
199
Docay SLD 50.
Decay SCD 200.0
Figure Results on data distillation experiments adapted from Lorraine et al. (30) (see See 4 for details). We compare BiSPS and decaying-ster SGD for different values of as,o where Hessian inverse in (2) is computed based on the Iden- tity matrix (left) or Neumann series (right). The lower-level learning rate is fixed at 10-4.
Moreover, 8 in (4p plays the role of a safeguard that ensures step size can found. We set to be small to avoid finding unrealistically large learning rates while tolerating some error in the

---

hypergradient estimation (see Appendix B for experiments on the sensitivity of 6). In practice, we found that simply setting 8 works well. In Figure Sa we observe that BiSLS-Adam outperforms fine-tuned Adam or SGD. Surprisingly, its training is stable even when the search starting point 0l6,0 is 5 orders of magnitude larger than a fine-tuned learning rate (O)10-4)) Importantly, BiSLS-Adam finds large upper and lower-level learning rates in early phase (see Figure 56 Scp for different values of 0, and $b.0 that span 3 orders of magnitudes. Interestingly, the learning rates naturally decay with training (also see Figure and 6d). In essence, BiSLS is a truly adaptive (no knowledge of initialization required) and robust (different initialization works) method that finds large and without tuning. In the next section, we give the convergence results of the envelope-type step size.
3 Convergence Results
3.1 Envelope-type step size for single-level optimization
We first state the assumptions, which are standard in the literature, that will be used for analyzing single-level problems. Assumption i on the Lipschitz continuity of f and fi in Problem 4
The individual function Ji is convex and Le-mooth such that [[V - Vi(('') S functiion Lillæ æ'11, Vi, Vx E dom f and the overall function f is L-smooth. We denote Lmax 2 max; Li- Furthermore, we assume there exists 1 such that 1 S ft inf, fx(x), Vi, and lower bounded by f obtained by some x² such that f = f(x").
Assumption 1.
The following bounded gradient assumption is also used in the analysis of convex problems
33
Assumption 2. There exists G > 0 such that V (z))l < G, Vi.
We first state the theorem for the envelope-type step size defined in (9) for convex functions.
Theorem 1. Suppose Assumption 7 2
hold, each I' is convex, C = dom f, 7Kk is independent of Then, the envelope-tyy step size in g achieves the
the sample fx(z²) and choose Po following rate,
%6.0 Vk+1
1000 - xt
log(K) (og(K))
B[s(a*) [(x'))
2 K-1 K
2
where K- = min(w, 20 and x=K F Ek xt VK)
We were not able give convergence result that uses the same sample for computing the step size and the gradient. However, we empirically observe that the performance is similar when using either one or two independent samples per iteration (see Figure 2 and Appendix B). When two independent
samples is and j& are used per iteration, the first computes the gradient sample V f. (I*), and the
fox (1 )
other computes the step-size 7h- For example, for SPSB this gives 7 min
cu V 11 7.,)-
This type of assumption has been used in several other works for analyzing adaptive step sizes 29] Under this assumption, we specialize the results of Theorem I SPSB and SLSB 27 44
where " = min zeLi 28.0 } and - = min 2(1-2) 25.0
Lyao <K respectively. Concretely, for achieve the following rate: (I f(x |00-='1 + 70.0 log(K) Next, we state the result for the envelop-type step 2To.oVK
K 2 18.0 maxx SLSB and SPSB with No vk41
20.0 and c
2/K
size when f is u-strongly convex.
Theorem 2. Suppose a p-strongly convex function f satisfying Assumptions I Nand 2 assume C is closed and convex set, and "/n independent of the sample V (2*). Then an envelope-type step size in 99) with To,k
7b.0 K+I 76,0 2 t. and wi < achieves the following rate
uko
(e komw |2o x x²122 + +20000 + G2 log K
B[f(Ex) - f(x" S 2(K - ko)
2(K - ko)
where FK 1 K- 2 and Ko max(1, |n0,o/wl 11. k- Ek=
7

---

We can again apply the result of Theorem to SPSB and SLSB with Yo
k+1
28,0
76.0
2 1
w = 1/ Lmaxs and c c=č= 1 to get an explicit rate: [ā]((x)) - 112 + G2, + mo. log K where ho- max(1, Lm.x 17. 2(K-ku)
100--f((a f(x*)()))))))) S 2[ Tik-ko)
pkko
e Emaax
100
Remark 1. Under the envelop-type step size frumework and the assumption of two independent samples, SLSB and SPSB share the same convergence rates of O (RR and O as SGD with decaying step-size for convex and strongly-convex losses respectively. For the latter, a projection operation is required to stay in the closed and convex set C. These rales are not surprising because of the structure of the envelope step-size in ( Indeed, the proof is similar to the standard proof of analogous rate for SGD with decaying step-size. Nonetheless, we include it here for completeness.
3.2 Envelope-type step size for bi-level optimization
We start with recalling standard assumptions in BO 22
19 L5 4. We denote = = [z: yl and recall
the bi-level problem in ( The first assumption is the lower-level objective g.
Assumption 3. The function g(x, [r, v) is Bg strongly convex in y for any given x. Morcover, Vg is Lipschitz continuous: [V (0((1111))) v1) ) Vg(r2, y2)]l || S - =2 falso assume that this holds true for each functionn g( y: 1)), and V g Lipschitz continuous: Il (V2g(13, 11) 4 V y2)l I La 21 22|1. We further assume that [ 1y v) I Cg. and the condition number is defined as K Lu
Next, we state the assumptions the upper objective f. Assumption 4. The function J and its gradients are Lipschitz continuous. That is: [11, v1) f(2. y2l L L1 - 22ll and , v)ll < Cy.
(f S L 22ll. We also assume that
Furthermore, we make the following standard assumptions on the estimates of V,, Vg. and V2g. Assumption 5. The stochastic gradients are unbiased: [o y Ø)] = Vf(z,
Ev[Vg(z yi } = Vg(a, y), and E. | (z, y: b)] = V g2, v). The variances of (z),z))
and V gxz yi v are bounded: folll - f y) 1) S 0f and Eg [VVV v)
(= y) | S oz
Finally, we introduce the bounded optimal function value assumption in (5). which is used specifi- cally for analyzing step size of the form III in the bi-level setting:
y [9(2, 8 (x); + - g(x, Vi ii +0 S og Vz,
(15)
B (2( v) V Vyg(z, y: 6) o Vx,
(16)
where y" (x) = min, g(a; y) and Vi min, g(x, y; 3 for a given x (recall that at any iteration k. the lower-level steps in BiSPS are SPS with an upper bound Bo,A: furthermore, fo. is non- increasing w.r.t. upper iteration k). The one- one-variable analogous assumption of (15) has been used in the analysis of SPSmax 29 Here, we extend it to a two-variable function. Unlike the bounded variance assumption (6). which needs to hold true for all x and y. we require (15) to hold at y (2)
for any given v. As mentioned previously, the closed form solution y (x) is difficult to obtain. Thus, we define the following ex expression by replacing y² (xx) with in (
Vi( v) V v) V Vayg(( v) 3y (2, v) V, (x,
(17)
A stochastic Neumann series in approximates (7) with x and y being x² and + (respectively).
also recall that + is an approximation of y" yx by running T lower-level SGD steps to minimize g w.r.t. y for fixed zt Based on Assumptions
and 5 we have the following results to
LF =1 - x2l1. [ly" (x1) y (x2)) < V ff v)ll < Ly (z) all. Furthermore, the bias in the stochastic hypergradient in (3) (denoted as B) decays exponentially with N and its variance is
be used in the analysis [5]: [VF(1)
Lyyl= - æ211. and [ y² (x)
bounded, i.e. E E S 0f (see Appendix A for details) [9].
Now, we state main theorem based on step size of the form
10 and
8

---

(a) Validation Loss
(b) Validation Accuracy
(c) Different 066
(d) Different So,0
Figure 6: Validation loss (a) and accuracy (b) against iterations. (a) Comparisons between whether
to use not use lene-search at the upper lower level: (b) Generalization performance of BiSLS- Adam/SGD and fine-tuned Adam/SGD; (c) Validation loss against iterations for different values of 06,0 (Bo.o fixed at 100). (d) Same plot (c) but for different values of $6,0 (as.o fixed at 10).
Theorem 3. Suppose and g satisfy Assumptions and learning-rate upper bounds 0b,k
.r. au.0 and 0i,k = vk+1 with on,o and 01,0 satisfying Le+4rg Z cñ.a and 0q,9 S 00s,0- Further Vk+i
an.0
assume that og is independent of the stochastic hypergradient hýy, and each sampled function
g(Ø, y: v) is convex. Then under the Assumption (15) with p 2.2 Cs minl kb,kk] }. T 2 00
(on(1-1,CC 1); and Bo,k
80,0 k+1
BiSPS achieves the rate:
Σ K
1
K-1 ((())()
Ō VK
22 log K
(18)
VK
Remark 2.
We further give the convergence result under the bounded variance assumption 16 in
Appendix A. TheoremB shows that BiSPS matches the optimal rate of SGD up to a logarithmic factor without growing batch size. We notice that the assumption (13) largely simplifies the expression on and does not require an explicit upper bound on $1.0- As in the single-level case, whether using one sample or two samples (which makes upper-level step-size independent of gradient) gives similar empirical performances (see Appendix B). Note that the independence assumption is only needed for the upper-level. Thus, the two-sample requirement of theorem does not apply to the lower-level problem. This is useful from computational standpoint as typical bi-level algorithms run multiple lower-level updates for each upper-level iteration.
4 Additional Hyper-Representttion and Data Distillation Experiments
reppetrrppessnttttion learning: The experiments are performed on MNIST dataset using LeNet
26 [2). We use conjugate gradient method for solving system of equations when computing the hypergradient (17). The upper and lower-level objectives are to optimize the embedding layers and the classifier (i.c. the last layer of the neural net), respectively (see Appendix B for details). For constant-
step SGD and Adam, we tune the lower-level learning rate 3 E {10.0, 5.0, 1.0, 0.5, 0.1, 0.05, 0.01 For the upper-level learning rate, we tune a E {0.001, 0.0025, 0.005. 0.01, 0.05, 0.13 for SGD, and (10-1,5- 10-5 10 10-4-- 5 10 10-4 0.001, 0.01} } for Adam (recall that 8 in (14) is set to 0). Based on the results of Figure o we make the following key observations: ① line-search at the upper-level is essential for achieving the optimal performance (Figure 6a) 2 BiSLSSAdam/SSC
not only converges fast but also generalizes well (Figure @ BiSI A.T.S-Aaamln dam/SGD highly robust to search starting points co.0 and Bo.0 (Figure 6c| 6d). It addresses the fundamental question of how to tune a and in bi-level optimization (sec Appendix for additional results on search cost).
Search cost and run-time comparison: The search cost of reset option in Algorithm for BiSLS-SGD and BiSLS-Adan is 89 + 15 and 115 + 16 per iteration, respectively, measured in the number of condition-checking via (14). These costs are significantly reduced when option is used. Concretely, Figure (7b suggests that choosing of (14) per iteration for both BiSLS-Adam and SGD. Choosing 1j = 1 in reset option equivalent to reset option 2, which further cuts down the cost to 4. However, this choice forces the learning rate to be monotonicallyydecren.
2 in option results in ~ 9 evaluations
which leads to a slower convergence compared to other 7's (sce Appendix B for more details). Besides this, Figure 7 shows that single step for

---

Adam
304
Apperslmate '00
CC Stuee
(a) Approximation of yf (x))
(b) Search cost
(c) Run time
Figure 7: (a) Validation accuracy and time (in seconds) against different number of gradient steps for approximating y y²(x) in (14). (b) Search cost (i.e. number of evaluations of (14) per iteration) against different 7j's for reset option 3 in Algorithm (c) Run time (in seconds) of BiSLS-Adam and fine-tuned Adam to reach 85% validation accuracy against different number of conjugate gradient steps for computing the hypergradient.
Viltttioo
200
Upeer Rorktor
Upeet Rerccon
(a) Neumann
(b) Identity
(c) Distilled MNIST Images
Figure 8: (a)(b): Comparison between BiSLS-SGD and Adam/SGD for Data Distillation on MNIST dataset. Validation loss plotted against iterations. (a) Hypergradient computed using Neumann series; (b) Inverse Hessian in (2) treated as the Identity [30] when computing the hypergradient; (c) Distilled MNIST images after 3000 iterations of BiSLS-SGD.
approximating the (²:) in (14) is sufficient, considering the trade-off between performance gain and extra computation overhead introduced. Most importantly, BiSPS-Adam takes less time reach threshold test accuracy than fine-tuned Adam (Figure 7c due suitable (and potentially large) Adam).
learning rate found using (4) (note that Figure 7c excludes the cost of tuning the learning rate of
The goal of data distillation generate small set of synthetic data from an original dataset that preserves the performance of model when trained using the generated data We adapted the experiment set up from Lorraine al. (30] to distill MNIST digits. We present the results in Figure 8 where we observe that BiSLS-SGD converges significantly faster than fine-tuned Adam or SGD, and generate realistic MNIST images (see Appendix B for more results).
Data distillation:
46 50).
Conclusion
In this work, we have given simple alternatives to SLS and SPS that show good empirical performance in non-interpolating scenario without requiring the step size to be monotonic. We unify their analysis based simplified envelope-tyr step size, and extend the analysis to the bi-level setting while designing a SPS-based bi-level algorithm. In the end, we propose bi-level line-search algorithm BiSLS-Adam/SE that is empirically truly robust and adaptive learning rate initialization. Our work opens several possible future directions. Given the superior performance BiSLS, we prioritize an analysis of its convergence rates. The difficulty stems from: (a) the bias in hypergradient estimation; (b) the dual updates in v and y (x) (incurring nested loop structures); (c) the error in estimating y (x)) remark
important direction to relax the two-sample assumption on SPSB /SLSB... Ultimately, we hope to promote further research on bi-level optimization algorithms with minimal tuning.
On single-level optimization,
10

---

This work is funded partially by the NSERC Discovery Grant RGPIN-2021- 03677, the NSERC Discovery Grant RGPIN-2022-03669, and the Canada CIFAR Al Chair Program.
Acknowledgement
References
[1] Amir Beck. First-order methods in optimization. SIAM, 2017.
[2] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 33: 14879-14890, 2020.
[3] Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 2011.
[4] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems, 2021.
[5] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A finle-ttiescale method for stochastic bilevel optimization, 2022.
[6] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd, 2020.
[7] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. framework for bilevel optimization that enables stochastic and global variance reduction algorithms, 2022.
[8] Mathieu Dagréou, Thomas Moreau, Samuel Vaiter, and Pierre Ablin. A lower bound and near-optimal algorithm for bilevel empirical risk minimization, 2023.
[9] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: fast incremental gradient method with support for non-strongly convex composite objectives, 2014.
[10] James E Falk and Jiming Liu. On bilevel programming, part i: general nonlinear cases. Mathematical Programming. 70:47-72, 1995.
[11] Chen Fan, Parikshit Ram, and Sijia Liu. Sign-maml Efficient model-agnostic meta-learning by signsgd, 2021.
[12] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator, 2018.
[13] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks, 2017.
[14] Luca Franceschi, Michele Donini. Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization, 2017.
[15] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. 2018.
[16] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International conference on machine learning, pages 5200-5209. PMLR, 2019.
[17] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation, 2020.
[18] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Convergence properties of stochastic hypergradients, 2021.
[19] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic, 2022.
[20] Feihu Huang, Junyi Li, and Shangqian Gao. Biadam: Fast adaptive bilevel optimization methods, 2023.
[21] Yo Ishizuka and Eitaro Aiyoshi. Double penalty method for bilevel optimization problems. Annals of Operations Research, 34(1):73-88, 1992.
[22] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design, 2021.
[23] Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops, 2022.

---

[24] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. near-optimal algorithm for stochastic bilevel optimization via
2021. [25] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXivv1412.69880, 2014.
[26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227-2333 1998.
[27] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes, 2019.
[28] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, 2019.
(29] Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence, 2021.
[30] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[31] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019.
[32] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate, 2019.
[33] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4): 1574-1609, 2009.
[34] Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[35] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pages 2613-2621 2621. PMLR, 2017.
[36] Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic
polyak stepsizes: Truly adaptive variants and convergence to exact solution, 2022.
[37] Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients, 2019.
[38] Sashank Reddi. Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. 2019.
arXiv preprint
[39] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A comprehensive survey neural architecture search: Challenges and solutions. ACM Computing Surveys (CSUR), 54(4):1-34, 2021.
[40] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[41] Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In Proceedings of the 24th international conference on Machine learning, pages 807-814, 2007.
[42] Daouda Sow, Kaiyi Ji, and Yingbin Liang. On the convergence theory for hessian-free bilevel algorithms, 2022.
[43] Sharan Vaswani, Issam Laradji, Frederik Kunstner, Yi Meng, Mark Schmidt, and Simon Lacoste-Julien. Adaptive gradient methods converge faster with over-parametterzzatoon (but you should do line-search). arXiv preprint arXiv:2006.. 06835, 2020.
[44] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates, 2021.
[45] Luis Vicente, Gilles Savard, and Joaquím Júdice. Descent approaches for quadratic bilevel programming. Journal of optimization theory and applications, 8 81(2):379-395 3999, 1994.
12

---

[46] Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A. Efros, Dataset distillation, 2020.
[47] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes, 2021.
[48] Jorge Nocedal Stephen Wright. Numerical optimization, 2006.
[49] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization, 2021.
[50] Ruonan Yu, Songhua Liu, and Xinchao Wang. Dataset distillation: A comprehensive review,
2023.
[51] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference Machine Learning. pages 26693-2000 20--26712 12. PMLR, 2022.
[52] Yihua Zhang. Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu. Advancing model pruning via bi-level optimization, 2023.
[53] Yongchao Zhou, Ehsan Nezhadarya, and Jimmy Ba. Dataset distillation using neural feature regression. arXiv preprint arXiv:2206.0077 2022.
13

---

A Proofs of Theorems and Additional Convergence Results
A.1 Useful Lemmas
Lemma ! provides more details on the envelope structure of SPSB and SLSB given in (10 and
The lower bound in (19) will also be used in Lemma 5 (for bounding the term Ily y (x*)
Lemma 1. Under the Assumption 7
have the following:
fig (2" 1. To,kh
SPSB :
min 2cLmax
1o S 7x min
cl V fiz (x*) To,k..
0cc.
(19)
min 2(1 - c)
Ai, (a ) 1
SLSB
7b S 7/ S min
To
0<ē<l.
(20)
T.max
S/ [1*)
Proof. The bounds in 199 have been shown
29
36
For 20). the first part of the inequality has
been shown in 44). For the second part, recall the Armijo condition (14)
Stn (Tx 7h Vi, (Ix)) S Ji (1rx) - 7 7x Vi, (mx)) 0<0<1.
We then rearrange this obtain
7k Sug (Tx) - Li (ITA 7n Vii (xR)
f (xL) f
(xx) 1
(21)
Vi (2=)
V (2*)
(x*)]²
where 1" is any lower bound for fü, Also recall that 76.6 is the search starting point at iteration k. hence (20) holds for SLSB.
Lemma 2 gives the expressions for the constants Lp, Ly and L.g. The proof can be found in 15
Lem 2.2T.
Lemma 2. Under Assumptions 3 ladd 4 we have the following:
[V((a)) - FF(x2)) < Ly [| - x2 l|.
11 (I1) - 3" (x2)) 42 x2
[Vf (x)) (f(z,))] S L (x) a11
where
Linigg
L (Lo + LgLa ~ O1x2)
Ly L1,1 +
+
Mg
Mg
1gg
L, Lg -O())
Hy
Lig (Tg +Tg)
(La + Ligia ~ O(w3)
LF = L1a1
Fi
Pg
1ig
Lemma 3 is on the bias and variance of the stochastic hypergradient in (3) which has the following form
N V Myg(a" / (++1));)) (x x==1;
h - V (z ;+) - Voyg(a" "eta(("""""/1/ "
vb0)
T
(22)
Recall that the hypergradient surrogate defined in 17 based on (a+ y is
Vi(a", y x = (a ) + 22 20 h+1 [ g(* ) 'V ptt)). (23)
Given filtration F up to and including 2 and k the bias of the stochastic hypergradient
defined B = V fa & b - FEhh(// and the variance defined as E|IlV b
E[ Lemma 3 has been proven in 19 Lem 1.] (also see [4] Lem 5.1). Lemmas and
will be used in the proofs of Theorems and
14

---

Lemma 3. Under Assumptions 3 and 5 the bias and variance of the stochastic hypergradient hjj satisfy the following
Bias: I yf ) - Biy Flll S CoCs (1
Kg ) Vk.
14g
I.g
Variance: BII I (a" , , 11 | |+111 S 83. vk,
where N is the total number of samples, and 03 = or + [(o] + (o) + +21 + of ~ (KK")
Lemma 4 is on the descent of the quantity Vk: := F F(**) - F(x*) + 111e* y² (x* )l? It will be used
in the proofs of Theorem [3] and +
Lemma 4, Suppose F satisfies Assumptions
and sequences Ob,k
abd vk+i
and 01
Vk+I
25.0 ago
with on.o and on,o satisfying T.+4E,
and on. S 0s.0- Further assume that og is independent
of ht.. Then step sizes of the form (10) and I achieve the following:
Ely S B 01.k
E
(0o, L3 + +2)Bllly y (2+))19
LFa yoy - n (a )[2) Vk,
+ where Vk F(+*) F(x)) + |1 ++ y³ |1 and recall that F is the upper-level loss defined in
B² + (21 2
Bll
(24)
Proof. We denote [| = - By the smoothhhsss of the objective F:
LF
1(a S Fx**) + (VF(x*), x x²) +
I| k+1 - x 112
2
Take expectation conditioned on a filtration of past iterates F% (up to and include x², +)
LF
B[F(> | s F(**) + ([ tht
xx 1
Bllla - x* 1111//1
2
Bi
= F(**) - Ea V
Bilin - bo + h 11 F
2
(a) F(x*) - Blax
L
E 2
|1A511 + El Fxl 03
2
E Elaxk
F 1
F' 2
F((t)
|n5]12
|FF('*) - nř1
2
2
LF
2
where (a) is by the assumption that ag independent of hy. Then expand the term [VF(z*) h111 as follows:
|VF(*)) - h²y12 = [|F((=** - ff(at, , V f(z* y - h
< <2IVF((*>) vs(at, + + 2 / ((x , - 1/2112
2T, |10 +1 - (x**) )|2 + 2B².
where (b) is by Lemma 2 and Substituting this into the above:
Elax| |VF 012 Elau| FA
Lr Frd] |1,511+++
E EF [FA] & )(a*)
|
+
2
2
Tr R+1 y² (1* 112 ElaulFilB2
I.
Elau| 113 11y
03
2
(c)
3 F(**)
al. |VF(=>)) ||
01, 1117111
I I b.k
11,/112+
2
2
I
00.L3311 y¹ (2* )1² + B² +
2 0g.
15

---

where (c) is by a1 S ag and 0b, 2 ap. Then take total expectations and subtract F(x"):
S[F(z*+))-F(C - < B[F(=*) - F(x")]
01K E VF
Ol
Bilki
E
E|| 84
11+
2
2
2
L
0b 00 1 ++1 -1- (1²)) + ab +
09
(25)
2
Now define the potential function v/ := F(**) - F(x*) + 11 - y" (2 and expand the
term [ly y² [1 as follows:
11y 1 y (x 1x* 1|1 = |1 y²(x") + +
- y0 111 + 2
I 2 2 h+ +2 (x²) - y (2
(4)
S 2 g h+1 (2(²²*
- 2211 - -hy
= 2 -21y k+1 - -
-
-hl++ + ky1l,
where (d) is by Lemma 2
Take expectation conditioned on J/:
Blly y² (a k+
k+1 s 1a--1-y-(a "0(x²))
s 2
2 + +
S 2111 h+l - (1+)))]] +1
Then, take total expectations:
Ellly - y² (xx (a ||3] s *+1 y - + +22))))22222244111 +
(26)
Now, based on the definition of V and combining 25 and (26)
E|V++1 E[F(x*) F(x")] 01, E[| B[|
2
111
2 (aLLE Lrag 2 - -12g02xx + (00s 1. + 2)B 1 (x()))
Ob B² + +2T2,00 + Lpak
)0}
2
(e)
( F(x')]
Oik
Bill (1I1
2)Bl1l y² (1
2
Lrab )09
Bb + +22I200
2
ElV4
01. Ell VF (2* )|2 + (as, + 2) k+1 (1+
2
B² B² + (21 + LFa )0y Elll** - y (1),
2
ai. 0n."' where (e) is because 11+1 2
2 (LF + 4L))aox = which guarantees that ar, vK+I
an.
oo (LF + 412))
Lemma 5 and Lemma give two alternatives for bounding the term b1 y (x* Lemma is
based on the assumption [g (x)); 16) g(x Vo x)] S oz Vz. The proof for its one-variable
analogous assumption is given in Loizou al. [291. Here we follow similar approach for the
two-variable function g(æ, v). Lemma 5 will be used in the proof of Theorem 3
Lemma 5. Suppose Assumptions 5 and the bounded optimal function value assumption hold.
Further assume that each sampled function g(,, y, 1) is convex, then step size of form 1 achieves the following:
Ellly k+1 1" 21 s (1 1h Cx, - 2² (1+)) 23. To
where C = min{ 1.
2pL. 3.
16

---

Proof. We denote hgg = V Vor(=" - :b), and Fx, be a filtration up to and including x6 and yh.
We have,
lly lyyt
y¹ (x*))²
=IlyAtt Bri 12 )12
11yAt y¹ (a*x))² 23 (1 11 (x"),,
(1 112h) + 1
(0)
tt 8¹ (x 23 b 3i (x h1 + BR. Lo(o s (b) g(x* 32 ( b6] p
(6)
$ hut 1 00(x")11 11 tet y- (x*), nigh)) + 2Bk 19 yx:²)a)) g(2". Vin wi +)
ll v (z (x²)]] 23, (1 - (x*), 1
19 R nhi v) g( v" v) + g(( V (x v) g(a 32 w . 43]
l1o v (a )1 + 23 1 1y - V (z*), hggh) + g( "/: v/) g(x y (x*) +)
19 (o ) 1) g(0 32 v14
11 y || + 20x 20 V (x*), (x + glæ* ;1: g( y. xx"(x") +)]+
23 1 (b)) g(x*t Vo w:: vi:,,:)))) U)),
where (a) is by Lemma 1 (b) is by choosing 2 1 and, (c) is by individual convexity of 2 g(2, y: v) such that - -yyh yn ) + +ga ;b) g( y (x));)) 0 and recalling that C = minf zpt. L : Bo,1 I Su,e by Lemma Take expectation conditioned on Frr, and note that Elh = Vug(o*, n) Elg(a*, ;b) = g(* s.tt), and Elg(**, yy (x*);: = gl0hh y² (x*)))
hrt1 - y² (x |12 S lighe - yy (2*))) + 20xl - y "²("",),, V Veg(a . +)+ g( (.tt) - gla "² (x*))] + 2B0,
(27)
Now, based on the strong convexity of g w.r.t. y.
-yght 3² (x*), V Vyg(o" ))+ ))> g(a", yhtht g(a") y (a*)) S
Hy |y y-
2
we can further obtain (by taking total expectations of (27 and using strong convexitt:)))::) Elig v (x* 11 < (1 My C1 |E hit v (0+) + 2,3
Solve this recursively from / = 0 to ( = T - 1 (recall T is the total number of lower-level steps,
y = y and gx+1 = )))):
Ellly y |19 s (1- (1 y [1
20 2
Σ (1 kyCWy
1=
s (1 -1000 y (z 17 2,,,
Lemma 6 is based the standard bounded variance assumption Vyg(z, y (=)) < og Va, in the bi-level optimization literature 19 4 Lemma 6 will be used in the proof of Theorem
Eg V ng(2 y (x);
Lemma 6. Suppose Assumptions 5 and the bounded variance assumption 16 hold. Suppose that th p 2 max L. A1., J. 3r,0 S min( 2
Hy Loy,
zugha }. Then step size of the form
2ug 2p5.g-
Ps -b-
Il accieves the following:
Bo.k
21g Lg Bo, EElle - y² (x+))
Ellly++1 - y" (1t))19 S
Cs
Pg Lo
where Cx = mint بptpa 1 B.
17

---

Proof. Similar to the proof of Lemma |] we can start with
llg - y² (x* = 1l - y (x*)) 2, - 32 (x*))* (, + S2, 11ge
Divide both sides by BR,t
|, y (x 11 - 15 (x*t))1
2/ - 1" (x()),, + Se.ellig011
3R,t
BKg
Then use the facts that Be,t S Bo and BRtt 2 Cki
h y² )1 1ly
('(xx)
2(y -- hitt + B 111
Bb.k
Cs
Next, take expectation conditioned on the Filtration Fi,e up to and including x² and yhe
BlllyAtt - (z
Bllly 1/" (x )1 - 2(g - y-((a),,,, Vg(a",u ,
Bo,
Ck
+ Bo, EI|| hn 1 |
C2 Billy
y (z || 1 - 2 - (x*),, Vg(=* ,3
+ Bo E1|l h/g - Vg(=" v(0)) + Vg(e" (12
Ellyy y
- 2(y e - yy (z*), Vg(a*, yh))))
Ck
+ B Bo, Vg(z* y(
where (a) is by the bounded variance assumption 16 Based on strong-convexity of g 34 Theorem 2.1.11], we have
1
E kitt
(1)))1
-/ Ch
Ily
y )2 2ggLg 11 11"h--"((a"")
(=(
Bo,k
Ho + Lu
2
Vg(a" 112 + Bo, + B Vg(l" "oll""""a )²2
Hg Lg
Multiply by fo,s in both sides, group terms, and take total expectations to reach
3 C₂
2 Bb.
El 3² (1+ <
B -y" (1. )
M1 Lg
+ 3o, (Po
Mg + Lg
Bo.k
2g Bo B.)l v |1] E.
My + Lo
where in (b) we have chosen Bo, S Bo,0 < we obtain:
vk. M ,,t Vk. Solving this recursion similar to Lemma 5
2
Bo.k
2pg B).k) Ellly* - (2*)) +
E y" ", <
T3
(28)
Ct Mg Ly
In we require
Ar. 24g Ly Bo,k 2 (recall C = minf 1 2pt.," , Bo, S 3x, S 3b,k), this is ny
min
Ct
Nut
equivalent to Cs S
1 My to In case of Ck = 2pf.," we choose p Z M,t (to avoid contradictions
2rg I.,
we also choose 2
Ho tho,, In case of Cs Bo we choose Bo, S 30.0 - 2p,
Hy+ho
4f.,
We also require
Ba 2ugLe Bo.k $ 1. In case of Cj So this is equivalent to
Ct Moy
2y Bo,b 2 O, which satisfied by all Bo In case of Ce 2pL,
1 we choose fo, S
Hg
3b.0 Σ 2pt., "g bh
Puting everything together, we have p. 2 max{ Py Mothu)
Motha 4h, 3.. and
20gke
ty Lzg 3,,0 I mint bot 2n bo 2pt.g-
200 hg }. Patii
18

---

A.2 Single-level Convex Proofs
A.2.1 Proof of Theorem
The proof of Theorem iss similar to the standard proof of decaying-step SGD (GD) that can be found in e.g. Beck ①. Here, we give the proof for completeness.
| - x²12 - - x², Vfi((*)) + ) || x 112
| -x=xx"" x=11 -)))((((()) -i((=)))) +
|| - x²12 2xx(f((=*) - + G
where (a) is by individual convexity of fi. and (b) is by Assumption 2 Take conditional expectation and assume that T is independent of sample k
(c) I 1xxh x²112 - 112--E((ne El(nl=="((fe - f(x")) + G2
B|||=* k+1 - x 1001
1 x0122 2m f(x')) 2h, G²
where (c) by independence of 7/ and 2², and (d) is because 7i S Tke vk. Take total expectation and rearrange
2 ([[(x*)) - [(x))] S BlIl= x² x²113) Filla x 11 + 02
Using the fact that W,K-1 S M1 wk E [K 1] and set YoRk VK+I obtain
vo k ++
Pr.k-1B[f(r²) - f(x))] s B|||** x01 E1|1 E11 x² 2221 +
G²
Summing over k to k K we obtain
2
K K
B[s(a*) - [(x))]
1 - x01 - -E[| x01
02
1
K
K
K
k ++1
k=
k=0
|100 x01
G log(K)
K
K
Define ã == 1 K
Ex= x apply Jensen's inequality and rearrange
1 x= 1|2
G² log(K)
E[S(**) - -(x=))
+
2 K
2M.
A.3 Proof of Theorem 2
The approach of Theorem 2 is similar to 16 Theorem 3.2]. The crucial difference that the step
size in [16] Theorem 3.2] constant (7k- - for k S 4[s],, whereas for envelope-type step size
it is of the form:
7 min mmax (,,
3, 1o R. min w. 70
where 7 can be (e.g. in the case of SPSB ):
(x+*) 1
h minf
Ck V [2
h
76.0
W
2c Lexx
Jig (a)(a")-1; V., (1)) or k+1 depending on
The proof of Theorem suggests that the step size can be either their magnitudes for k S ko (ko max /7////////// - 1)). After kn iterations, the step size is 70.0 This finding is numerically confirmed by the experimental results in Section B
Theo
7h K+II
19

---

To proceed with the proof, we have:
|| x²12
|| 7h Vf((==)) - =2212
| xx" -27 (V ===(
(0)
S | x² -1 2 V ==
where (a) is because "/k S 78,,, vk. Take conditional expectations
B B||
x=
11 [x*
| x 1| 2 | f(=*) x x²) + 18, (
I
x²11 1 || x x²11 2T (1* - f(x')()))))))) + + G2
IAS
1 x²1' pMn. |1 x² 112 2 (f(*t))) f( ) + n C²
where (b) is by bounded gradients assumption and strong convexity of f- Take total expectation and rearrange
2E[f(x²) - f(xx)] HBIx)
x²1 [1] E El|
x 112
G2
7
Choose kn max /wo/w] }}, then for wk s.t. & ko we have Vv. min min 7b.6 20 K-1 which means nh k+I
Ko,k
tt after ko steps. Within the first kn steps, the step size is
Tk minfw, (o, Hence, for & 2 Ko we have
WML BE[la* x 201131 - E[llx*+ x011
G0
2E[s(x*) f(xx((() -
7c
k +
Now, sum from K = Ko to K 1
K-
K
(1 (OL ) x
x² 1121
E[1 - =21
K-1
G2
2 Σ - - <
71,
h: ++1
k=
k=
k=
(29)
For the first term in 29
call it A, we expand it as
K-1
B1110x x= 11]
A
Elll>*
x= 20113((
11) + E1[l2 - x x=1131(
- (4)
11,
7
K.K-1
+1
k + 1
k
ho + 14)
Bl|l x² (1
4)
+
1[[ [1]]
70
70
70
k=
(d)
B Billz x² 1171
where (d) because "/ we have term
8+1
- 0, V/ and
11 S pko. For the second ku+1 70
to
70
29 call it B, we have
G2
[ K-1
B
S T0G²
dx G0 log(k) - log(ko 1)] S G2 log K
h ++1
x x+1
k=ko
Putting A and B together, we obtain
1
ko - Bll x= 1=112
G2 log K) 2(K - Ko)
(30)
2(K - ko)
Within the first Ko iterations, similarly to the above, we have
E B|| x= |]] S (1 (71,) x=1 2 2n, f(x')] 22 G2
< (1 B|]la x²1
20

---

For the first & S ko- iterations, MA = where wp < 1; thus, we obtain the following
x=1 B|l|a*+| xx S (1 - (w)) - =0= G2.
Solve this recursively,
Ro 1
(1 - (m) Ao k- h 7/
B| | x² x²1|a] S (1 - - - xx
+
(k+ + 1)2
k=0
1o-1
706²
< (1 - 11100 xx" +
(k: + 1)²
k=
pho
I (1 - (1-jaa)bb) |110 - x² 112 + G2
dr
(1+
1
(1 )m)) |10 xx 1| + 10
G²
kn
$ (1 (1-mww)Mollst x= 12 + G0
(31)
Putting this into (3).. we obtain
K 1
Joki
(oxp(-kopw))llz - x²12 + + + G0 log K 2(K ko)
Blf(x*) - f(x))1
K Ko k=
2(K - ko)
Define ãx- = K- 2k=ko
1 K-1 x², then by Jensen's 's inequality we have
puko
(koo--)o - x01 + +z00) + 70 log K 2(K -ko)
E(f(Tk) f(x*)] s 2(K ko)
where Ko max /no//] - 13 and 70 2 +.
A.4
Bi-level Proofs
A.4.1
Proof of Theorem 3
Start with Lemma 4
E B 01K E [[ (00,
+ |11 y² (2**))1
B² + 121202 + Ira j09 - -Ell** s² (z 1P
We substitute the result of Lemma 5 for the expression Bill** y¹ )13)
01
BII + [(a0 13 + 2)(1 Mo C²) - -1 (2
2
+ BB - -2L, + LF وo
200, T 0 +
2
(0)
B
01 E
((00 +2)(1 M, 11)² -11=-1B[[laal 1]B[lb 3/' (11]
Bo T1303 + 48, To, + R² + =(213 + Lr
2 oā
(6) 2 ElV'1
01.k E1l F (x *) [P] 200 3,, T TL303 + 43, TT + a + (2L + Lr 2 oz
2
where (a) is by 0s,0 2 ab C -1 S C,, Vk. hence 13) MM > (00,
(T (recall that Cs = min 2pL. Bo,b} in Lemma 1 (b) by T 2 log log(1=u(xxi} which
log/
implies that T. 2) ug K- 1 )T < 1. Now, rearrange and use the fact that 0n 0n,k-
V || < 2 2 + 400 T033, +83 + 20 B² + (4L2 + LF LF)a
21

---

Then sum over k- = to K 1:
2V
10
K-1
8o g
K-1
2B²
K-1
g
ab,
3 +
0
K
01,K-1K
01,K-1 K
OR,K- K
OH1K-IK
K
k=0
k=
k=0
(4L3 - LF)Øo
K-1
0bbk
01.K-1 K
k=0
2V
4T
4T13030000000
K
300330.0
K
(k + 1)2.5 +
0IK-IK
0LK-IK
an K
k=0
2Baas. ab.0
VV+F
K-1
Σ
(AL + LF 03 6,0
01
K
VK++
01,K KK
k+1
@vi
2V
of log(K) 80
01,0VK K
O,,OVK K
anoV K
2
(4Lg + LF 08 20 log(K)
01,0
a
where we substituted 0b.
ano
and Book = 9.. in (c); (d) is based on Ek= (4+1) S 2,
Vk+I
K+I
EkO उन & log(K), (K), and ===
VK+I S V.. Recall that in Lemma 2 we have I.g Onm))
by ~ (K)), and Lp ~ O(x3). Also recall that ObD = Vk+I
0s.0
and OnLK
VK+I' hence
01.0
we choose 0g 00,0 O T Ok)), and Bb,0 O(x Then we can obtain K-
R Ek=D E[] < O VK
+
x² log(K)
VK
A.4.2 Theorem 4 and its proof
Theorem 4. Suppose f and g satisfy Assumptions and 3 and, learning-ratt upper bounds O,
06.00 and ai,k vK+I with an,o and an satisfying LF+1LE 2 oi.a and au S -ss.u- Further VK+I
0n.o
a1.o
assume that og is independent of the stochastic hypergradient l Then, under the Bounded-variana
assumption in T6p with p 2 max 1hg AA,,
Motbaa }. 30.0 S min( 2 Hg 2pyhh" 22pg pu LTg
2ugho } and
pyy
lool 3 0 +2)
2 min - log(1- 20gh2 bbg Do. .).- log( (og((( "y mo )0
BiSPS achieves the following rate:
5 3
n² log K ) VR
K
VK
k=0
Proof. Start with Lemma 4
1 < V
a11 E [[] + (an, I.3 + 2) k+1 - y¹ (1*)))
2
Lra 109 Elli** v² (a (1.)
B² + (213a +
We substitute the result of Lemma 6 for the expression E11l 1¹ y0 112)
E EII [12] + [(as, L33 + 2)(
no. C₁
2 Bo.x)= 1|Elle* (2*)))
2
Mg + Ln
I.r
+ T2 B + 23, + 0b, B² + [21 +
B²,
2 o
(a)
< ElV4
- 015
BII 1 1 B6,
+ 2T o2 + B2 + +1213 + Ir
2 o
2
22

---

log 1. +2)
log( 1.
where in (a) we have chosen T 2 max
). This ensures
log(1
Mat Po. --
28g42
log(2pt..
2اghي )8,00
Pu
that T loglassoL2ã+2
Vk, which guarantees that (av,
0b.k C2
Buglg Lg Br,k) -1 5.
- log( 2x Me La
20 96.))
Motho
Now, rearrange and the fact that 01,K -1 S 01,A-
0L,K - - $ 2
2006 8 TI300 + A + 200 B² + (4Tl + -.r)
Sum over = 0 -
2V
2T K-1
4T
K-1
Σ |||
Σ
Cb,kk +
Σ
82 p
K
0I,K km0
04,K
k=0
2B
K-1
(AL) + Lo)
K-1
Ob,k +
2
01, 01,K-
K
01,K K
k=0
k=0
2V
20
0 40
K-1
1
4T
K-1
01,K-KK
Q1,K-1K
(k + 1)3/2
KI KK
2Ba06.0
K-1
(4L + Lp 1
K-1
Σ
01,K-1 K
(k + 1)0.5
Q1K-1K
k+1
k=
k=0
2V0
2T ab
00.0% 6,0
4T
32
log(K)
6,0
01KK-K
a,oov K
2Baab.
(4L + LF 1, log(K)
01,0
a,,ovK
where in (b) we have substituted ab, = a.. and BB, = vk+1
8..0
and (c) is by Σk= k= (++1)//2 22
Vk+I
ΣK- I
K+I S log(K), and KK1 (k+1)-72 S VK. Similar to the proof of Theorem
we choose
01D0 06,0 0(k-3), T O(s), and BB,0 O(x-1) to obtain K EK= E
s
0 x² x² (og(()) K
L
VR
B
Additional Experiment Results
This section is organized as follows. First, we discuss synthetic quadratics experiments. Second, we provide more details on the sensitivity of the algorithms to the choices of in (14). on the reset procedure, and on the search cost of BiSLS. Third, we compare the empirical performance of I-sample vs 2-samples implementations of our algorithms for single-level convex and bi-level optimization. Some additional results for reperrrepreennttioonn learning and data distillation experiments are also presented. We rum independent runs for all our experiments.
B.1 Synthetic Quadratics
The experiments on quadratic functions are adapted from Loizou et al. 29 The training objective is as follows:
f(x) ( (Gc=it)THHt (x- ( x3)²"
xi)
-x-x
H2 xz))
where H; 2) are positive definite. The optimal solutions x; (i = 1,2) are generated randomly from standard normal distribution. Specifically, H; is defined as follows:
H; OT Diagg(oo(11 + Ax)) O, i =
where O and A are taken from the spectral decomposition of pTP, and P is generated from the standard normal distribution. Figure[sshwss shows the convergence of various algorithms with different starting points. Interestingly, both SPSB with either 1 sample or 2 samples (1 sample for computing the gradient and the other for computing the step size) converge to the optimal solution (labelled with star).
23

---

DecSPS
SPSB (2 samples) Starting points
x x Minimum
6
Figure 9: Iterate trajectories of different starting points for the synthetic quadratic experiments.
B.2 Sensitivity of 6, reset, and search cost
In this section, we discuss the effects of 8 in (14), in Algorithm 2 and comment on the search cost of the options in the Reset Algorithm 2 Recall that the line-search condition (8) assumes that we can find a largest "Y I 7b.0 to satisfy it. However, in practice, we apply backtracking procedure, i.e. Th = 7% * w, 0 < w 1, until "/ satisfies (8). Therefore, the found learning rate not guaranteed to be the largest. Nonetheless, we assume that 7/ is the largest to simplify our analysis given above (similar arguments apply to line-search at both upper and lower-level in the bi-level optimization). The experiments in this section are based on syper-representation Icarning [42]. In this case, the objective of the induced bilevel-otimmiztioon problem can be written as:
min (ww) 2Dx, (I w)c (w) Y111
8.l. c c((w)= = argmin 2Dx,
11f((2;;)) Y2112 2
where (X1, Yi) and (X2, Y2) are validation and training data sets with sizes Dx, and Dx,, respec- tively; [(; w) are the embedding layers of the model parameterized by w; and, e is the classification conjugate gradient methods (CG) 17 18 to solve the linear system when computing the hypergradient for hyperrrepressentatoon learning experiments.
layer. Moreover,
Reset While Algorithm 2 (reset) be applied to both upper and lower-level problems, focus our discussions here on the upper-level learning rate (a+). This is because we empirically find it to be critical for the convergence performance (see Figure 6aa. As shown in Algorithm 2 reset has 3 options. Options 1, 2, and 3 search starting from 06,00- 0 and 1/0g-1, at iteration respectively. Option 1 has the highest search cost as it always starts from the same initial upper bound (av.n). Option 2 ensures the monotonicity of the learning rate due to S 0% = -r Option 3 chooses the search starting point at iteration (av,s) by multiplying the previous learning rate (ax-1) by factor 2 1. As in the single-level convex case where monotonicity in the step size can potentially lead slow convergence (see Figure 3 we again observe that monotonicity in the upper learning rate (i.e. option 2) leads to poorer performance when compared against options 1 or 3 as shown in Figure 10 Finally, we compare the performance
different 17s option 3 (note that 7) in option is equivalent to option 2). We observe in Figure IT that different 77s perform equally well. This shows the robustness of our algorithm to the choice 1). As mentioned previously, the choice of option over option 1 are due to 2 reasons: (a) reduced search cost; (b) provides overall non-increasing and non-monotonic trend of upper bound 04t We discuss search cost of different rys option below.
Search Cost Based on the results in Figure 7b we observe the use of option in reset can significantly reduce the search cost for both BiSLS-Adam and BiSLS-SGD. Figure [0 further suggests that options I and 3 have nearly the same performance. Therefore, option 3 is an efficient algorithm that maintains good performance while reducing computation cost. Option 2 has the lowest search cost (~~ 4 rounds per iteration). However, its performance is not as good as option 1 or 3 as

---

1.8
000p 1) 0.0 (0pt-2)
5 0.0 (Opc
(0pi-2)
1.6
(Dpe-))
(Dpt-)
1.4
Validation Less
1.2
1.24
Validation
1.0
0.8
6.8
30 Upper lterations
Upper lterations
(a) Different Opt (BiSLS-SGD)
(b) Different Opt (BiSLS-Adam)
Figure 10: Validation loss against iterations with search options 1, 2, and for the upper-level learning rate. The results for BiSLS-SGD and BiSLS-Adam in (a) and (b), respectively. For the lower-level search, we fix it option 1 with 56,0 = 100. Results are based on hyper-representation learning.
BISLS-SGD
B/SLS-Adam
BISLS 20
BISLS n-
1.8-
BiSLS-SGD y- 5.0
BiSLS-Adami 5.0
BISLS 7.0
BISLS Adam 7.0
1.4
14-
B:5LS-Adam 10.0
Validation Loss
Valldation Loss
1.2
1.2
1.0
1.0
6.8
6.6-
0.4
0.2
10
20
30
40
Upper Iterations
Upper lterations
(a) Different rys (BiSLS-SGH
(b) Different yys (BiSLS-Adam)
Figure 11: Validation loss against iterations for different 7s based on reset option 3. Results for
BiSLS-SGD are given in (a) and for SiSLS-Adam are given in (b). Note that v = 1 in reset option is equivalent to reset option 2. For the lower-level search, we fix it option I with 8r, 100. Results are based on hyper-representation learning.
observed in Figure 10
Moreover, the average lower-level search cost is only round per iteration
when option is used (see Figure 12)
Sensitivity on As mentioned in Sec 2 due to the stochastic error in hypergradient computation, further complicated by the approximation error of y (ar) (see (14). a learning rate guaranteed to be found in the bi-level case. Specifically, this is in contrast to the single-level convex problems.
To avoid this, we introduce in (14 8 slack give some tolerance such errors. Here, we give thorough investigation of the effects of on performance. We vary its magnitude across orders for both reset options and (see Algorithm faathmmmmandd and discussions on reset above). We observe that despite large difference on the magnitudes of ò, they all share very similar performance for both BiSLS-SGI S-D and Bidm---Adam: see Figures and 14 We summarize the key fins this section as follows: ① The option 3 in reset has good empirical performance (outperforms option 2) and an effective way reduce search cost (Figure ??); @ BiSIS is highly robust different choices of in option 3 and ò in 14 (Figure
25

---

1.05
Lower-Level Search Cost
1.04
1.03
1.02
1.01
1.00
4000
fn.
Figure 12: Lower-level search cost measured in the same way upper-level against different lower- level search starting points (3,,)). The lower-level search is done with option (see above for discussions about these options).
1.8
1.8
0.0000ppt:1
1.6
10 (0pt1)
0-10-1 (Op-1)
6=10- (0pt1)
8=10 (0pt1)
1.4-
6-10- (0pt1)
0-10-1 (Op-1)
10s1 (0ps4)
6= (0pt1)
Validation Loss
6- 10 (0p:
Validalion Less
10-2 (Opt1)
1.2
1.0
0.4
0.4
0.2
10
20
Upper Iterations
Upper Iterations
(a) Different 6s/Opt-1 (BiSL--SGD)
(b) Different 8s/Opt-1 (BiSLS (ddmm))AAdm)
Validation loss against iterations for different is based on reset option 1. Results for BiSLS- SGD (a) and for BiSLS-Adam (b). For the lower-level search, we fix option with $0.0 100. Results are based on hyper-represeenatiio learning.
Figure 13:
B.3 Data distillation objective and additional results
We let (w) denote the loss evaluated dataset S with model weights w. The objective of data distillation can be expressed as a BO problem as follows:
D* = argmin Ly (w" (w"(D)) s.t. wD( = argmin Lp (w)),
where V of the same size as D and subsampled from the entire (original) dataset V. The solution D* is the distilled data, e.g. 9 MNIST digits each corresponding to different label. In figure 15a we show the performance of BiSPS for different values of 04,0 in comparison with BiSLS-SGI and observe that BiSL.S-SD has better performance. In 15b] we show the results when we increase the number of lower-level iterations (T) from 20 to 50. As observed for T = 20 (in Figure g) BiSLS-SGD here also outperforms a fine-tuned Adam or SGD.
B.4 1-samlle or 2-samples versions of algorithms for convex and bi-level optimization
provide additional results to compare the performance of 1-sample and 2-samples (one for computing the gradient and the other for computing the step size) versions of algorithms for
26

---

1.8
0.0 (0pt
6 100t
10r4 (0ps3)
10r4 (opa3)
6- 1- (Opt3)
6- 1-10-1 (0pt3)
10 (0ps-3)
10-1 (0p43)
Validation Less
10-1 (Opt
10 (0ps-3)
Validation Loss
14-
6- 10- (0pt3)
10 (0po3)
1.0
6.8
0.8
0.6
0.6
6.4
0.2
30
10
20
40
50
Upper lterations
Upper iterations
(a) Different 8s/Opt-3 (BiSLS-SGD)
(b) Different 6s/Opt-3 (BiSLS-Adam)
Figure 14: Validation loss against iterations for different ōs based on reset option (17 = 10). Results for BiSLS-SGU (a) and for ESSLS-Adam (b). For the lower-level search, fix it option 1 with $0.0 = 100. Results are based on hyper-repressenatton learning.
BISPS-0.1Ik 1
100
-
Validation Loss
Validation Loss
10-1
BISLS-GD
10-1
10a²
10
Adom
d- 0.001
Adem
Adm
2=0.
10
10
10
10
250
500
1500 Upper Iterations
750
1000
1250
1750
2000
250
500
750 1000 1250 1500 1750 2000
Upper Iterations
(a) Different 0s,pS (BiSPS)
(b) T= Identity
Figure 15: Validation loss against iterations. (a) Comparison between BiSPS with different 05,08
and BiSLS-SGI (b) Comparison between BUSLS-SGD to fine-tuned Adam/SGD (3, fixed 10 4). Inverse Hessian in (2) treated as the Identity [30) when computing the hypergradient. Recall that is the total number of lower-level iterations and we have shown the results for T 20 in Figure 8b
SPSB and BiSPS used for single-level and bi-level optimization, respectively. In the single-level case (Figure 16). we observe that 2-samples SPSB performs just as well as I-sample SPSB Interestingly, we observe that their step sizes also follow similar pattern. That is: an initial increase followed
fz, (-1)
by regime where 7 A [I") is frequently used, and eventually changes decaying- step SGD. This seems to also match with Theorem where a transition point for SPSB (kg = max (1, ////]] - 1}. w 2cT-uax 7 2 1,) predicted. At the same time, we also that (perhaps, unsurprisingly) the 2-samples version seems to have a slightly more oscillatory behavior than the 1-sample version as shown in Figure 16 SLSB with either 1-sample 2-samples also result in similar performance and step size. Overall, despite the requirements of Theorems [ 2nd for 2-samples assumption, the empirical performance of 1-sample and 2-samples for either SPSB or SLSB appears to be very similar. Moving on to the bi-level case, recall that Thcorems 3 and 4 require the 2-samples assumption (i.c., ag independent of ht) for the upper-level learning rate. learning and data distillation
We empirically verify this assumption with both experiments. For hyper-representttiio learning experiments in Figure 17 BiSPS with either 1-sample or 2-samples for different values of os.0 show similar performance. In fact, for 0s.0 0.1 we even observe that the 2-samples variant outperforms the 1-sample BiSPS. For data distillation experiments in Figure 18 the performances of I-sample and 2-samples BiSPS are similar each other when
27

---

08.0 = 10.0 or db.u 50.0. In general, the performance difference between I-sample and 2-samples the single-level bi-level settings is small.
Canst SCD
10*
SGD
10
98.50
18,50
SPSD
SPS8
Train Loss
Step Sizes
102
100
10-
Conct 5GD
Decay
S1SA samplees)
10-1
SPS0
10a
SPS9 2 samp mm)
1000
2000
3000
4000
5000
10a
102
102
10
Iterations
Iterations
(a) Train loss
(b) Step size
Figure 16: Binary linear classification on w8a dataset using logistic loss [3. Train loss (left) and step size (right) against iterations. We choose "6,,0 1000 for all algorithms. The upper bound for either
SPSB or SLSB decays as "6.6
76.0 For decaying-step SGD, the learning rate schedule is %8.0
I
vk+1*
Decaying-step 5GD
1.75
BISPS (1-sample) a 0.01
BISPS (1-sample) a. 0.05
BISPS (1-sample) a. = 0.1
1.50
BISPS (2-sample) 0.01
Validation Loss
BISPS (2-sample) de 0.05
1.25
BISPS (2-sample) a.
1.00
0.75
0.50
0.25
0.00
10
20
50
Upper Iterations
Figure 17: Comparison between BiSPS (2-samples), BiSPS (1-sample) and decaying-step SGD. Experiments are based on hyper-repressentation learning. For either version BiSPS, the lower-level learning rate (3r) is fixed at 10. The hypergradient is computed using conjugate gradient [17]
28

---

100
Validation Loss
10
10-2
250
500
1500 1750 2000 Upper Iterations
750
1000
1250
Decay SGD da. 10.0
BISPS da. 10.0
BISPS (2 samples) as. 10.0
Decay SGD 50.0
BiSPS 50.0
BiSPS (2 samples] 50.0
Decay SGD
100.0
BISPS 100.0
BISP5 samples) 100.0
Figure 18: Comparison between BiSPS (2-samples), BiSPS (1-sample) and decaying-step SGD. Experiments are based on data distillation. For either version of BiSPS, the lower-level learning rate (8x) fixed at 10-4, The Inverse Hessian in (2 is treated as the Identity when computing the hypergradient [30]
29


Reviews:
[{"review_id": "vfLh0sRbLD", "reviewer": "Reviewer_TsPX", "summary": "The paper introduces the use of stochastic adaptive-step size methods, namely stochastic Polyak step size (SPS) and stochastic line search (SLS), for bi-level optimization. This approach addresses the challenge of tuning both the lower and upper-level learning rates.", "questions": "What is the overhead of using the proposed algorithm to tune the step size?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. SLS and SPS can be seen as special instances of general family of methods with an envelope-type step-size. \n2. The unified envelope strategy enables the algorithm development and convergence analysis. ", "weaknesses": "The paper compares the proposed algorithms to vanilla SGD or Adam versions, but it does not provide a comprehensive comparison with other existing algorithms for bi-level optimization. This may limit the understanding of the relative performance of the proposed algorithms in the broader context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your overall positive assessment of our work.\n\nweakness: The paper compares the proposed algorithms to vanilla SGD or Adam versions, but it does not provide a comprehensive comparison with other existing algorithms for bi-level optimization. This may limit the understanding of the relative performance of the proposed algorithms in the broader context\n\n**Reply to weakness:** We would greatly appreciate if the reviewer could provide more specific details regarding particular methods they have in mind that could potentially be missing for comparisons. The primary focus of our work centers around the intricacies of tuning the two learning rates within the context of bi-level optimization. Thus, we try to make the comparison as straight and fair as possible under the alternating optimization framework given in eqn (3). For instance, some bi-level optimization algorithms that rely on variance reduction or momentum may require additional hyperparameter tuning, which falls out of the scope of our work. Nonetheless, we believe that our approach can be integrated with these methods, since the general motivation behind line-search is to find the learning rate given a suitable direction. Moreover, we have already shown the compatibility of our algorithm with various techniques for computing the hypergradient, such as Conjugate Gradient, Neumann Series, or the Hessian inverse being treated as identity (Figure 5a, 7a, 7b).\n\nquestion: What is the overhead of using the proposed algorithm to tune the step size?\n\n**Reply to question:** The overhead is the execution of line search steps until the modified Armijo line-search rule given in eqn 14 is satisfied. To avoid always searching from initial learning rates $\\alpha_{b,0}$ and $\\beta_{b,0}$, we have come up with a reset subroutine (Algorithm 2) that sets the search starting point of current iteration to be a factor $\\eta$ times the previous iteration's learning rate (option 3). Its full descriptions can be found in Section 2 and Appendix B.2. We have shown that our algorithm is robust to the choice of $\\eta$ in Figure 10 in Appendix. Furthermore, Figure 11 in Appendix shows the cost for finding the upper and lower-level learning rates are $9$ and $1$ respectively when $\\eta = 2$ (measured in terms of average number of search rounds until eqn (14) is satisfied per iteration).\n\nTo further address your question, we added additional experiments on the run-time of the algorithm measured in seconds. Despite the search cost, our algorithm reaches a threshold validation accuracy (85%) faster than the baseline for different number of Conjugate Gradient (CG) steps as shown in the table below. This is because our algorithm is able to find suitable and potentially large learning rates as demonstrated in Figure 5b and 5c. Moreover, tuning the baseline learning rates has a significant higher computation cost (not included in the table) than running the algorithm itself, which is resolved by our proposed approach. \n\nWe are happy to discuss further if there are any additional questions.    \n\n| CG steps | 5| 10 | 15 | 20 |25| \n| -| -|-|-|-|-|\n| Adam| 138.4 $\\pm$ 15.5 | 131.8 $\\pm$ 14.7| 144.6 $\\pm$ 23.6| 158.1 $\\pm$ 19.6| 169.93 $\\pm$ 22.4|\n|BiSLS-Adam (ours)|84.7 $\\pm$ 14.5| 84.0 $\\pm$ 10.5| 98.5 $\\pm$ 20.9| 110.3 $\\pm$ 19.5|117.6 $\\pm$ 22.7| \n\n\n"}, {"review_id": "K92zbMgCAv", "reviewer": "Reviewer_evaJ", "summary": "This work studies adaptive step-size methods for both single-level optimization and bilevel optimization. The authors propose two novel variants of stochastic line search (SLS) and stochastic Polyak step size (SPS), and they unify these variants into a general envelop strategy. Importantly, these variants are simpler to implement and demonstrate good empirical performance, particularly in non-interpolating scenario. By using the unified envelop strategy, the authors also propose a bi-level line-search algorithm BiSLS-Adam/SGD with convergence guarantees, which demonstrates empirical robustness and generalizes well.", "questions": "Q1: Can the authors explain in more details why it is possible to set the number of inner steps to be 1 in Line 213? \n\nMinor Comments:\n1. For Equation (2), the $+$ should be $-$.\n\n2. In Equation (13), $\\nabla_y^2 yg$ should be $\\nabla_{yy}^2 g$.\n\n3. In Line 175, $\\nabla f_x$ should be $\\nabla_x f$.\n\n4. The quadratic functions in Figure 2 and Section B.1 do not satisfy the gradient bounded assumption in Assumption 2. \n\n5. The $+$ in Equation (17) should be $-$.", "limitations": "The authors discussed some of the limitations on single-level optimization in the conclusion section of the paper. \n\nOn bilevel optimization, a limitation is the lower-level strong convexity in Assumption 3. It would be of interest to investigate whether this condition can be relaxed or removed, taking into account recent advancements in the field, such as those presented in [1, 2,3].\n\n[1] B. Liu et al. “Bome! bilevel optimization made easy: A simple first-order approach.” NeurIPS 2022.\n\n[2] R. Liu et al. “Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity.” ICML 2023.\n\n[3] H. Shen and T. Chen, “On penalty-based bilevel gradient descent method.” ICML 2023.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Both adaptive step-size methods and bilevel optimization are currently active topics. The investigation of auto-tune step sizes for bilevel optimization algorithms is under-explored, and the studied topic in work is interesting and important. \n2. The illustrations in Figures 1-5 are helpful in understanding the contributions.\n3. The newly proposed variants of stochastic line search (SLS) and stochastic Polyak step size (SPS) in this work are novel and easy to understand. Moreover, these variants can be unified into a general envelop-type step size, and their effectiveness in the context of single-level optimization and bilevel optimization is well-supported by theoretical results and extensive experiments. ", "weaknesses": "See the Limitations below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! \n\nWe appreciate your careful reading of our paper and thank you for pointing out a few typos, which will be fixed in the revision. \n\nQ1: Can the authors explain in more details why it is possible to set the number of inner steps to be 1 in Line 213?\n\n**Reply to Q1:** Although we have not formally analyzed this heuristic, we have found that it works well empirically while significantly decrease the computation cost. Specifically, while more steps can be used to give a better approximation of $y^*(x)$ in the nested loop, they don't seem to give significant improvements in terms of validation accuracy considering the extra overhead introduced. We have added additional experiments to justify this point with changing number of steps for approximating $y^*(x)$ given in the top row of the table below. \n\n|  | 1| 2 | 5 | 7 |10| \n| -| -|-|-|-|-|\n| Best validation accuracy (units in 100%)| 91.42 $\\pm$ 0.70 | 91.78 $\\pm$ 0.70| 91.88 $\\pm$ 0.83| 91.86 $\\pm$ 0.99| 92.00 $\\pm$ 0.95|\n|Time to reach 85% validation accuracy (units in seconds)| 110.10 $\\pm$ 19.70| 113.76 $\\pm$ 20.49|161.91 $\\pm$ 26.85|181.74 $\\pm$ 22.84|244.34 $\\pm$ 38.02| \n\nLimitations: The authors discussed some of the limitations on single-level optimization in the conclusion section of the paper. On bilevel optimization, a limitation is the lower-level strong convexity in Assumption 3. It would be of interest to investigate whether this condition can be relaxed or removed, taking into account recent advancements in the field, such as those presented in [1, 2, 3].\n\n**Reply to Limitations:** Thank you for highlighting these recent works. While lower-level strong-convexity is a standard assumption in bi-level optimization, e.g. [4,5,6,7], we are eager to study in detail the references that you mentioned hoping to extend our results to that context in future research.\n\n[4] Ghadimi and Wang Approximation Methods for Bilevel Programming\n\n[5] Hong et al. A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic\n\n[6] Ji et al. Bilevel Optimization: Convergence Analysis and Enhanced Design\n\n[7] Chen et al. Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems"}, {"review_id": "UGqXy6Czs6", "reviewer": "Reviewer_ysEm", "summary": "This paper presents an adaptive step size algorithm for bi-level optimization, which improves the shortcomings of the existing BO method that requires careful adjustment of the upper and lower learning rate, and gives a proof of convergence. Experiments also verify the robustness of the method to learning rate.", "questions": "1.The drawing of  figure is difficult to read. For example, the line of beta=10.0 in Figure 1 is not fully drawn, different colors and lines are mixed in Figure 2 but have no additional meaning, and the second half of the right subgraph in Figure 3 is too complex, resulting in some lines being unrecognizable.\n2. The light colored parts in the figure do not seem to represent the three standard deviations, but rather the upper and lower bounds?\n3.I noticed that the sequence of upper and lower bounds for the declared step size in the paper needs to be appropriately controlled, so my point of interest is whether the decay rate is not 1/ sqrt {k+1}? Or can I change the decay rate to change the rate of convergence?", "limitations": "Yes, the author clearly stated the assumptions of the algorithm.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper presents an adaptive and robust bi-level optimization algorithm for adaptive step size, which can obtain a good set of step sizes without prior knowledge and careful modulation.\n2.This algorithm is compatible with the accelerated solver Adam in addition to SGD, improving computational efficiency.\n3.The analysis framework of this algorithm more generally unifies SPS and SLS.", "weaknesses": "1.Theorem 1 only states that f is convex rather than strongly convex, but the full text lacks explanation for the case of multiple solutions at the lower level\n2.Potential computational burden. Although the author states that only a small number of matrix vector multiplication and addition operations are usually used to approximate matrix inverses, this still implies additional computational complexity and there is a problem: the trade-off between the performance loss caused by approximation and the improvement of computational efficiency. Specifically, the lack of time analysis in the charts in the paper exacerbates this concern.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our work.\n\nweakness 1: Theorem 1 only states that f is convex rather than strongly convex, but the full text lacks explanation for the case of multiple solutions at the lower level\n\n**Reply to weakness 1:**  Let us please clarify that Theorem 1 is for the case of single-level optimization; thus, there is no lower-level optimization. \n\nweakness 2: Potential computational burden. Although the author states that only a small number of matrix vector multiplication and addition operations are usually used to approximate matrix inverses, this still implies additional computational complexity and there is a problem: the trade-off between the performance loss caused by approximation and the improvement of computational efficiency. Specifically, the lack of time analysis in the charts in the paper exacerbates this concern.\n\n**Reply to weakness 2:** We want to emphasize that there is no additional backpropagation operations when executing the line search steps until eqn (14) is satisfied. Hence, the matrix vector multiplications are mainly associated with computing the hypergradient. Here, we have added additional experiments on the run-time (in seconds) of the algorithm to reach 85% validation accuracy for different number of Conjugate Gradient (CG) steps given in the table below. We observe the consistent improvement of our algorithm over the baseline in terms of computation time. This is due to the suitable and potentially large learning rates found by our algorithm (Figure 5b, 5c). Besides this, a more significant computation cost of the baseline is tuning the learning rates (not included in the table) which is not required by our algorithm. \n\n| CG steps | 5| 10 | 15 | 20 |25| \n| -| -|-|-|-|-|\n| Adam| 138.4 $\\pm$ 15.5 | 131.8 $\\pm$ 14.7| 144.6 $\\pm$ 23.6| 158.1 $\\pm$ 19.6| 169.93 $\\pm$ 22.4|\n|BiSLS-Adam (ours)|84.7 $\\pm$ 14.5| 84.0 $\\pm$ 10.5| 98.5 $\\pm$ 20.9| 110.3 $\\pm$ 19.5|117.6 $\\pm$ 22.7| \n\nTo further explore the trade-off between performance loss and computation efficiency, we have added experiments that change the number of steps for approximating $y^*(x)$ in eqn (14) (note that we limit it to be 1 in eqn (14)). We observe that increasing this number can improve the performance of the algorithm, but the gain may not be significant considering the extra overhead introduced, e.g., comparing the number of steps being 1 and 10. Figure 11 in Appendix provides additional information on the search cost for different values of $\\eta$ in reset option 3.   \n\n|  | 1| 2 | 5 | 7 |10| \n| -| -|-|-|-|-|\n| Best validation accuracy (units in 100%)| 91.42 $\\pm$ 0.70 | 91.78 $\\pm$ 0.70| 91.88 $\\pm$ 0.83| 91.86 $\\pm$ 0.99| 92.00 $\\pm$ 0.95|\n|Time to reach 85% validation accuracy (units in seconds)| 110.10 $\\pm$ 19.70| 113.76 $\\pm$ 20.49|161.91 $\\pm$ 26.85|181.74 $\\pm$ 22.84|244.34 $\\pm$ 38.02| \n\nQuestions: 1.The drawing of figure is difficult to read. For example, the line of beta=10.0 in Figure 1 is not fully drawn, different colors and lines are mixed in Figure 2 but have no additional meaning, and the second half of the right subgraph in Figure 3 is too complex, resulting in some lines being unrecognizable. 2. The light colored parts in the figure do not seem to represent the three standard deviations, but rather the upper and lower bounds? 3.I noticed that the sequence of upper and lower bounds for the declared step size in the paper needs to be appropriately controlled, so my point of interest is whether the decay rate is not 1/ sqrt {k+1}? Or can I change the decay rate to change the rate of convergence?\n\n**Reply to Q1:** Thanks for the suggestions regarding Figures 2 and 3. We will improve their readability in the revision. For $\\beta=10.0$, the algorithm diverges after the period in which the line is drawn.  \n**Reply to Q2:** The light colored parts are standard deviations. \n\n**Reply to Q3:** We expect that using different envelopes can give faster rates under additional assumptions (or achieve similar rates in more-general settings).\n\n"}, {"review_id": "0KSlCCz5uW", "reviewer": "Reviewer_75AD", "summary": "This paper studies the bilevel optimization problem, an in particular, focuses on developing effective learning rate schemes for bilevel optimization. In specific, the authors propose two adaptive step-sizes methods named stochastic line search (SLS) and stochastic Polyak step size (SPS) as variants of methods such as SPSmax and DecSPS. Compared to existing approaches, the proposed methods do not require the step-sizes to be monotonic by replacing the constant $\\gamma_{b,0}$ by a non-increasing $\\gamma_{b,k}$. The adaptive stepsizes are further applied to bilevel optimization on both upper and lower levels. The convergence analysis is provided for SPS and SLS on single-level problems and also for bilevel problems. Simple experiments are provided. \n", "questions": "Please see Weakness part. ", "limitations": "Please see Weakness part. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Studying adaptive learning rates in bilevel optimization is interesting, and has not been explored well in the literature. \n\n2. The proposed adaptive learning rates are more practical than existing methods like SPSmax and DecSPS with milder requirements. ", "weaknesses": "1. The paper is well written and hard to follow. For example, there are quite a few assumptions and requirements in the paragraphs of describing the proposed methods. There are also many notations and inequalities in Section 2. It makes me a little bit hard to follow the principle of the designs. \n\n2. The adaptive learning rates seem to introduce more hyperparameters such as $l^*_{i_k}, c_{k},\\gamma_{b,k}$. It makes me wonder how it can be meaningful in practice given more efforts in tuning such parameters. In addition, no sensitivity analysis is provided for such parameters in experiments. \n\n3. How to find the approximate $l^*_{I,k}$ of the lowest function value? Is the choice of this quantity important in terms of performance? A more comprehensive empirical justification should be provided.\n\n4. In terms of the complexity, it seems to me the proposed stepsizes cannot provide improved sample or computational complexity in theory. Maybe I miss something, but I think the authors can elaborate on this\n\n5. The experiments are not convincing enough. Since the biggest motivation lies in the design of adaptive learning rates, the benefits may come from the empirical side. Thus, it would be better to provide more comprehensive experiments on practical NN architecture and larger datasets for the validation. However, the current experiments are rather toy examples. If the contribution lies in the theoretical side, it fails to show improved complexity performance. \n\nOverall, I like the topic of adaptive learning rate for bilevel problems. However, the current theory and experiments are not convincing enough, and how important the proposed methods also are not clear to me. For this reason, I am on the negative side for the current version. I am also open to change my mind if more convincing experiments (e.g., how to select extra parameters, more datasets and backbones, sensitivity analysis, more problems) can be provided. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to weakness 1:** We would appreciate if the reviewer could elaborate on specific issues that might be unclear to them. This would enable us to address these concerns and enhance the overall clarity of our work.\n\n**Reply to weakness 2:** Let us clarify the roles of these hyperparameters. Starting with $l_{i_k}^*$, note this is simply a **lower bound** on the minimum function value. In particular, it can be taken as $0$ for positive losses such as cross-entropy and we set it to be $0$ for all experiments.  With regards to the parameters $c_k$ and $\\gamma_{b,k}$, we emphasize that our algorithm is robust to these choices. To further illustrate this, we provide below additional experiments on the minimum train loss for different values of $\\gamma_{b,0} \\in$ \\{$ 100,500,1000,2000$\\} with $c_k = 1, \\forall k$ (note the decay schedule for $\\gamma_{b,k}$ is $\\frac{\\gamma_{b,0}}{\\sqrt{k+1}}$).\n\n| $\\gamma_{b,0}$ | 100 | 500 | 1000 | 2000 |\n| -------- | -------- | -------- | -| -|\n| Minimum Train Loss     |  0.04821 $\\pm$ 2e-05 |  0.04458 $\\pm$ 3e-05 | 0.04433 $\\pm$ 5e-05 | 0.04475 $\\pm$ 9e-05|\n\nWe further show the results for different values of $c_k \\in$ \\{$1,2,5,10$\\} with $\\gamma_{b,0} = 1000$. \n\n| $c_k$ | 1|2|5|10|\n|- |- |-|-| -|\n| Minimum Train Loss|0.04433 $\\pm$ 5e-05| 0.04439 $\\pm$ 6e-05 | 0.04453 $\\pm$ 6e-05| 0.04497 $\\pm$ 5e-05|\n\nIn particular, we wish to contrast these results to the sensitivity of decaying-step SGD to its learning rate. For the latter, the table below shows the minimum train loss of SGD changes much more drastically as the learning rate changes when compared against our algorithm (note the learning rate schedule is chosen to be $\\frac{\\gamma_{b,0}}{\\sqrt{k+1}}$). \n\n| $\\gamma_{b,0}$ | 100 | 500 | 1000 | 2000 |\n| -------- | -------- | -------- | -| -|\n| Minimum Train Loss     |  0.04945 $\\pm$ 8e-05 |  0.073 $\\pm$ 1e-03 | 0.119 $\\pm$ 3e-03 | 0.220 $\\pm$ 6e-03|\n\n**We did a thorough study on the extra parameters associated with our algorithmic design in the bi-level setting, specifically, search initializations for upper ($\\alpha_{b,0}$) and lower-level learning rates ($\\beta_{b,0}$) (Figure 6c, 6d), sensitivity of the algorithm to $\\delta$ in eqn (14) (Figure 12, 13 in Appendix), performance of different reset options in Algorithm 2 (Figure 9 in Appendix), sensitivity of $\\eta$ in reset option 3 (Figure 10 in Appendix), and upper and lower-level search cost (Figure 11 in Appendix). We want to emphasize that BiSLS is highly robust to the parameters associated with the algorithm, namely $\\alpha_{b,0}$, $\\beta_{b,0}$, $\\delta$, and $\\eta$** (note that reset option 3  has the best performance in terms of convergence speed, generalization, and computation cost). Besides this, we also observe that BiSPS is much more robust to $\\alpha_{b,0}$ (upper-level learning rate bound) when compared against decaying-step SGD (Figure 4). \n\n**Reply to weakness 3:** see reply for weakness 2.  \n\n**Reply to weakness 4:** The convergence rate matches the best rate of SGD [1]  while not requiring exhaustive step-size tuning.  \n\n[1] Chen et al. Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems\n\n**Reply to weakness 5:** **The key contribution of this work is to address the question of how to remove the extensive manual tuning of the two learning rates in bi-level optimization  (Figure 5b,5c)**. The experiments of hyper-representation learning and  data distillation are adapted from [2] and [3], respectively, using neural networks and real datasets. These are important and recent applications of bi-level optimization. The experiments in the bi-level setting are more challenging than the single-level setting as the computation of hypergradient typically involves second-order gradient information which can incur a high memory cost.\n\n[2] Sow et al. On the Convergence Theory for Hessian-Free Bilevel Algorithms \n\n[3] Lorraine et al. Optimizing Millions of Hyperparameters by Implicit Differentiation\n\nTo concretely demonstrate the computation efficiency of our approach, we performed additional experiments on the run time of an algorithm to reach 85% validation accuracy for different number of Conjugate Gradient (CG) steps (results with units in seconds are given in the table below). We observe the consistent improvement of our algorithm over the baseline. Besides this, the baseline requires extensive tuning of the two learning rates which adds significant more computation cost at first place (not included in the table).   \n\n| CG steps | 5| 10 | 15 | 20 |25| \n| -| -|-|-|-|-|\n| Adam| 138.4 $\\pm$ 15.5 | 131.8 $\\pm$ 14.7| 144.6 $\\pm$ 23.6| 158.1 $\\pm$ 19.6| 169.93 $\\pm$ 22.4|\n|BiSLS-Adam (ours) |84.7 $\\pm$ 14.5| 84.0 $\\pm$ 10.5| 98.5 $\\pm$ 20.9| 110.3 $\\pm$ 19.5|117.6 $\\pm$ 22.7| \n\nFurthermore, we added experiments that change the number of gradient steps (given in the top row of the table below) for approximating $y^*(x)$ when executing the line search steps according to eqn (14) (note this number is limited to be $1$ in eqn (14)). The results suggest that a single step already gives good performance. Further increasing this number does not lead to significant improvement considering the increase in the run-time of the algorithm.  \n\n|  | 1| 2 | 5 | 7 |10| \n| -| -|-|-|-|-|\n| Best validation accuracy (units in 100%)| 91.42 $\\pm$ 0.70 | 91.78 $\\pm$ 0.70| 91.88 $\\pm$ 0.83| 91.86 $\\pm$ 0.99| 92.00 $\\pm$ 0.95|\n|Time to reach 85% validation accuracy (units in seconds)| 110.10 $\\pm$ 19.70| 113.76 $\\pm$ 20.49|161.91 $\\pm$ 26.85|181.74 $\\pm$ 22.84|244.34 $\\pm$ 38.02| \n\nFinally, our experiments demonstrate that the proposed algorithm can work with different types of hypergradient computation including CG (Figure 5a), Neumann series (Figure 7a), or the Hessian inverse being treated as identity (Figure 7b). \n\nWe believe that our experiments are comprehensive. Thus, we are happy to discuss further if there is any remaining  concerns. "}]

Author rebuttal:
Dear Reviewers,

We thank you for taking the time to carefully read and review our work. We are confident that integrating your suggestions will further improve our paper; thus we plan on doing so in the revision.
In the specific replies below, we comment on specific issues brought up by different reviewers.

We are open to further discussions should any additional questions arise.


Meta-review: The reviewers are in consensus that this work is novel and significant, unifying the Polyak step size and stochastic line search in a common framework for bilevel optimization. The authors addressed reviewers' concerns comprehensively, including running additional experiments to resolve some reviewer curiosities. The authors are encouraged to incorporate the reviewers' remaining suggestions, which arose during the discussion period.
Decision: Accept (poster)