An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
Authors: Xiaochuan Gong
Jie Hao
Mingrui Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Bilevel Optimization
Acceleration
Unbounded Smoothness
Nonconvex Optimization
Primary area: optimization
TL;DR: This paper introduces a new algorithm and analysis to accelerate bilevel optimization under unbounded smoothness.

Abstract: This paper investigates a class of stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness and the lower-level problem is strongly convex. These problems have significant applications in sequential data learning, such as text classification using recurrent neural networks. The unbounded smoothness is characterized by the smoothness constant of the upper-level function scaling linearly with the gradient norm, lacking a uniform upper bound. Existing state-of-the-art algorithms require $\widetilde{O}(\epsilon^{-4})$ oracle calls of stochastic gradient or Hessian/Jacobian-vector product to find an $\epsilon$-stationary point. However, it remains unclear if we can further improve the convergence rate when the assumptions for the function in the population level also hold for each random realization almost surely (e.g., Lipschitzness of each realization of the stochastic gradient). To address this issue, we propose a new Accelerated Bilevel Optimization algorithm named AccBO. The algorithm updates the upper-level variable by normalized stochastic gradient descent with recursive momentum and the lower-level variable by the stochastic Nesterov accelerated gradient descent algorithm with averaging. We prove that our algorithm achieves an oracle complexity of $\widetilde{O}(\epsilon^{-3})$ to find an $\epsilon$-stationary point, when the lower-level stochastic gradient has a small variance $O(\epsilon)$. Our proof relies on a novel lemma characterizing the dynamics of stochastic Nesterov accelerated gradient descent algorithm under distribution drift with high probability for the lower-level variable, which is of independent interest and also plays a crucial role in analyzing the hypergradient estimation error over time. Experimental results on various tasks confirm that our proposed algorithm achieves the predicted theoretical acceleration and significantly outperforms baselines in bilevel optimization.

An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
Xiaochuan Gong
Jie Hao
Mingrui Liu"
Department of Computer Science
George Mason University {xgong2, jhao6, mingruil/sgmu. edu edu
Abstract
This paper investigates class stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness and the lower-level problem strongly convex. These problems have significant applications in sequential data learning, such as text classification using recurrent neural networks. The unbounded smoothness is characterized by the smoothness constant of the upper-level function scaling linearly with the gradient norm, lack- ing uniform upper bound. Existing state-of- saate-of-ther te-thhe-rt algorithms require Ö(e product to find an
oracle calls of stochastic gradient or (lessian/Jcoobian-vedde e-stationary point. However, it remains unclear if we further improve the convergence rate when the assumptions for the function in the population level also hold for each random realization almost surely (e.g., Lipschitzness of each realization of the stochastic gradient). To address this issue, we propose a new Accelerated Bilevel Optimization algorithm named AceBO. The algorithm updates the upper-level variable by normalized stochastic gradient descent with recursive momentum and the lover-level variable by the stochastic Nesterov accelerated gradient descent algorithm with averaging. We prove that our algorithm achieves oracle complexity of Ö(E-3) to find an e-stationary point, when the lower-level stochastic gradient has a small variance O(e). Our proof relies on novel lemma characterizing the dynamics of stochastic Nesterov accelerated gradient descent algorithm under distribution drift with high probability for the lower-level variable, which is of independent interest and also plays a crucial role in analyzing the hyper- gradient estimation eтror over time. Experimental results on various tasks confirm that our proposed algorithm achieves the predicted theoretical acceleration and significantly outperforms baselines bilevel optimization. The code is available here
Introduction
Bilevel optimization receives tremendous attention recently in the machine learning community, due to its applications in meta-learning (27 559 hyperparameter optimization [27 25], data hyper-
cleaning 44, continual learning 7 37,, and reinforcement learning 47 The bilevel optimization
problem has the following formulation:
min ((x) == f(),y"(x)), s.t., y (xx) e arg min g(z, v). <
yERdy
where I and g are upper-level and lower-level functions respectively. For example, in meta- learning 266 27, denotes the layers of neural networks for shared representation learning, denotes the task-specific head encoded in the last layer, and the formulation (T) aims to learn the a
*Corresponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

common representation learning encoder x such that it can be quickly adapted to downstream tasks by only updating the task-specific head y. In machine learning, people typically consider stochas- y; {)] and g(x,0) v) = EE [G(x, ys {]], where D and D are the underlying unknown data distributions for I and g respectively, and one can access noisy observations of f and g based on sampling from D, and Dg-
tic optimization setting such that [(x,, y) RE [F(x,
There emerges a wave of studies for algorithmic design and analysis for solving the bilevel opti- mization problem ( under different assumptions of f and g. Most theoretical work assumes the upper-level function smooth (i.e.. gradient is Lipschitz) and nonconvex, and the lower-level function
48). However, as pointed out by [75] 13], certain neural networks such as recurrent neural networks (2),, long-short term memory networks [40] and transformers [65]
is strongly convex [30
44
41
33
have smoothness constants that scale with gradient norm, potentially leading to unbounded smooth- ness constants (i.e., gradient I Lipschitz constant can be infinity). Motivated by this, Hao et al. (8
designed the first bilevel optimization algorithm to handle the cases where f is nonconvex with
potentially unbounded smoothness and g is strongly convex. The algorithm in 388 achieves Ö(c-t)
oracle complexity for finding an e-stationary point (i.e., a point x such that [ S <). Gong et
al. 32 proposed an single-loop algorithm under the same setting as in (3 and also achieved O(c-t)
oracle complexity. This complexity result is worse than the O(e oracle complexity under the relatively easier setting where f has a Lipschitz gradient, and each realization of the stochastic oracle calls is Lipschitz with respect to its argument (e.g., almost-sure Lipschitz oracle) 77 This naturally motivates us to study the following question:
Is it possible to improve the Ö(c-t) oracle complexity for bilevel optimization problems where the upper-level function is nonconvex with unbounded smoothness and the lower-level function is strongly convex, by assuming that the properties of the function at the population level also hold almost surely for each random realization?
In this paper, we give a positive answer to this question by designing a new algorithm named AccBO with an improved oracle complexity of Ō(c-3), when the lower-level stochastic gradient has a small variance O(e). Our algorithm is inspired by momentum-based variance reduction techniques used in nonconvex smooth optimization 18 under the almost-sure Lipschitz stochastic gradient oracle framework. The innovation of AccBO lies in its update rules: it employs normalized stochastic gradient descent with recursive momentum for the upper-level variable and stochastic Nesterov accelerated gradient descent with averaging for the lower-level variable. Our approach differs from existing accelcrated bilevel optimization algorithms, such as those proposed by [7] 46) in two key ways: (i) while these algorithms use recursive momentum for the upper-level variable update, AccBO utilizes normalized recursive momentum to address the unbounded smoothness of the upper-level function: (ii) for the lewer-level variable update, we use stochastic Nesterov accelerated gradient descent with averaging, in contrast to the recursive momentum method used by the other algorithms. The primary challenge in analyzing the convergence rate of AceBO arises from the need to simultaneously control errors from both upper-level and lower-level variables, given the unbounded smoothness, large learning rate, and recursive momentum in the upper-level problem. Our main contributions are summarized as follows.
We design a new algorithm named AccBO for solving bilevel optimization problems where the upper-level function is nonconvex with unbounded smoothness and the lower-level function is strongly convex. AccBO leverages normalized recursive momentum for the upper- level variable and Nesterov momentum for the lower-level variable under the stochastic setting to achieve acceleration. To the best of our knowledge, the simultaneous usage of these two techniques in stochastic bilevel optimization is novel and has not been previously explored in the bilevel optimization literature.
We prove that the AccBO algorithm requires Ö(c-²) oracle calls for finding an e-stationary point, when the variance of the lower-level stochastic gradient is O(e). This complexity strictly improves the state-of- the oracle complexity for unbounded smooth nonconvex upper-level problem and strongly-conver lower-level problem as described in [38] 32 To achieve this result, we introduce novel proof techniques for analyzing the dynamics of stochastic Nesterov accelerated gradient descent under distribution drift with high probability
"Note that even if the lower-level stochastic gradient variance is O(e). the oracle complexity required 38 32 is still Ö(c= since the oracle complexity required for their upper-level problem is already Ö(c-)).
2

---

for the lower-level variable, which are crucial for analyzing the hypergradient error and also of independent interest.
We empirically verify the effectiveness of our proposed algorithm on various tasks, in- cluding deep AUC maximization and data hypercleaning. Our algorithm indeed achieves the predicted theoretical acceleration and significantly outperforms baselines in bilevel optimization.
2 Related Work
Relaxed Smoothness. The concept of relaxed smoothness was initially introduced by [75 inspired by the loss landscapes observed in recurrent neural networks and long-short term memory networks. They show that techniques such as gradient clipping and normalization could improve the performance compared with gradient descent in these scenarios. It inspired further investigations that concentrate on various aspects, including improved analysis on gradient clipping and normalization [74] 45).
adaptive algorithms [13] 51 68 24], federated algorithms [54] 17). generalized assumptions [5
14), and recursive momentum based methods with faster rates 660 [56]. The work of [8
considered a relaxed smoothness condition for the upper-level problem in the bilevel optimization
setting.
Bilevel Optimization. Bilevel optimization refers to a special kind of optimization where one problem is embedded within another. was first introduced by (9]. Early works developed specific bilevel optimization algorithms with asymptotic convergence analysis [67] [ 69). Ghadimi and Wang [30] initiated the study of non-asymptotic convergence for gradient-basee methods bilevel optimization where the upper-level problem is smooth and the lower-level problem is strongly convex. This field saw further advancements with improved complexity results
21 and fully
first-order algorithms 48 52). There is line of work which leverages almost-sure Lipschitz oracle (e.g., stochastic gradient) to obtain improved convergence rates of bilevel optimization algorithms [7]] [46. When the lower-level function is not strongly convex, several algorithmic framework and approximation schemes were proposed [6 63
55 10 The setting considered in this paper 38 32 where the upper-level function is nonconvex and unbounded smooth, and
is very close to
the lower-level function strongly convex. However, the work of [38 32 not have an accelerated
rate 3c) for finding an c-stationary point as established in this paper.
Nesterov A Accelerated Gradient and Variants. Nesterov Accelerated Gradient (NAG) method was introduced by (58) for deterministic convex optimization problems. The stochastic version of NAG (SNAG) was extensively studied in the literature 3 5 66 13). To the best of our knowledge, none of them provide a high probability analysis for SNAG. the online learning setting, there is a line of work focusing on the perspective of sequential stochastic/online optimization with distributional drift 66 770 57 20]. While these studies provide valuable insights into adaptive techniques and performance bounds under distributional drift, they do not explore the potential integration of such methods with bilevel optimization problems, nor do they consider the application SNAG within this framework.
3 Problem Setup and Preliminaries
Define (.-)) and || as the inner product and the Euclidean norm. Throughout the paper, we use asymptotic notation (-). (-), 22-)) to hide polylog factors in c and 1/8. Denote f: Rd Rdd, - R as the upper-level function, and g: Rd x Rd + R as the lower-level function. The hypergradient
(x(r) has the following form 330:
( ( v² (z)) V (2,0(, (x)) [V 22 (x)) (x))) V,,
(2)
To avoid the Hessian inverse computation, we typically use the following Neumann series to approxi- mate the hypergradient (30 46 41. In particular, for the stochastic setting, define
V2
vy G(a,(a G(a.v:(1))
vf V V,F(2,y:5)
2 G(z, y
II
I
V FyF(
1,11
1
where q()) ~ Uniform
Q- 11. E = (0) ((()2) and we use the convention that
A = 7 if j = 0. Then [V { a good approximation of (x:) y and y (a) are
close 30
3

---

Throughout the paper, we make the following assumptions.
Assumption 3.1 ((Lz,0, LI.1, Ly. (y.1)-smoothness (38). Let 2 = (I, and x' = (x', there
exists Lm,0, La,1; Ly Ly,1 > such that for all 2, if || - =11 s 1/1 2 + 1,,,)) then
[[) (=((=)) < (Ln,0 + Ve.alVaa(=)I))) - z'1l and VV) - vyf(z')I S (Ly,0 +
L V (z)ll)) -
Remark: Assumption 3.1 is introduced by [8] for describing the bilevel optimization problems with
recurrent neural networks. This assumption can be regarded block-wit relaxed smoothness assumptions for two blocks v and which is a variant of the relaxed smoothness assumption (75 and the coordinate-wise relaxed smooth assumption [15].
Assumption 3.2. Suppose the followings hold for /bjetiiivfuunctionss I and g: (i) f is continuously difserentiable and (Lz.0, In,,,, Iy,1)- in (I, y); (ū) For every v, (V w)ll S $1 for all y: (iii For every I, g(2,3) V) is u-strongly-conver in y for > 0; (iv) 9 is 1.11 -smooth jointly in (x. (v) is twice continuously differentiable, and 2 V2yg, V2ng are h.z=LLipschizzoonii in (x. v)-
Assump- tion 3.2 (i) characterizes the unbounded smoothness of the upper-level function and is empirically
Remark: Assumption 3.2 is standard in the bilevel optimization literature 48
30
observed in recurrent neural networks (38].
Assumption 3.3. The following stochastic estimators are unbiased and have the following properties:
V.f(a, BEND, [[V F(,, - (x, s of.. EEWD, ((r,
= o7.1
Pr([VV,G(a {) V w)
2 A) S 2exp(- /o..)) V\> 0,
E ECND, II 22 - (z, b) r) s .2.2. E<-D, [I [1V () Ving(a, w)|l S o
Remark: Assumption 3.3 assumes the stochastic oracle for the upper- problem has bounded variance, which is standard in nonconvex stochastic optimization 228 B0] It also assumes the stochastic oracle for the lower-level problem is light-tailed, which is common for the high probability
analysis for the lower-level problem (50) (3). Note that the same assumption is also made in 38
for the bilevel problems with a unbounded smooth upper-level function.
Assumption 3.4. F(x, E) and G(x, y: () satisfy Assumption 3.2 for every & and Ç almost surely.
Remark: Assumption 3.4 assumes that each random realization of the upper- and lower-level functions satisfies the same property as in the population level. Note that this condition is the key to achieve an improved Ö(E=)) oracle complexity under various settings, including both single-level nonconvex smooth problems 23 18, 64] and bilevel problems with nonconvex smooth upper-level objectives (71 46). Furthermore, this assumption is shown to be necessary for achieving improved oracle complexity single-level problems
4
Algorithm and Analysis
4.1 Main Challenges and Algorithm Design
Main Challenges. We begin by explaining why existing bilevel optimization algorithms and their corresponding analysis techniques are insufficient in our setting. First, most algorithms developed for bilevel optimization require the upper-level function is smooth (i.e., the gradient of the upper- They characterize the estimation error
level function is Lipschitz) 30 of the optimal solution for the lever- problem. utilize an approximate hypergradient descent approach and the descent lemma for L-smooth functions to prove the convergence. In particular, they demonstrate that potential function, incorporating both the function value and the bilevel error from the lower-level problem, progressively decreases in expectation. However, when the upper-level function is (Tzz,; T , T,,,0: )-smooth illustrated in Assumption 3.1 the previous algorithms and analyses relying on L-smoothness do not work. The reason is that the hypergradient bias depends on the approximation error of the lower-level variable as well as the hypergradient itself: these elements are statistically dependent and the standard potential function argument with an expectation- based analysis would not work. To address this issue, the work of [38 32 requires a careful high probability analysis in the unbounded smoothness setting and obtains ((e-)) oracle complexity. Such requirement of high probability analysis prevents us from leveraging the momentum based
46
21 48

---

Algorithm 1 STOCHASTIC NESTEROV ACCELERATED GRADIENT METHOD (SNAG)
I: Input: 2, 9-1 No. ā, To
# SNAG yo, O, To)
2: for t- t= 0, ,,...,21 To do
3: Sample 7t from distribution Dg
4: & = Dt +B= 31-1)
5: Mt+1 2₁ aV, GV,G(z, me)
6: end for
variance reduction technique for updating the lower-level variable. For example, the work [46] which has Ō(--3) oracle complexity in the smooth case leverages the momentum- haasd variance reduction technique 18 for updating the lower-level variable with an expectation- baaed analysis, but it seems difficult to establish high probability analysis for the momentum-based variance reduction algorithm in terms of the lower-level variable. Second, the recent work of Hao et al. (38] and Gong et al. [32] considered that the upper-level function is unbounded smooth and addressed this issue by performing normalized stochastic gradient with momentum for the upper-level variable and periodic updates or stochastic gradient descent for the lower-level variable, but their oracle complexity is not better than Ō(c )) These facts indicate that we need new algorithm design and analysis techniques to get potential acceleration.
Algorithm Design. To obtain potential acceleration and enable a high probability analysis for the lower-level variable, our key idea is to update the upper-level variable by normalized stochastic gradient descent with recursive momentum and update the lower-level variable by the stochastic Nesterov accelerated gradient (SNAG) method. Different from [38] [3], the key innovation of our algorithm design is that we achieve acceleration for both upper-level and lower-level problems simultaneously but without affecting each other. The upper-level update rule can be regarded as a generalization of the acceleration technique (e.g., the momentum- technique) [18] (56) from single-level to bilevel problems. The main challenge is that we need to deal with the accumulated error of the recursive momentum over time due to the hypergradient bias, which is caused by the inaccurate estimation of the optimal lower-level variable. Therefore we require very small tracking error between the iterate of the lower-level variable and the optimal lower-level solution defined by the upper-level variable (i.e., y (x)) at every iteration. This requirement is satisfied by executing SNAG method under the distribution drift for the lower-level problem, where the drift is caused by the change of the upper-level variable over time. Note that we can provide high probability analysis of the SNAG method under distributional drift, which strictly improves the analysis of SGD under distributional drift in 19 in the small stochastic gradient noise regime.
variance reduction
The detailed description of our algorithm illustrated in Algorithm 2 At the very beginning, we run a certain number of iterations of SNAG for the fixed upper-level variable xo (line 2) as the warm-start stage, and then update the lower-level variable by SNAG (line 8 ~ 20) with averaging (line 21) and update the upper-level variable by normalized stochastic gradient descent with recursive momentum (line 23- ~ 24). Note that we have two options for implementing SNAG. In Option (line 8 ~ 9), the algorithm simply runs SNAG under distribution drift caused by the sequence {x²)- Option I is specifically designed for a particular subset of bilevel optimization problems where the lower-level function is a quadratic function. Option II (line 11 20) is designed for broader range of bilvel optimization problems, accommodating general strongly-convex lower-level functions. In Option II, we run SNAG with periodic updates: the lower-level update is performed for N iterations only when the iteration number f is a multiple of
4.2 Main Results
We first introduce some useful notations. Let (-)) be the o-algebra generated by the random variables in the argument. We define the following filtrations for t 2 1: Finit = omo........ .
F, = o 1). F = ( ... 1), and we also define F3 = aTT..... / a multiple of We use H,, Ey, and E to denote the conditional expectation E|- Fi). the expectation over F, and the total expectation over Fr respectively.
o. N N-1) when t is
Theorem 4.1. Suppose Assumptions 3./ to hold. Let {2a} be the iterates produced by Algorithm For any given 8 E (0, and small enough (see exact choice in (44)) if g.1 O(ve) as defined in (55). and we set parameters init a, B, n, N, S, Q, To (see exact choices in 56 57 58
5

---

Algorithm 2 ACCELERATED BILEVEL OPTIMIZATION ALGORITIM (AccBO)
1: Input: a init a, 8,7, T, S, Lo,T,, T, set zo, yo
2: Mo = SNAG(To, with a To), and set y-1
V/u
# Warm-start
3: for t = 0,,1,.,.... 1....,.
do
4: Sample (QQ) Uniform
Q 1) and (4 (9(2)) Dg
St
5: Sample (Er.. } ~ D, denote & == 1 (q(2), Ee.e, St.a ..... St,
(a((1))
6: # Lower-Level: Stochastie Nesterov Accelerated Gradient Descent with Averaging
7: # Option I: from Line 8 ~ (for quadratic lower-level function)
8:
2 = yt + 7 (34e-- 1 9/-1)
9:
Mi+1 V 21; me). where ~ D3
20 (for general strongly convex lower-level function) i 0 and L. is multiple of then
# Option II: from Line
11:
12:
Set vL 4/ =
for j 0, 1,,1,-.. .0....... N do
oi vi + +yvi yi )
!/i =t aV, G( 21: mf), where ाद Dr
16:
end for
N+1
17:
M/++1 1/1
18:
else
19:
Vi+1 = y/1
20:
end if
21:
Ut+1 = (1 - T)h + Tyt+1
# Averaging
22:
# Upper-Level: Normalized Stochastic Gradient Descent with Recursive Momentum
23:
m. 8m,-1 + (1 (00--8)22 B)V dc: Er) +BVV G.) - 11 ift 2 1 else
mo (=0o Jo:
24:
Ft+11 2t 17 T
my
25: end for
59
and
(60) as
T= r= 7= 0(),, init O((²), O 1- =-)= n n= )
Ō( Ō N Ō Ō=Ō(1). S= Ō())..
Then with probability at least 28 over the randomness a oFFint U F/)) (for Option I) or a (Jrinit U (U))TF?)) (for Option II). Algorithm 2 guarantees + Et (x+))( S 20e within Ö(E iterations, where do (xxo) inf 4(x) and the expectation taken over Ado
gc
the randomness over Fr. For Option requires To + SQT Ō(E-a) oracle calls of stochastic gradient or Hessian/Jacobian vector product. For Option II, it requires Ty + NT + SQT = Ō(e oracle calls of stochastic gradient Hessian/Jacobian vector product.
Remark: Theorem 4.1 established improved Ö(c oracle complexity for finding e-stationary
point when the lower-level standard deviation g. = ((VE). This complexity result strictly improves
the Ō( (4) obtained by [38 32 when the upper-level function is nonconvex and unbounded smooth.
This complexity result also matches that the single-level unbounded smooth setting (56) and nearly optimal in terms of the dependency (2). The full statement of Theorem 4.1 is included in
Theorem
4.3 Proof Sketch
In this section, we provide a roadmap of proving Theorem 4.1 and the main steps. The detailed proofs can be found in Appendix [D) [n] The key idea is to prove two things: (1) the lower-level iterate is very close to the optimal lower-level variable at every iteration; (2) two consecutive iterates of the lower-level iterates are close to each other. particular, define y/ = (x,), and we aim to prove that || yī < O(e) and || Jell < O) for every (. These two requirements are essential to control the hypergradient estimation error (i.e., || ( caused by inaccurate estimate the lower-level problem. Lemma 4.7 provides the guarantee for the lower-level problem, and Lemma 4.8

---

characterizes the hypergradient estimation error. Equipped with these two lemmas, we can adapt the momentum-banne based variance reduction techniques [88 [6] to the upper-level problem and prove the main theorem.
The main technical contribution of this paper is provide general framework for proving the convergence of SNAG under distributional drift in Section 4.3.I which can be leveraged as a tool to control the lower-level error in bilevel optimization and derive the Lemma 4.7 illustrated in Section 4.3.2 In particular, we can regard the change of the upper-level variable x at each iteration as the distributional drift for the lower-level problem: the drift is small due to the normalization operator of the upper-level update rule and also the Lipschitzness of y" (z). Once we have the general lemma for tracking the minimizer for any fixed distributional drift over time, this lemma can be applied to our algorithm analysis and establish guarantees for the bilevel problem.
4.3.1 Stochastic Nesterov Accelerated Gradient Descent under Distributional Drift
In this section, we study the sequences of stochastic optimization problems min (e(w) indexed by time / E N. We denote the minimizer and the minimal value of oe as wi and Φi and we define the minimizer drift at time / to be A, ||wu w1+1ll- With slight abuse of notation we consider the SNAG algorithm applied the sequence { where T is the total number of iterations:
= Wt + 7 (wi w;-1)
W/+1 wy + 7wm w;-1) ogt:
where 9r. Vohi Ee) is the stochastic gradient evaluated at with random sample & Define E, = St - (ze) as the stochastic gradient noise at (-th iteration. Define H. =
as the filtration, which is the o-algebra generated by all random variables until (-th iteration. We make the following assumption, which the same as Assumption 3 in [20] for high probability analysis.
Assumption 4.2. Function Φz Rd - IR is p-strongly convex and L-smooth for constants μ., L > 0. Also, there exists constants A, a > 0 such that the drift A is sub-exponential conditioned on H4 with parameter 2 and the noise E is norm nab-Gaussian conditioned on Ha with parameter o/2. Lemma 4.3. Suppose Assumption 4.2 holds and let {w,} be the iterates produced by the update rule with constant learning rate a S 1/25L, and set Y = 1-vpa Define 0₂ = [[wr
Vua
we) we)), T, (w--1 - ",, RR2d, and the potential function Ve as V== 0. PO. + (wt)) (ww() where
1
ppa /uax)2 8 la-
P
20
V/Juxx -
Then for any given å E (0, 1) and all 2 O, the following holds with probability at least 1 - 6 over the randomness in He (here e denotes the base of natural logarithms):
(i) (With drift) Let (r(w)= = fll will 1 then V. S (1-
pa
Vo +
(ávão" V
804?
In el
8
(ii (Without drift) Let (ew)) = (ww) be any general strongly convex functions with A then vpa
V. S
Vo
+
5va0? V/a 8
In eT
Remark: When [6. is sequence of quadratic functions with moving minimizers, Lemma 4.3 provides high probability tracking guarantee for SNAG with distributional drift, which is useful to provide guarantees for Option in Algorithm 2 Note that this guarantee strictly improves the guarantee of stochastic gradient descent with distributional drift (e.g.. (20 Theorem 6)) in the small stochastic gradient noise regime and therefore of independent interest. In particular, for small a, 4
the decaying factor in the first term is improved from 1 μo
2 to 1 - yua the drift term is improved
from A = to A² and the variance term becomes a bit worse (from 2x2 to vp When a is small enough, the variance term becomes insignificant compared with the drift term, then Lemma 4.3 provides an improved convergence rate with high probability. To the best of our knowledge, such an improved guarantee for SNAG with distributional drift is first shown in this work. When there is no drift, Lemma 4.3 also provides a high probability guarantee for SNAG. It holds for any smooth and strongly convex function şi and it is useful to provide guarantees for Option II of Algorithm
yagz
'The notation in Section 4.3.1 is independent of that in other sections, although there may be incidental
overlaps in terminology.
7

---

4.3.2 Application of Stochastic Nesterov Accelerated Gradient to Bilevel Optimization
Inspired by [8 32]. we can regard (x(.) as (x(-) == g( -) in the bilevel setting, and then we have A == for every due to the upper-level update rule and the Lipschitzness of y (z)).. Therefore we can focus the high probability analysis the lower-level variable without worrying about the
randomness from the upper-level. Throughout, we assume Assumption 3.1 3.2 3.3 3.44 In
addition, the failure probability 5 E (0, 1) and e >> 0 are chosen in the same way as in Theorem 4.
Lemma 4.4 (Warm-start). Let { be the iterates produced by line 2 of Algorithm 2 Set a (e)*), g,1 (ua))/40 n. and dr (y) g(zo, y). Then llvito -vlll v [ua e holds with
32 Lo
probability at least 1 8 over the randomness in Finit (we denote this event as Einit) in To = 0 iterations.
Remark: Lemma 4.4 shows that for fixed initialization zo, running SNAG for at most To Ō(E-)) iterations can guarantee that the Euclidean distance between the lower-level variable yinit and the optimal solution y" (aro) is at most Oe)), with high probability.
Lemma 4.5 (Option D. Under event Emit. let {ve} be the iterates produced by Option I. Set a 6(2), 9.1 = (uaa)/+ā,,r and dc(y) = g ( y) = ~ flyy-1a - yfll I|? Then any t E [T) Algorithm
guarantees with probability at least 5 over the randomness in Fl. (we denote this event as Eny that 11ye vI / c/2lo--
Lemma 4.6 (Option II). Under event Einit, let {ye} be the iterates produced by Option II. Set = = N Ö(c-1), I= Ö(c=)), Jg,1 (pa))/+/ a, and Φx(y) g y) when t is for
multiple of (i.e., It is fixed for each update round of Option II so can be general functions).
Then for any 1 [T), Algorithm guarantees with probubility at least ô over the randomness in (f (we denote this event as Eg) that 11ye- - vt S e/Lo.
Remark: Lemma 4.5 and Lemma 4.6 4.6 show that, under event Emit and both option I and option II, the algorithm guarantees that each iterate ye is -cc-cs to the the optimal lower-level variable ył at every iteration with high probability.
Lemma 4.7 (Averaging). Under event Einit n E (Option 1) or Eint n E (Option II), set T Vpa
in the averaging step (line 21 of Algorithm 2) Then for any 2 we have 1| vē l1 and
|lū++1 - Dell S 24L60a.
n²² =: 0.
Remark: Lemma 4.7 shows that after performing averaging operations over the sequence {ye )T the averaged sequence enjoys stronger guarantees. First, each averaged iterate dt is still Oce)-close to the optimal lower-level variable yi: Second, two consecutive averaged iterates (i.e., ÿs and (t+1) ((e))-closs to each other. The stronger guarantees are crucial to control the hypergradient estimation error as described Lemma 4.8
Lemma 4.8. Under event Enai. O EY (Option 1) or Eiit n Ey (Option II), define = m f (Iee E.),, then have the following averaged cumulative error bound:
V
T Σ
5 Bla T(1 3)
55
Lu
2(T 02) S
Li
2(n² + 02)
Σ
E
-1-
5(1 3)
where S denotes the batch size, and o, Lo, Li are defined in Lemmas B.4 and B.6
Remark: Lemma charactrrizzes the upper-level hypergradient estimation error under the good event that the lower-level error can be controlled. One can choose hyperparameters appropriately such that the cumulative error (i.e., LHS) grows only sublinearly in terms of T,, which is important for establishing the fast convergence of our algorithm.
Experiments
Deep AUC Maximization with Recurrent Neural Networks. AUC (Area Under the ROC Curve) (36] is a critical metric evaluating the performance of binary classification models. It measures the ability of the model to distinguish between positive and negative classes, and
8

---

Trids AIC Pyoch
Teat AdC vs. Boach
2.40
50007
333
Fuening mine
(a) Training AUC
(b) AUC
(c) Training AUC'ss running time (d) Test AUC vs. running time
Figure I: Results of bilevel optimization on deep AUC maximization. Figure (a), (b) are the results over epochs, and Figure (c), (d) are the results over running time.
is defined as the probability that the prediction score of a positive example higher than
that is negative example [35]. Deep AUC maximization [53] 72] can be formulated as a min-
max optimization problem [53] min (a,b)e32 max.eR f(w, a, b, = Ex [F[[ a, a;; z]],
where F(w, a, b, a; = (1 (h(ww - [- + r(h(w; x) b) + 2(1
w denotes the model parameter, 2 = (æ,c) c) is the random data sample (x: denote the feature vector and c C {+1,- -1} denotes the label), h(w, x) is the score function defined by neural network, and Pr(c 1) denotes the ratio of positive
a) (rh(w; x -===-1
ax)
samples in the population. This min-max formulation is an special case of the bilevel problem with g = ff in (T) which can be reformulated as the following:
min (a))E
E. [2(F(w, a, b, a (w, a, =); s.t., a a"(wa,, E arg min oER
-B a, b, oz 2)
where (w, a. b) denotes the upper-level variable, and denotes the lower-level variable. In this case, the lower-level is a quadratic function in terms a and is strongly convex, and the upper-level function is non-convex function with potential unbounded smoothness when using a recurrent neural network as the predictive model.
We aim to perform imbalanced text classification task and maximize the AUC metric. The Deep AUC maximization experiment is performed on imbalanced Sentiment140 [31] dataset (under the license of CC BY 4.0), which is binary text classification task. Specifically, we follow [73] to make training imbalanced with pre-defined imbalanced ratio (r), and leave the test set unchanged. Given we randomly discard the positive samples (with label 1) in original training set until the The imbalance ratio r set to 0.2 our experiment, which
portion of positive samples equals means only 20% data is positive in the training set. We use two-layer recurrent neural network with input dimension=300, hidden dimension=4096, and output dimension=2 for the model prediction.
We compare with some bilevel optimization baselines, including StocBio 44 TTSA [41] SABA (1], MA-SOBA [12], SUSTAIN (6)) VRBO [7] and BO-REP (38) We show the training and
test AUC result with 25 epochs in (a) (b) of Figure I and running time in (c), (d) of Figure Our
algorithm AccBO achieves highest AUC score among all the baselines over epochs and running time. The running time figure shows Ac converges to a good result faster than other baselines. The detailed parameter tuning and selection are included in Appendix G
Data Hypercleaning. The Data hypercleaning task tries to learn a set of weights À for the corrupted training data Drr, such that the model trained on the weighted corrupted training set can achieve good performance on the clean validation set Deat, where the corrupted training set Dtr t= {x; Tt and the label Di is randomly flipped to of other labels with probability 0 hyper-cleaning can be formulated as a bilevel optimization problem,
1. The data
min
Σ L(w" (A):E), s.t. w" (A) E arg min SED
Σ o()))[(w;)) (1) + +cl/a|)" (5)
Deal
Dun
T
GED.
where w is the model parameter neural network, and (x)) - is the sigmoid function. We perform bilevel optimization algorithms on the noisy text classification dataset Stanford Natural Language Inference (SNLI) [8] (under the license of CC BY 4.0) with a three-layer recurrent neural network with input dimension=300, hidden dimension=4096 and output dimension=3 for the label prediction. Each of sentence- pairs manually labeled as entailment, contradiction, and neutral.

---

Trais des vs. Fpush
Textl Acc Fyech
Tran
0.03
2.4
1:33
300
5.00
044
035
20307
60
10
L62 150 270
10
15
ratang Oiee
(a) Training ACC
(b) Test ACC
(c) Training ACC vs. running time
(d) Test ACC vs. running time
Trate Acciss Broch
That Ace ves Saach
Acc vo, rennieg
6:65
Bac
141
6.0
040
Bods
6.33
16
15
(e) Training ACC
(1) Test ACC
Training ACC vs. running lime
(h) Test ACC vs. running time
Figure 2: Results of bilevel optimization on data hyper-cleaning with 0.1. Figure (a), (b), (c), (d) are the results with noise rate p = 0.1 where (a), (b) are the results over epochs, and Figure (c), (d) are the results over running time. Figure (c), (f), (g), (h) are the results with noise rate p 0.2.
Specifically, the label of each training data is randomly flipped to one of the other two labels with probability p. We set = 0.1 and p = 0.2 in the experiments, respectively. We compare all the baselines used in the deep AUC maximization experiment. Different from the formulation 4 for the deep AUC maximization, the lower-level function in (5) is not quadratic function of the lower-level variable. Therefore we choose Option in Algorithm i.e., periodic updates for the lower-level variable. The results are presented in Figure 2 (p = 0.1 and
0.2). Our algorithm AccBO exhibits the highest classification accuracy on training and test set among all the bilevel baselines, and also shows high runtime efficiency. More detailed parameter tuning and selection can be found in Appendix G. All the experiments are run on the device of NVIDIA A6000 (48GB memory) GPU and AMD EPYC 7513 32-Core CPU.
6 Conclusion
In this paper, we propose a new algorithm named AccBO for solving bilevel optimization problems where the upper-level is nonconvex and unbounded smooth and the lower-level problem is strongly
convex. The algorithm achieved Ö(e-²) oracle complexity for finding an e-stationary point when the lower-level stochastic gradient variance is Oc)), which matches the rate of the state-of- sfate-of-the-ar single-level relaxed smooth optimization [56) and is nearly optimal in terms of dependency on e (2).
Limitations. There are two limitations of our work. One limitation of our work is that the convergence
analysis for the Option I of our algorithm relies on the lower-level problem being quadratic function: only under this case the algorithm becomes a single-loop procedure. Another limitation is that we require the lower-level stochastic gradient has variance O(c). It remains unclear how design single-loop algorithms for more general lower-level strongly convex functions and get rid of the small stochastic gradient variance assumption for the lower-level variable.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. We would like to thank Tianbao Yang and Qihang Lin for helpful discussions for the quadratic function with distributional drift in the earlier version of our paper. This work has been supported by the Presidential Scholarship. the ORIEI seed funding, and the IDIA P3 fellowship from George Mason University, the Cisco Faculty Research Award, and NSF award #2436217, #2425687. The Computations were run on ARGO, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https://orc.muu.ed.
10

---

References
[1] G Anandalingam and DJ White. A solution method for the linear static stackelberg problem using penalty functions. IEEE Transactions on automatic control, 35(10): 1990.
[2] Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1-2):165-214, 2023.
[3] Mahmoud Assran and Michael Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings. arXiv preprint arXiv:2002./2414, 2020.
[4] Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated stochastic gradient method. Advances in neural information processing systems, 32, 2019.
[5] Necdet Serhat Ayhat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. Robust accel- erated gradient methods for smooth strongly convex functions. SIAM Journal on Optimization, 30(1):717-751, 2020.
[6] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- fions research, 1225-11227- 2015.
[7] 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.
[8] Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher 1) Manning. A large annotated corpus for learning natural language inference. arXiv preprint arXiv: 1wXivv:508.000 1508.053200 2015.
[9] Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
[10] Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301.007// 2023.
[11] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 14-25294-225077 2021.
[12] Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306. 12067, 2023.
[13] You-Lin Chen, Sen Na, and Mladen Kolar. Convergence analysis of accelerated stochastic gradient descent under the growth condition. Mathematics of Operations Research, 2023.
[14] Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex opti- mization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02854, 2023.
[15] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 2022.
[16] Michael Crawshaw, Yajie Bao, and Mingrui Liu. Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data. In The Eleventh International Conference on Learning Representations, 2023.
[17] Michael Crawshaw, Yajie Bao, and Mingrui Liu. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. In Thirty-seventh Conference Neural Information Processing Systems, 2023.

---

[18] Ashok Cutkosky and Francesco Orabona. Momentum based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
[19] Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under time drift: iterate averaging, step-decay schedules, and high probability guarantees. Advances in neural information processing systems, 34:1 1559-11869 2021.
[20] Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under distributional drift. Journal of Machine Learning Research, 24(147):1-56, 2023.
[21] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 01-26698-267111 2022.
[22] Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):1992111, 1990.
[23] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
[24] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.06570, 2023.
[25] Matthias Feurer and Frank Hutter. Hyperparameter optimization. In Automated Machine Learning, pages 3-33. Springer, Cham, 2019.
[26] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. International conference on machine learning, pages 1126-1135. PMLR, 2017.
[27] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages 1568-1577. PMLR, 2018
[28] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-253 -2366,, 2013.
[29] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99, 2016.
[30] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.000 088...222466 2018.
[31] Alec Go, Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervi- sion. CS224N project report, Stanford, 1(12):2009, 2009.
[32] Xiaochuan Gong, Jie Hao, and Mingrui Liu. nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In Forty-first International Conference on Machine Learning, 2024.
[33] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. arXiv preprint arXiv:2202.03397, 2022.
[34] Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266. 2021.
[35] James A Hanley and Barbara J McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1):29-35) -6, 1982.
[36] James Hanley and Barbara McNeil. method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology, 148(3):839-844 1983.
12

---

[37] Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. Advances in Neural Information Processing Systems, 36, 2023.
[38] Jie Hao, Xiaochuan Gong, and Mingrui Liu, Bilevel optimization under unbounded smoothness: A new algorithm and convergence analysis. In The Twelfth International Conference Learning Representations, 2024.
[39] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1): 2489-2512 22, 2014.
[40] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 7735-1780, 1997.
[41] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 137)))447-180, 2023.
[42] Bin Hu and Laurent Lessard. Dissipativity theory for nesterov's accelerated method. In International Conference on Machine Learning, pages 1549-1557, PMLR, 2017.
[43] Quanqi Hu, Zi-Hao Qiu, Zhishuai Guo, Lijun Zhang, and Tianbao Yang. Blockwise stochastic vuriance-reduced methods with parallel speedup for multi block bilevel optimization. In International Conference on Machine Learning, pages 13550-13583. PMLR, 2023.
[44] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference machine learning, pages 4882-4892. PMLR, 2021.
[45] Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34:2771-2782, 2021.
[46] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems (NeurIPS), 34:30271-30283, 2021.
[47] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[48] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18113. PMLR, 2023.
[49] Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753, 2023.
[50] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programminng 133(1-2):365-39) 2012.
[51] Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assumptions. arXiv preprint arXiv:2304. MoXi::230413372,00 2023.
[52] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35:17248 17262, 2022.
[53] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. ICLR, 2020.
[54] Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-effcii distributed gradient clipping algorithm for training deep neural networks. Advances Neural Information Processing Systems, 35:26204-26217 2022.
13

---

[55] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. International Conference Machine Learning, pages 6315-6315. PMLR, 2020.
[56] Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal non non-convex stochastic optimization under generalized smoothness. arXiv preprint arXiv:2302. 02.30200060.,... 2023.
[57] Liam Madden, Stephen Becker, and Emiliano Dall' Anese. Bounds for the tracking error of first-order online optimization methods. Journal of Optimization Theory and Applications, 189: 437-457, 2021.
[58] Yurii Nesterov. A method of solving a convex programming problem with convergence rate (1/k2). In Soviet Mathematics Doklady, volume 27, pages 372-376, 1983.
[59] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pages 113-124, 2019.
[60] Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303.0080 2023.
[61] Shoham Sabach and Shimrit Shtern. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-666 660, 2017.
[62] Han Shen and Tianyi Chen. On cenalty-based bilevel gradient descent method. arXiv preprint arXiv:2300..0 05 185, 2023.
[63] Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXivv 123, 2022.
[64] Quoe Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv: 2019.
[65] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[66] Sharan Vaswani, Benjamin Dubois-Taine, and Reza Babanezhad. Towards noise-adaptive, problem-adaptive (accelerated) stochastic gradient descent. In International conference on machine learning, pages 22015-22059, PMLR, 2022.
[67] Luis Vicente, Gilles Savard, and Joaquim Júdice. Descent approaches for quadratic bilevel programming. Journal of optimization theory and applications, 81(2):379-399, 1994.
[68] Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pages 161-190. PMLR, 2023.
[69] Douglas White and G Anandalingam. A penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3:397-419, 1993.
[70] Craig Wilson, Venugopal V Veeravalli, and Angelia Nedić. Adaptive sequential stochastic optimization. IEEE Transactions on Automatic Control, 64(2):496-509, 2018.
[71] Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 1370-1162,, 2021.
[72] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In Advances Neural Information Processing Systems, pages 451 -559, 2016.
[73] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang- Large-scale robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification. In Proceedings of the IEFE/CVE International Conference on Computer Vision, pages 3040-3049, 2021.
14

---

[74] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511- 15521, 2020.
[75] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference on Learning Representations, 2020.
15

---

A Technical Lemmas
In this section, we will introduce a few useful lemmas. The following technical lemma on recursive control is crucial for providing high probability guarantee of the lower-level variables Yr and Dr in Algorithm 2 at anytime. We follow similar argument in (20, Proposition 29] with slight generalization.
Lemma A.1 (Recursive control on MGF). Consider scalar stochastic processes (Vs), (V(2). (V(2). (Dr,), (Dr,2) and (Xx) on a probability space with filtration (Hr), which are linked by the inequality
Ve+1 S an + Dr, Vi Via + DEav Viz Xx Kit
for some deterministic constants 04 (-o0, 1] and Ki R. Suppose the following properties hold.
Vi, Vi, and V122 are non-negative and measuauue..
Dra is mean-zero sub- Gaussian conditioned on H4 with deterministic parameter ds, and
Vi. S V4 for 1,2:
Elexp(ADr.)) H4] exp(X>o?/2) for all X
X2 is non-negative and sub-exponential conditioned on Hi with deterministic parameter Ve: Elexp(AX,)) HH,] s exp(Aus) for all OSAsi 1/ve.
Then the estimate
E(exp(AV4+1)] exp(A(er + (1)
holds for any À satisfying 0 S X S min { ([( 20r }
Proof of Lemma A.I For any index t 2 and any scalar À 2 0, the law of total expectation implies
E[exp(AV+++) s E exp(A(an,V + Dr. VL,1 + Dr2y Vi2 + Xx + ki)) +x)))
= exp(Asx E Texp(Acr.V)) V:)B Texp (>(Dr. /
Via + P../Viis exp(AX,) [..]]
Hölder's inequality in turn yields
E Texp(AAx,V Vi)TE exp (* (DDII Via Dra Vi2) exp(AX,) Hel
< E exp (2x (D.. V/, + Dr.v/Vi Ho E (exx((2XXX)) | HH4]
S v exp (2AR(o?V', + V(V())) exp(2Arr)
S exp (o2 + Vi) exp(Ar;)
provided 0 A 1/20,, where we use Vi, S Vj for = 1,2 in the last inequality. Therefore, under the condition that
1- -+;
1
0 s5 min
2( + oz)" 20
the following estimate hold for all 2 0:
E[exp(AV[+1)] & exp(A<;) [exp(Aax Vz) exp (A² oz)V; exp(Xv:) = exp(A((e + Kx)) exp (A(a: + A(o + v3)
<exp(X(1 + m4) E(xxp(() (.2))/
where the last inequality follows by the given range of X. Thus the proof is completed.
Next, we introduce the following Young's 's inequality beyond Fuclidean norm cases. This lemma serves an important role when dealing with distributional drift for high probability SNAG analysis.
16

---

Lemma A.2 (Young's 's inequality). For any vectors 01, 02 RR, positive semidefinite (PSD) matrix Q Rdxd and scalar > 0, it holds that
||ll + U2 la s (1 l)ll + (1+ 1
Proof of Lemma
A.2 By definition of || Ilq. we have
||0 U/ (#1 + 22) (vi v2)
(6)
|| ||2 l + 2v Q
Since Q E Rdxd is PSD, let Q UUT be the Cholesky decomposition, then
20 Q = 20j UUT U2 = 2( v1) TU (T))))
< v1l1 JUTr2l'
(7)
= =clla1lã
- 1
where Young's incquality and definition of || ||o for the second and third lines, respectively. Combing 66) and gives the result as claimed.
B Auxiliary Lemmas for Bilevel Optimization
In this section, we provide important properties of the objective function & in bilevel optimization problems, as well as characterizations (such as variance and bias) for stochastic hypergradient estimator V (xx y/: () based on Neumann series, For readers' convenience, we only list the results here and defer the detailed proofs to Appendix F
Lemma B.1 (Lipschitz property, 38 Lemma 8)). Under Assumptions 3.1 and 3.2 y (x) is (1g./11)-
Lipschitz continuous.
Lemma B.2 ((Lo, () smoothhess, 38 Lemma 9]). Under Assumptions we have
3.1 and 3.2 for any x.
(VV(()) (=)))) S (I I'll
||x-
V
2(1 2(1
(1,1//) + L3 1
where (Lo. smooohhhsssssss constant Lp and L, are defined as
12 [1,00 Lz,1 laatso la. (L + L.,1 4,.0
19.14.22 + 19.21
Lo =
and L = +V+
1
L
112
112
112
Lemma B.3 (Descent inequality, Then for any x, x' we have
38 Lemma 10)).
Suppose Assumptions
3.
and
3.2 and
3.2 hold.
(xx) (
Lo
L1
V1(2'))
|/
if 11x-x111
1
2
2(1 + 12, (T?, + I2
Lemma B.4 (46) Lemma B.I]). Under Assumptions estimate of the upper-level objective satisfies
3.7 to 3.4
the bias of the stochastic hypergradi-
10.14.00
(1-
I Vxx v) EE
g.1
where Q is the number of samples chosen to approximate the Hessian inverse. Moreover, we have
3 #
[ fz <
[(o + (,)0 +22,,) + o o =²
Here define || V V Qu for any vector R² and PSD matrix iddd
17

---

Lemma B.5. Under Assumptions 3.7 to 3.4 we have
(2(2)) IV v+)=))
(L + Lx,illV( (x)))
where constant L is defined as
== 122,0 + Lgg11 121
+ 11 (Iy, + 1,0) + 1.0 Ubg. + 1922 S Lo-
11²
Lemma B.6. Under Assumptions 3.7 3.4 we have
(i) For any fixed y RR and any a. x' TRd,
Eg (el
". (Tg [ - 2/11.
(ii) For any fixed æ E Rd and any y.y' R
(eIlV[(E - v' E)12 S (L) 1 1/1
In the above expressions, we define To and Tn
Too = { [0a,0 Lnn,1
Lx, Ir..4g,1
|1 110-8' 5/ (z))1 (()))
[Iu,00
6Q
17.09.112220 9.20
) 1/2
fa (nil + 2 + 22. (1 -u)² n1)
2p
n2
I, = 11 Tea,1 (1)
Note that in Lemma B.6 constant Ly depends on the value of Iyy - aoy-y"(an (x)]l- When we consider this Il. which are both as small as O(e) (and thus bounded) with high probability by Lemmas 4.5 to 4.7 In other words, we can treat this term as another constant for our algorithm and analysis.
term in Algorithm 2 turns into 1/y, yr or 1
C Proofs of Results in Section
For convenience, we will restate a few concepts included in Section 4.3. here. We consider the sequences of stochastic optimization problems
min (e(ww) wERd
(8)
indexed by time t E N. We denote the minimizer and the minimal value of d, w and di and we define the minimizer drift at time / to be A, == ||w! w/+ With slight abuse of notation, we consider the SNAG algorithm applied to the sequence { where T' is the total number of iterations:
we ((w w2-1)
Wi+1 = we + >w: - w - agi.
where 9. Vol (Zti is the stochastic gradient evaluated at o, with random sample &.. Define Dt. (zx) as the stochastic gradient noise at 1-th iteration. Define H, = oEEI...., 1 as
the filtration, which is the r-aleerra generated by all random variables until 1-th iteration. We will make the following standard assumption, illustrated below +l
Assumption C.I.
The sequences of time-varying functions satisfy that, each function Φr Rdd p-strongly convex and L-smooth for some constants p., L 0.
Assumption C.2 SSub-Gaussiar drift and noise). There exists constants A, > O such that the following holds for all 2
(i) (Drift) The drift A? is sub-exponential conditioned on He with parameter 2
(ex)(AAA) Hi] S exp(2A2) for all 0 X A
'Note that Assumptions C.1 and C.2
concrete than that in Section 4.3.1
18

---

(ii) (Noise) The noise En is norm sub- Gaussian conditioned on H4 with parameter a/2:
Pr Pr 2 e H.) - eexp(-2g -2a) for all 0.
The following lemma characterize the one-step improvement for stochastic Nesterov accelerated gradient method. Although part of our analysis is similar to [33 51, our final goal is quite different: we aim to derive careful formulation (see (13) such that we apply Lemma A.1 to recursively control the moment generating function of V, with distributional drift, thus leading to a high probability
bound for V, at anytime (see Lemma C.5 while [13 5 without distributional drift.
only show the convergence in expectation
Lemma C.3 (Distance recursion, with drift), Suppose that Assumptions C.I and C.2 hold. Let {w:} 3 be the iterates produced by update rule b
with constant learning rate a S 1/2L and set constants
7, P O, and matrix P 2ddx2d as
/aa
1
VBa - V (1 (--vua)² 20 la-
7 1 Vua
0² = 1 vua, P=
(10)
20 [pa-1
Define 0g =[wwe - wi) (W - wt) -
E 2d also define the potential functtion and U1,1 14,2
as
=, P0 P0, + (w(e)) - (r(w)),
100
W2 W
w7
24,2 =
1|2 w0
21 We
(11)
Then for all 1 2 0, it holds that
Wr+1 wi] W/. wi
W141 w/
P
+ (.(ww)))) (c((2))
Wt wi
(12)
S ppVV - - La) + La
||r|1??
2
Specifically, if (ww) f1l - we 11?, then we have
V411 s (1 1
vua
Ve + (1
pace
2ua((1 - La (a)(ue,,, V
11 110, - -
2
4
(13)
2a 2a
v/a
|| well + a(1 + La)
20μ2?
a11
Lu) Ex)
|1/11
+
1 + Via
2/20
2
jacE
Proof of Lemma
C.3
We first apply Lemma A.2 with
Wi+1 - w Wt w 1 01
Wi411 w/? Wt
W
w ++ w
81 + 1/2 0++1
U/2
Q = P
w.
w
to obtain
V-1 = 0. P0,+1 + 0e+1 (w++1) ) De+1 (wi+1)
+ tace
We+1 We wy
We+1 w/
+ 1
4
[wi
wi+1
Tw wi+1
+ ( - (
We w
Vuaa
wi+1
ang wi+1
+ y jucx
Wr+11 w/ We we
P
Wi+1 wi
+ (w0++))))--- (10())
1
Wc - wi
(4)
+ +++1(We+1) (1+1(w((1)
(0e(wi+1) (e(w))
_ Viaa
Tw
w
Tw0 w
w
w
w
(B)
(C)
Now bound terms (A), (B) and (C') individually.
19

---

Bounding (A). Let us define vector We E R and matrices A E R2dx2d
B E R2dxd as
+
wi = (o)(
la. B
0 x La.
By 9 we have
[[ - -wi) wi)T, (wi - [ Adt + B(wir + Ee)
(14)
Since Φ1 is u-strongly convex, then
(e(we) - (z())) 2 (Vor(zt), Wi ze) + H
マタ ooy - zel1?.
(15)
By L-smoothness of de and the fact that 12+1 2t- agg, we have
L
de(2)) - (1)+++))= 2 (V), 2
wH+1)
|1u+11 1112
La²
= =((Vv((z).9)) 2
119h112
(16)
)| + (VoV =]]\Vo(<>)| La²
+ ||ex113)
= -2 - La) La²
||ee]] a(l La) (V)
2
where we use 9: (2)( + E, in the second equality. Noting that by 9 we have
wx+- - ž = - - wi) ) + (wv-1 wr),
and combining 15 and T6 we obtain
(e(we) (e(w)+1) 2 (Vo((z)) wi - zx) + H ||we zel1
La)l (1)(21) - La²
+ 2
(2
||E + - (17)
2
0g Wi
La²
X1
||r|| + a(1 - La)(Vo((z))))))
Wi
2
where matrix X, E R3dxxdd is defined as
mn?
un? un2
-7
X
= 2 u7²
?
8 la.
?
al2 La)
Then applying the strong convexity of Φb again gives
(v(w)) - 00(x)) 2 (Vo((z)), w - -21) + /
2 : - 2z 12.
(18)
Noting that
" - 2, = (w] - w/) 7(1 - wi) + (Ww - w
-11 + 7) (wi w;} + 7 (w w,), )
and combining 16 and (88) we obtain
(ww) (r(w++1) 2 V (z)( wi =2a) 11 Illu3 1
La²
(2 - Lai)l (2))2
+ a Lo( (19)
2
0o T
0.
La²
X2
|| + aa =V))
We
We
2
where matrix X, 3ddx3d is defined as
n(1 + 7)2
-1m(1 + +7)
-(1 +
X₂ = 2
-117 +7)
un2 7
2 Lg.
71+
o(2 Loa
20

---

Next, we multiply
17p by p² and (9) by 1 - p², then sum them up to get
(we( (((w;)) (ote (1+1)) (w(
0c [W]]
0₁
Lax2
(20)
(p² x1 (1 xx)))))
||ee|l + a(1 (V) ex).
Wi
By 42 Section 3.1]
(see also [5]
Corollary 4.9],
Theorem 2.3]), we have the following fact:
PA
p'P
A AP
(p² X + (1 - ) 30
(21)
PA
PA
B PB
P
which, combined with 20 yields
W(+1 :/
P W++1 wi
A0 P8,
W/=
0
A
PA PA PA
p²P
PB
0i W
t B PBe.
W/
B PB (0²x1 + (1 X22
0:
+
a
]|sx|12
Wi)
2
- (666(w6+1) - )c(wx)) + (o)(((u)))) - di (w:)) -a---aa1-aaaa- (o) st) + a+ La
||,.
2
where the first incquality uses (14 and (2T). along with the fact that B T PB = (a/2) & La and hence
Amax (B T PB) = az/2; and the last inequality follows by (20). Rearrange the above inequality and by definition of the potential function Vi, we obtain
Wh+1 - wi We w
Wt-1 wit W1
P
+ +w((++1) - (l(()
w
(22)
5 Lol(aa) + a(1 Laa
||
Now recall that in (8) our objective function has the form of (w) f1l -wt will? 11? hence (2.( 1(2: wx)) Plugging this into the above inequality gives
Wi+1 wi]
Wt+1 wF] + ve(ww+1) - =w(()
P
We - wi
Wi - ww
< 22V pa(1 La)( =() + a La²
||e||1
2
a(1 + La)
PV ppa(1 Lai wi uual1 -a)(z(-;,a)) w),
||r/1 (23)
2
1/4 1 - -wil
=\ 22uua(1 La) (u)) /
20 a(1 - La)( 1 /ua
|| well + ax1 + Ia)
+ Vua
2v20
2
where 44n and 412 are defined
Wr w
21 Wt
U4,1
1 =wll
U1,2 =
1/ we
Therefore, we conclude that
v pa
pv 24uaa(1 La)) Lo), Ex) V // |1 w.'l
(A) s 1
4
2a 2a
a(1 (u),,))) 1 + /uce
a(1 + La)
11 10el-ell
||ee11
1 1 / jaa
2 202xx 2xx
(24)
3 jaa
V1 +
22 - La)
11 Illur will
4
2 2a
1 vua
1| - -well + a(1 + La)
a(1 La)
||E
1 + v pma
2xx
2
21

---

where the last inequality follows from the definition of and simple calculation
1 11+ 4
pacc
(1+
-²
1+
paa
(1 vpa
1 3 /
Bounding (B). Recall that under distributional drift, the objective function in (8) has the form of (1(w)
f w wil I12, then we have
2
(B) Φ (wr+1)= @c+1(W]_1) (1 1 viax
(0c(w(+1) - (x({))
4
Vua
-
(01+1(W(41) 1041111111)) (e(we+1) + (w()))
4
1
1
v vua
(11011 w/-111 -11u211 we 12]l)3)
2
1
1+
y /ua
| 11l1ulll14441 - wi + w1+1 wital
2
/
1+ v /aa
(2 w + 111f41 wt l)
2
Since Φ1+1 is j-strongly convex and matrix P PSD, then
V4+1 = 0,4 P0 + 10+1 - (((((+)) 2 00+1(w++1) - (e((((+1)
|ur+1-wital S / / 2
W++1 wi+1ll
Vi+1-
Plugging the above fact back into the upper bound for (B) gives
(B) S 1 2
Vua
2
/V-n + ++))
1 +
A.
2
(25)
2
(1+
via
V4+1+ + P
Vua
A?
4
4
Bounding (C).
For this part, we handle the distributional drift. By definition of P in TOP. we have
(C)
1
4
"
wi+1 w
1
Id
(Vμa- - L
w
w
V
2x
(Vrra 1)Ia (1 L
w wi+1
(26)
p
+
A?
2
Vμa
where in the last equality we the basic algebra of block matrix multiplication and the definition of
A, | - wi+1l. - ||.
Final Bound for Vi+1. Now we are ready to derive the upper bound for V4+1 Combining 24)
25 and 266 together yields
Ve+1 < (A) + (B) + (C)
1
3. /aa
V.
2uia(11 La)(ue,,
1 Iw:
will
2 2a
a=1 Ea)(ue2,
1
pace
1/2 well
+
a<1 + La)
||
(27)
+
ya
2/2n
2
+ 2 1
jaa
V4+ +
1+
pa
2
A,a
Vpa
For simplicity, we define D as the following
3 pa
22 La)(un,, 11 Illu will
D =
Ve +
4
2/v/2ox 2x
1 1+ vpa
|| - will + a(1 + La)
Vua
2
a(1 La) (u),u,2,
||Ee|
+ 1
+
A3
1 + / jua
2/20
2
8
v vaa
22

---

Hence 27
turns into
(+ vuai 1/10)) /V++i DS
V4++ V2
Solving the above inequality we get
Vua
+ +V ( /2n
Vuaa
VV+1 - 2 V2 [1
[1+
+ +DD
4
4
(1+
vpa
+ VD
Then application of Young's inequality reveals
v/aa
(V2ud, (1 v(o))
Ve+1 _
1
D +
1
4
Vpa
1+ Vpa
{(1
///
Vi [- [-22ua(1 Lax (un)
1 wlw w./
1
4
2pv2a 2a
1 + vpa
||: will + a(1 + La)
+ 1 ( (1+
Vua Ja
2 /uaa
a(1
La)
(ue,2
|
+
A
1
Vpa
2/
8
1 vpa
2
+ 1 +
Vpa
4
1
vua
V +
1 1
Vua
2ua (u) Ex)
1
l will
4
2
2cx
1 + vpa
a(1 + Taa
a(1 La)(ua Ex)
1| -vell
||ee|1
+ Vua
2/2cx
2
+ p
1 +
1
pa
A + (1
4
2
11 Vua
4
8
vpa
Vua
where we plug in the definition of D for the first equality. Since the learning rate a S 1/L L and thus paa S 1, then we have
pa (1
pa
125
1+ Vua )
uaa
125
1 + 4
I
1+
S
8
VIa
32 / /ao
4
8 \/pa
Therefore, we finally conclude that
V4+1 S
V,
1
v paa
//uaaal La) La)(u,,
V
11
Iluss -wil
2
2a
1+ Via
|| will a(1 + La)
20
a(1 La)
(u,,2,
||E/|22
+
1+ Vpa
20
/ua
which is as claimed in 13
When there is no drift, the following lemma holds for any general strongly convex functions 6 in Rd Lemma C.4 (Distance recursion, without drift). Under the same settings as in Lemma C.3 with (e(w) (ww), and w w², where σ(w) can be any general strongly functions in R.d. We redefine
U4,1, 24, as
Ve((E)) Vo(w*) U1,1
Vo(2.) V
[V)(w)) - V Vo(w*)|
Ur =
[Vo(z.) V
(28)
Then for all t 2 0, it holds that
V4+ < (1 VucvVV 2 La La) La) (a)(1-L))uu,,1
1 / Vo.( - Vol(w")]
T
2
(29)
20
+ vua
a(1 + La)
a(1 La)(ur,,
[or(zz) Vol(w;)]
| 12
1 + ypa
2L
23

---

Proof of Lemma C.4
By 12 in Lemma
C.3
with @r(w) = d(w) and wt = w", we have
La²
V4+1 $ V a(1 (or
||=112
2
a(1 + La)
p'V a(1 La) vor(w)) Et) a(1 La) Vor(w)),
||E|||
= (1 Vua)Vi / 2 V La(1 La) La) Ex)
Vor(w)) - vor(w")]
L 2
2L a01 - (u) 61)
+ p
a(1 + La)
||rl1
Viaar
21. 2nx
2
Hence the proof is completed.
The following result shows the first part of Lemma 4.3 To the best of our knowledge, this is the first high probability guarantee with improved rate for SNAG under distributional drift.
Lemma C.5 piibb-irobabblityy distance tracking, with drift). Under the same setting as in Lemmal C with a S 1/25L, for any given d E (0, 1) and all t [T], the following holds with probability at least 1 - 8 over the randomness in He:
paa 4
55v02²
80A
eT
V1
Vo+
In
(30)
V/l
a
Proof of Lemma
C.5
We will invoke Lemma A.
to show the results. To apply Lemma A.I
we first
need to show the following two facts:
1 + Vua
Fact (I)
wIll S VVz & Fact (II)
|| well S VV. (31)
2
2v
Fact (I) verification.
Since de is j-stronglyy convex and matrix P is PSD, then
V 0. P0, + (w:) (.(w)) 2 (w,,) - (x(w))
14 w/ o 1|
V 1w will VV.
Fact (II) verification.
By definition of matrix P and simple calculation we have
1
Vv2
0. Pd: = V
[[ - w:) + (Vua 1) -w
2a
11
(ua) - (.,1)) + vua(ws - wz)il
2a
2a (1 Vua)lluu w1-1ll /
/ Klleer - will
2a (1 Vuaa)|lu wi-il Vv.
Rearrange the above inequality, and recall the update rule of stochastic Nesterov accelerated gradient method, have
2 well = >| we w - 27 2x
2
VV.-
VVe.
pa
1+
where for the last equality we use the definition of y as in
10 Rearrange it gives
31)
By Lemma C.3 and the choice of S 1/L, we have
jia
V1 + 1 Vua )
V2 LL) -E6)
1 we - will
Ve+1 S
2
4
(32)
2 20
1 + vpa
+ 20
+ + //a
a<1 La)(ue,2 -Ex)
| - well + alle
2/20
jaa
24

---

there exists an absolute constant 2 such that for all t 2 0, ||=/|| sub-exponential conditioned on H, with parameter co and E, mean-zero sub- Gaussia conditioned on Hd with parameter ca [20] Theorem 30]. For convenience we simply let c here. Thus (ut,1, - mean-7ero sub- Gaussin conditioned on Hi with parameter a, and A? is sub-exponential conditioned on H, with parameter A by assumption. Hence, in light of (32).
Note that under Assumption C.
apply Lemma A.1 with
1 11100-- - w
(1+ +
He. = -He = V1,
Vi =
Vi,2
|| w/l?
2
8a
1+ vua
1+ vua
2p1/2a
D1,1
(2 Lax) (u,,1 -Et);
D1,2
a11 - (La)ua) -82),
4
Vpa
X, = 1 11 VpQ
20μ
Vua
allEr11²
a, =1=
K₁ = 0,
Vua
2
Vuaa
1+ Vua
2 2a
01 (1+ 4
22uaa(1 Lajo,
02
a(1 La)o,
+ vpa
(1
vua
pa
20p 2
11-
a0 +
4
V/aa
yielding the following recursion
(N((1+
Vua
20
(2(1-
vua
E[exp(AVe+1) S exp
ao +
E
exp
>
Vi
4
vua
4
(33)
for all À satisfying
0 X min
125a
5a00 / /
+ 40p /pa
We then apply 33
recursively to deduce
(1- 11-Vrn) ) Vo +1 ((1+ Vua
Vua
a0² + 20
V/a
Elexp(AV)+1)) exx
4
Via
4
< exp
A (1- je
Vo + 4
11
v/ac 4
a
0²
804
4
Vua
for all À satisfying
0 S x < min
/25a./aa pao?
5000 40p / /pa
A2
Moreover, setting
5
80A
V/
a
and taking into account S 1/25L, then we have
(1+
p/a
804
0² +
<
Vua
a
and
2
< min
5 V + 8022/a
125a / 2
5002 + 40 1
Thus we obtain
1)]
-11 - Vuo pax
(1-
E exp
A Vi
Vo
< exp(>v) for all 0 0 X S 1/v.
Taking À 1/v and applying Markov's inequality and union bound completes the proof.
25

---

The following result shows the second part of Lemma 4.3
Lemma C.6 (High-probability distance tracking, without drift). Under the same setting as in Lemma C.4 with a I 1/25L, for any given E (0, 1) and all t E [T), the following holds with
probability at least å over the randomness in He:
pa
5va0²
eT
Vi 1
Vo
In
(34)
8
Proof of Lemma C.6
First it is easy to verify that
+ ypa
TV 2
VVr(w,
Vvn)(w))))) VV.
and
[Vd((a)) - Vol(we)l S VV..
2Lv2a
Then we apply Lemma A. to obtain the final result. the same procedure in proof of Lemma
We omit the detailed proof here since it follows
C.5
D Proofs of Results in Section 4.3.2
We first present the following algebraic fact under suitable choice of parameters.
Lemma D,1 (Parameter choice, informal). For any given ō E (0, 1) and any small c satisfying
1/3
170
32edo 9.1 max
0g11 do }
g.1 ō
E
(35)
6p2
we set parameters a, 3, 17, T as
1222
0 do
1 - (1-8),
T = 4do
1-3- = 170 64L 9.1 In(P)'
min
(1-3),
a
0g = Vuaō 9,1.
7/E
(36)
where is defined in Lemma B.4 and dg and P are defined as
do = (
inf (x), wERdx
P
170 64edo L0
g.1
max
1..1 σ
})
(37)
6p123
0g.1 do
Then the following holds for all L E [T]:
40x22 g.1
160
eT 2²
9.1
+
1ºa
8
64L3
Proof of Lemma D.I By Lemma B.1 Thus in our bilevel setting, choose A n/..1 / (4, where A is defined in Section 4.3.1
we have A, = =lvž vē+ || <
||+ r++1
By choice
of o, n, T as in (36), we have
10c0 8.1
160r/212 8.1
eT
10(1 - -)5 9.1
160y
4edo ÒNE
In
9.1
In
8
122
1²
B)
170(1
3)68 9.1
4edo
,g,1 4dg })
1
In
max
112
8E(1 - B)
Now we choose 3 to be
1.222
170 64edo a.1
1g.1 ō
}
1 - 3 = 170 64L ln(
where p=
Spze3
max
0g,1 do
Then have
170(1 - 9)02
4edo )
2
22
n In
- (nP) In (VPIn(P)) S
(1
64L3
where we use the fact that In( In(VPIn(P)) S In(P) s In² IP) for any P 2 4 by choice of as in
35
In the rest of this section, we assume Assumptions 3.1 to hold. In addition, the failure probability
5 e (0, 1) and e > 0 are chosen in the same way in Theorem 4.1
26

---

D.1 Proof of Lemma
Lemma D.2 (Warm-start, Restatement of Lemma 4.4). Let fyt } be the iterates produced by line 2 of Algorithm 2 Set iuit = ua² = OE with a defined in (36). qg ( g, and (1()) = g( y). Then lurit"" - vôll I v ua e holds with probability at least 1 - 8 over the randomness in Fimi (we denote this event as Eiitt) in Tu O(E iterations, where
To In 256I. juit vill
/11m
pa
Ō
(38)
Proof of Lemma D.2 By Lemmas C.6 and D.1 and p-strong convexity of g in y, we have with probability least I over the randomness in Finit that
2
12a22
Tb
10 20
eTo
voll2
<
Unuit
9.1
In
11
11
5
2
pac
To
Uniit
pace
4
64L3
where the first inequality uses the choice of init pa?. By 1g,1 -mmotthessss of g have
v2aa u?az
Unnit
Iigimit 2 + g (((tttiniit)) g( v66
2pac
3 init vúll2=
lluó
+
1
llua
init vōll x
2
inis vōll
2pa2
2
Na2
where the last inequality uses S 1/1,,1- Now set
2
1
100
2
juit voll2
+
pae2
-
pave?
11
4
uaa
64L3
32L3
which gives
3
To 2 In
1
256
Init
1o12
4
By choice of as in (36 and simple calculation we obtain To -2) when is small.
D.2 Proof of Lemma
Lemma D.3 (Option I, Restatement of Lemma 4.5 Under event Emitt let {yr} be the iterates
produced by Option I. Set a = ((e2) as in (36). 0.11 = (pax) g.a. and dr(y) = g(x),)) y) = Ely - 2t 1 Then for any L E [T), Algorithm guarantees with probability at least over the randomness in F1 (we denote this event Egy that 1|ye yi S e/2Lo.
Proof of Lemma
D.3
By Lemmas
C.5 and D.2
we have
11
122 <
1
Uo
10a02
g.1
160n/21
9.1
In
eT
4
1
p
v
jia
1y
init
vol 16
10a02 9.1
160
9.1
In
eT
4
α
3
d
2
2
|
96
6412
4L3
0
Thus conclude that for all t E [T], have 11ve
vł ||
S e e/2Lo.
27

---

D.3 Proof of Lemma 4.6
Lemma D.4 (Option II, Restatement of Lemma 4.6). Under event Emits let {y: be the iterates
produced by Option II. Set = (EE²) as in 36). g.1 (pa))//A and run SNAG in each update
round
pa
ipa O(E
In
128
steps in every == 201-B)Lo
O(==)) iterations, set Φe(y) g(z,, y) when t is multiple of be general functions). Then for any t E [T), Algorithm 2 guarantees with probability least 1 over the randomness in a ((
I (i.e., Te is fixed for each update round of Option Il
(we denote this event as Eg) that |[ye Vi 1| S c/ Loo
Proof of Lemma D.4 At the beginning of the first round, by Lemmas D.2 and D.3 we have |
yōll S <//Lg, then do not update the lower-level variable until I-th iteration, then for
we have
Blur - vill = l1yo- yřl
S
I|y0
yōll + Σ llyl yi-1l
é Na.1
<
1
2T.0
To
where in the last equality we plug in the definition of v) and 1 smmoothhsss of g we have
2 - 2/p + pa
U₁
2a 1lyr
voll 2 + 9(11,91)
g (.)
3 |1y1 v/1l2 + 19.1 lys vi aLg
26
20
Then for N steps update in the inner loops of t = I-th iteration, we set
vua
N
2e
2
2
+
S
4
aLi
64L
16L
which gives
u0
N
In
In
1
128
By choice of a as in 36) and simple calculation we obtain N Ō(E-)) when is small, Now have
2 (1
Vua
2
E²
||yr+1 vi 1/vi" 1il12
11
aL
64L
161
which yields
11r+1 vi+1ll < 11r411 vill + |1y] - vi+1ll 5
6
+
p1..1
<
4Lv
2
where we choose - 3 to small (see (56 for details) such that 77 is small enough to make above inequality holds. Repeating the same process yields the result.
D.4 Proof of Lemma
Lemma D.5 (Averaging, Restatement of Lemma 4.7 Under Assumptions 3.1 to 3.4 and event
Emit n (Option 1) or Emit NE? (Option II), we further set T = /pa in the averaging step (line 21 of Algorithm 2) Then for any t we have
2c and l1 - 0.1l 24I23 9.1
2e
0.
Lo
28

---

Proof of Lemma D.5 We will first show the following result by induction, i.c., for any t 2 0, the averaged sequence { satisfies
(1 7)mp e
1
will
5
(39)
Tp
To
For 1 = 0, by Lemma
D.2 we have
1100 36 = 11vtt init vōll S
pa
V
1-
-
32 Lo
32
Lo
Lo
thus the base case holds. Now suppose
39 holds for some t 2 0, then for time step t 1 we have
[10c+1 - Vi+1ll = [|(1 T ( - vit1) + (yh+1 - vi+1)ll
[ r v1 (1 -1)-((u Viit1) + + vi+1)ll
(1 T) v1ll (1 -T)lli² Ve+ill 1l +lllet+1 vitil
(1 -1-11 11-Tiaaa + Lo
(1 - T) 76
(1 7)
+
TH
P Lo
(1 - T) c
TH
Lo
where we use induction hypothesis in the second inequality. Therefore, we have that (39) holds for any 2 Also, consequence, for any we have
1 dell || 9t)1
s - +11b1+1 - yi+1ll + Tllbi+1 - Vi + =1yb. - dell
N9.11 +
(1 - 7)1]la11 + Lo
Lo
TH
(by,1
26
+
TH
Lu
Now we plug in the definition of a. 3, T, 1) as in 36 to obtain
l1
vEll -
+
V
3
+
e
S
TM
Lo
Lo
Lo
and
n/
2c
me²
110e+1 Dell S
+
T/
To
24T.20 g.1
D.5
Proof of Lemma 4.8
Lemma D.6 (Restatement of Lemma 4.8 Under Assumptions 3.1 to 3.4 and event Ena NEg (Option
I) or Enst NE (Option II), define E m, V Dc: E,),, then we have the following averaged cumulative error bound:
T-1
Lo
2(12 + 02) + LiV
2(1² (2)
T-1
Σ t=0
Ellall <
+ V1- Br +
S(1 3) T E
Σ
T
T(1 B)
VT 3 S
Proof of Lemma D.6 Define E, m, E f(r, 0ri E.)], also define é, and é as
& Vf E.) [V 0r: E)
& Vf E.) 1 E, B
By definition of c,, & and é,, have the following recursion for any t 2 0:
6111 Be, (1 B)ε + SE,+1
(40)
29

---

Then we apply 440) recursively to obtain
6 = 30 3 Σ 8 (1
Σ
Ei
which by triangle inequality and total expectation gives
E||e/|1 = 8 Ellcoll +(1 - B)L E
+
8
E
(41)
Brr
Errs
Bounding Erri.
By definition of cu and Lemma B.4 along with Jensen's 's inequality, we have
Elleoll S / R||coll2 S o.
(42)
Bounding Errg. obtain
We apply Lemma B.4 and follow the similar procedure in 38 Lemma D.9] to
2
σ (43)
S
E
22
vI - B
where Jensen's inequality for the first step.
Bounding Errg. holds:
We will first use induction to show that for 0 < t 1, the following inequality
2(1²
82
2(1 8
i
1-
E
E
Σ
8 B
B25 +
8
-1- -
S
S
j=(+1-
1=1
(44)
Then it's easy to check that by setting = t + 1 we can obtain the bound. When i obviously since
0, 44
holds
E
SE
3
g g i
30

---

Hence the base case stands. Now suppose holds for + 1. In fact, we have
44
holds for some 2 0, and we aim to show that
44
217 + L3 Σ 825-2
E
Σ
(45)
201 + L3
1-i
E
Ex-i-1
325-2 +
Σ
8
(46)
S
1=1
2(n + L3
S E
R--i-1
325-24 +
Σ 31
(47)
2(1 + L2
(-i-1
-E
E E1-1-1
Σ
gzj-2 + 1 2
Σ
31-
3
(48)
S
fml
2(1 + LB
8
|-i-1
$ E
En-i-1
goj-2 +
2 -311V4( 02)
Σ
Br-JEz
S
5
j=1
(49)
2,321
2(1 + 82)L2
:-i-1
= =EF----1
+ v0)
B25 +
Σ
B1-1E
(50)
S
S
2(12 02) 8 T1 (=)-)))4
2012 22)
1+1
1---1
< B
825-2 +
81-58
(51)
S
S
47 follows by Jensen's 's inequality, fact that e, for j < t- are Ft-i-1- and are uncorrelated with é for we use Lemmas B.6 and D.5 to derive
where (46) follows by law of total expectation,
48
uses the
E E---1 10--11111110 1
E
V f H1
Vf
E
< E V / (Z2-
s 1 ||| f [1 (z.- - V [
+ --1
- V 11
2
<
5 (L3 + V4 (1)
81 1 + -100-1
2 (1 + (= 02).
S
And (50) follows from the fact that .,-; is -easuralll 51 uses Va + va vb for for
b O. Hence the induction proof is completed. We set i = ++ to obtain
2(12 + 02) S
2(1² + 0
E
3 &
L
8
E
32i
S
1=0
(52)
2(n + 12)
Ln
2(n² + 02)
L
8
E
V
r
S
v1 B
S
1=0
Final Bound.
Combining
42 43 and
52
yields
Lo
2(1² + 82)
2(7 + (2)
Bller|| s 3 + vI 30 +
+
L
VI 3
S
S
1=0
31

---

Taking summation and dividing 1/T on both sides gives the final result
Lo
2nn + 02)
2(n2 02)
T-1
T Σ Ell S T(1 B) + v B0 +
+ 1
Σ
(x,))
v1- 3
S
S(1 B] T
t=
E Proof of Theorem 4.1
Before starting the proof of main results, i.e., Theorem 4.1 we first need the following lemma.
Lemma E.1. Suppose that Assumptions 3.7 hold. For any y satisfying
1
17 S
2(1 + / (2/12) + 1221)
it holds that
1 (1- 1 2n1 -2111180
1
vill
(x+)|
T
((x0)) - (((TT)
7-1
21 21.
Q
2L
T-1
1
+
Elles1 +
l10e
vi 1l
+ Nn
Tn
1
T
Proof of Lemma E.1
Define h2 m. (z)(
Then we apply Lemma
B.3
to obtain
Lo + L1 [
(1x S (xxx)) (V(())) 24+1 - -xa) +
1 mel1
2
((xx)) n (V)))
m,
1
2 + L [v+)))
|mm1|| ||
1
= ((x,)) 7/m hr
+
2"
(Lu + [(())l
|mmell
(53)
((xx)) 71|me|1 + ry(he. ||me||
me
2 77
1
(Lo + "Lo
< (xx.)) m/|mell + m//1 + 2" ( TT + (+()))
< ((x)) 7 (2:)) + 2n hell + 2 " + L ([(z))),,,
where for the last two lines we use Cauchy-Schwarz inequality and |hel [[V - hell 2
(x:))) - [helll Now expanding h2 by triangle inequality, we have
[he = ||m - (=(())
De: - ff 8e)l + IV 0.) -x)x))] < ||me- E.IVf dc: Gr:E)111 + |
$ ||ca|| + 1g,1 (1 (1-
11
(Lo L (= se ll.
1g.1
where we use definition of ér, Lemmas B.4 and B.5 in the last inequality. Plugging the above inequality back into (53) we obtain
(1 (1-14)) )
$ ((T+1) S (xx)) - M| / + 2//lc= + 2n
19.2
1
+ 20 + 41 (x:) - = ll + "
(Lo + Lall ((x))l
= 2 - n マタ L₁ - 27L1 vill |[ + 2nll
+ 21 10,0 (1-
/
2n
1 -i'l 2 To.
1
32

---

Dividing 1/Th on both sides, then taking telescope sum and total expectation, and rearranging it finally yields
1 1 11
1
2 n41 -211llie - vill
T
(x+]]
1=0
((xo) - (((T))
T-1
21 2 (1- 9.
2L T
1 vil ll +
+
Bllez|1
+
11
2 znnoo
Tn
T
1
1=0
1=
Theorem E.2 (Restatement of Theorem 4.1 Suppose Assumptions 3.7
to 3.4
hold. Let {ra)
} be the
iterates produced by Algorithm 2 For any given d E (0, 1) and any small
O satisfying
Lo
Lo.Lo
Lo
1o
Lo
19,10911 L1
(
1644 - 32edo 22
m.l
9
1/3
eSmin
max
32L1
8L1²
n²2
8p22
0g.1 do
(54)
if g.1 satisfies
1/4
n²2²
1n
6
0.1 =
min
164
16 8.1 In(P)
46 g.1 Li 4
0g11
(55)
with 0g1 O1), and we set parameters ag iuit 3,
T. th T, N, S, Q,
1222
1
2
0g,11 do 4,1 F
B = -min
= min
(1 - 3), (56)
164 16L 9.1 In(P)
4
g
L1
4
a init
1-3
1-
3
1
Vua
T=1
/uce
(57)
11 1.11
1
1 + Viaa"
2²
p
To In
In
(58)
256L2lly/
y6ll2
4
yuE
Vua
1= 2(1 T.
N
In
In
(59)
128
S max 128 (P).
12813
(P)).
11 Lg
Q = In 1
In
J.C
(60)
L3
12
lg.1
10141,0)
where do and P are defined in (37 Then with probability at least 28 over the randomness
in o FFintt U F+) (for Option 1) or o (Finit U (UIgT (for Option II), Algorithm 2 guarantees
T EL ( I 20c within T
4do 0(1/²) iterations, where the expectation is taken
ne
over the randomness in FT. For Option I, it requires To + SQT Ō(1/²) oracle calls of stochastic gradient or Hessian/Jacobian vector product. For Option II, it requires To + NT SQT Ō(1/e²) orucle calls of stochastic grudient or Hessiann/acooiin vector product.
Proof of Theorem
E.2
By Lemmas D.6
and
E.
we have
(1 1
n11 -
-0 - vill
E
(x:))l
2
T 1=
((xa))
-(((T)
+
2
T-1 1
Elle:
+
24
(1- (1-
14
Q
+
2
T-1
11
l|
+
Tn
T
1a.1
T
2
1=0
t=0
do
21 21.11400
1
11
Q
2Lo
T-1
Σ
11
vil +
2 no
Tn
9.1
T
(=0
27
+ /
+
20.
2(n² + 192)
+ 22
2(n2 + 02)
T Σ
T-1
E [
T(1 - 3)
VI
-
S
S(1 3)
33

---

Rearranging the above inequality gives
1
2(n2 + 02)
1-ク
2I,
11be
vill
2|11
S(1
3)
1=
(LHS)
do
2.
(1
Q
2L0
T-1
20
2Lo
22 + +02)
+
11
Vi + 2 n +
+ + - +
V
1g.1
T
T(1 3)
vI 3
S
(RHS)
Bounding (LHS).
By Lemma D.3
we have
(LHS) 2
0 L1
(1 - B)
2T,
2
2
2(n + 02)
21 g.1
Lo
S(1 B)
(61)
1
1
4
Bounding (RHS). By choice of parameters, we have
1
(RHS) S 4 + 2e + 4e +et +e+es 10c.
(62)
2
Combining (61) and (62) finally yields
Σ
( 20c.
F
Omitted Proofs in Appendix B
F.1 Proof of Lemma B.5
Lemma F.1 (Restatement of Lemma B.5). Under Assumptions 3.1 3.4
we have
( (L+ Ll y (x)
where constant L is defined as
5.00 1..1 (Fy, 1.,0) +,,0 pdg,2 + 1g,2 To-
1= Tu T
112
Proof of Lemma B.5 Recall that the exact expressions of V f(z.)) and V
((x V.I(x,
and
( = V v fz p [ttp://hjj..aaaaoo/////////////r
Then by Assumption 3.2 we have
[Vf(z.)) - V v.f.v)))
-
http://wwwSSSaaaaoooooo/////o/// (Ln,0 + L,, (,
+ |15p://cf1h10ll////////////////1
34

---

L2,0 + Lun1 (1g2l50 + -(18((0))) vx))(())
10:0 1401,,2 1222118 -x((x) + 1
1111 1² l.2lly (z(x))
(Ly.0 V v (z)))))) (x))l
u
L2,0 Lxn11 1 + l.. (Lo p,0 + 1000
u + 29
+ L L [[,1\((()1]] 11 -w-v"(<))
a
4²
By definition of L conclude the proof.
F22 Proof of Lemma B.6
Lemma F2 (Restatement of Lemma B.6p. Under Assumptions 3.7 to 3.4
we have
(i) For any fixed Rd and any 21, 22 R
Eg ff v: V fz2,
y: Ell & (L) + [3 - x211?.
(ii) For any fixed x E Rd and any 91,92 E RRd,
E. (l Vz( v2: 1) S (Tg + [ x211?
In the above expressions, we define Lo and L1 as
Lo { (Lao+ Lu,1
(Lmo+ + 22 ) 11 - will
1
1
bobbukk22 (eilTga [ 2..00.2 (1 =12
}
1/2
6Q
2plg
11)2
L1 = 2Lx, + 1n.1ll11 vill I))
Proof of Lemma B.6 We show statement (i) of the lemma, and (di) follows by similar arguments. For any fixed y E Rd and any x2 E Rdd by definition of V f(z y) we have
V ()
Q 1g.11
v, ((oc v.
s 2 V F(2.
+2 v G(a,,
1,
(r
C2,
II
10.1
1,,1
(=1
2(T T (V.,,
x2l1 +2
v2
G(E1,
II
(1
V. F(1,)))
6.11
1,11
1=1
(0))
Q
v, (,F((s.ui))) (o
1
1g
1,11
For the second term above, we have
Q
L
1
G(n,
VyF(xi,
1..1
s=1
1 T,
v, F(2(22)))))
Q²
29
< 312
[V,
9.1
12
1
9.1
Q²
+ 312
1
G(o,
vi -le
p
1g,1
2.1
35

---

+ 313 1,,00
17,00
Q II
v
Q
II
1
1
C(zz, (1))
1,11 1=1
1,11
9,1
1..1
=11
$ $30²
1
29
(Ly. + L (
+ -12l"
(1
M
20
f
x221
19.1
17
1..1
+ +317,00 00
II
G( (0))
V
G( Us
((00
1,23
1,11
Then we take expectation with respect to and obtain
Q
1
1
Eg
v
1g.1
vi
II
V. y F.2, Vin
10.1
1,,1
1=1
0²
p (1-
24
$
(L Ly,a v.l(
x2ll²
1
E2ll x2ll
Bg
1..1
+ +3
II 1 1a1 ((o,))
II
Vig ((os
10.1
3Q + Lu,a Vuf(2i ,)1l) - x2 + 0²
B. Q(2plg.1 422)
<
12
12 - zall²
12
2
+ 03
(1,11 (2plgg 1121 1|01 12
3Q
317 12 22,
S 2p - 212
(L + 1 - x2ll² + 11, - x2ll") + (l.11 () - -12) -12)1101 - 222
Gob.b2202)
3Q
B.llLy. + ) + 17.0l..2 + (1,.2 1u)3
||01 - x2
24lg,1 - -x²
Finally, taking expectation on both sides yields
[ellV/(a1. - f y: 11 S 2(T
T VV 9)))) -x2112
6Q
12 (Lu + 2 + P7 + 1..00.222000
+ 2pd g.1 1
||0 - 22l1?
(1 11)
Since for any y E BRd,, we have
[V - Vaf(E1, S (Izz,0 + L1 VV vi)li - sill
Lo.0 + La,1 (buulr + ((((a()))) |1 sill
11000 Lealgaloo + Lz. [[ Il - -ill.
which yields
[V.l(an S V.I(<II, (Lao + Amalgale + Lz. (v..IVV((a)) |1 - will
1 + [[ + (Loo+ Iealgale + La V I1e1 - vill
14اد650 + (Lzo + Laslorlro) ) 11l1 vill) + (1 + L |v - (
1
36

---

Therefore, we conclude that
( - Vx(2 y: E112 1 22( + (1. -
6Q
L G.llLno + Ly110,00 + 1.006.22 1000++770000 + 1
+ 21l.,11 112
||21- -221
(1 u)
L. ken 11911 - -oil-vill) + L. (1 Le,, -i
2
2 L0.0 + La,1
||0| -
6Q
17 9.00 29,02
+
12 1g.lT + ,,,1 + f. +
||2|| - -
2p - 112
(1.11 - 11²
11 vil
14 Lu,0 + Li.1
|| x2l1
1
1
+ 4T. (1 + TeN
1191 11
x2|1
6Q
1 f 20200
+ 2 - 11²
l. GgnlL + ,,,
1.00
|| - x221
(1.11 n12
(Tg + [ - x2l1²
where we use the definition of Lo and Lj in the last equality.
G Additional Experimental Details
Hyerparameter setting. We tune the best hyperparameters for each algorithm, including upper- /lower-level step size, the number of inner loops, momentum parameters, etc. The upper-level learning rate Tup and lower-level learing rate now are tuned in the range of [0.001, 0.1] for all the baselines on experiments of AUC maximization and data hyper-cleaning, the best (Nup: T]oow) on
AUC maximization are summarized as follows: StocBio: (0.01, 0.001), TTSA: (0.005, 0.01),
SABA: (0.01, 0.005). MA-SOBA: (0.01, 0.005), SUSTAIN: (0.03, 0.01), VRBO: (0.05, 0.01).
BO-REP: (0.001, 0.001), AccBO: (0.005, 0.005). The best learning rate on the experiment of data hyper-cleaning are summarized as follows: Stocbio: (0.01, 0.002). TTSA: (0.001, 0.01),
SABA: (0.05, 0.02). MA-SOBA: (0.01, 0.01), SUSTAIN: (0.05, 0.05). VRBO: (0.1, 0.05), BO- REP: (0.02, 0.01), AccBO: 0.11, Note that SUSTAIN decays its llper-llowerllevel step size with epoch (t) by Tup ///p/(t+ (t) now Mup/ /tpppptt/2 (t+ while other algorithms use constant learning rate. The number for neumann series estimation in StocBiO and VRBO is fixed to 3, while is uniformly sampled from {1, 2, 3} in TTSA, SUSTAIN, and AccBO. In AUC maximization, AccBO uses Option (Option in data hyper-cleaning) to update the lower-level variable, and sets the Ne- strov momentum parameter 7 0.5, the averaging parameter hyper-cleaning). AUC maximization, the batch size is set to be 32 for all algorithms except VRBO, which uses larger batch size of 64 (tuned in the range of {32, 64, 128, 256, 512)) at the checkpoint step and 32 otherwise. In data hyper-cleaning, the batch size is set to be 128 for all algorithms except VRBO, which uses larger batch size of 256 (tuned in the range of {63, 128, 256 512, 1024)) the checkpoint step and 128 otherwise. AccBO uses Option II in data hyper-cleaning, and the periodical update for low-level variable sets the iterations N 3 and update interval I 2. Other hyperparame- ters setting keep the same in AUC maximization and data hyper-cleaning: The momentum parameter is fixed to 0.9 in AceBO, MA-SOBA. BO-REP The warm start steps for lower-level variable in AccBO is set to 3. The number of inner loops for StocBio is set to 3. BO-REP uses the periodical update for low-level variable, and set the iterations N and the update interval I = 2.
0.5 (y 0.1 and 0.5 in data
37

---

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

---

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

---

Answer: [Yes]
The code and data are attached as a supplement with instructions for repro- ducibility.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips. //nips.cc/pil wwcppbblc/gguiicuceccccccoe.oopp /etggudddsse/eebbbinninn
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are included in Section 5 and Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[No]
Justification:
We only run once due to limited computational budget.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
40

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The hardware specification is described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have read and conformed to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field of Machine Learning from algorithmic and theoretical aspects. We do see any direct paths to negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not involve the release of any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our paper uses existing text classification datasets and are cited in Section and their licenses are mentioned.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
42

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "JPSKwFkY6n", "reviewer": "Reviewer_wLtJ", "summary": "This paper considers a class of stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness, and the lower-level problem is strongly convex. Their novel algorithms achieve an oracle complexity of $O(1/\\epsilon^3)$ to find an $\\epsilon$-stationary point.", "questions": "1. Regarding the main challenge, the authors state why previous algorithms and analyses do not work. However, this explanation is not clear to me. Can you elaborate on how your work addresses the problem of hypergradient bias? Also, how does your potential function argument differ from previous work?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The setting is novel: they consider problems with potentially unbounded smoothness.\n2. Their complexity strictly improves the state-of-the-art oracle complexity for unbounded smooth nonconvex upper-level problems and strongly convex lower-level problems.", "weaknesses": "1. In the algorithm, for the update of the normalized stochastic gradient, it seems that it can be reformulated to tune the learning rate by dividing by the norm of the stochastic gradient. Therefore, the novelty and reasonableness of this step may be unclear.\n2. In the experiments, it is common to use the same learning rate for baselines and the proposed algorithms for a fair comparison. However, in the experimental details, the authors provide the best learning rate pairs for different baselines, which seems unusual.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for taking the time to review our paper. We have addressed each of your concerns below.**\n\n**Q1. In the algorithm, for the update of the normalized stochastic gradient, it seems that it can be reformulated to tune the learning rate by dividing by the norm of the stochastic gradient. Therefore, the novelty and reasonableness of this step may be unclear.**\n\n**A1.** Thank you for your insightful question. We would like to emphasize that we use *normalized stochastic gradient descent with recursive momentum* for updating the upper-level variable $x_t$ to reduce the effects of stochastic gradient noise, as well as the effects of unbounded smoothness and gradient norm. A similar approach of using normalized stochastic gradient descent with standard momentum is outlined in the Section 3.1 of [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf).\n\nThe novelty and reasonableness of our upper-level update lie in the following two aspects: first, we use recursive momentum update for $m_t$ (line 23 of Algorithm 2) to achieve variance reduction and acceleration, while [Hao et al., (2024)](https://arxiv.org/pdf/2401.09587.pdf) uses moving average estimation for $m_t$; second, we choose a larger learning rate $\\eta$ to achieve acceleration. Specifically, for any given small $\\epsilon>0$ (i.e., the target gradient norm $\\epsilon$), our algorithm's learning rate is $\\eta=\\widetilde{\\Theta}(\\epsilon^2)$ , while that of [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf) is $\\eta=\\widetilde{\\Theta}(\\epsilon^3)$. The large learning rate is crucial for proving acceleration.\n\n**Q2. In the experiments, it is common to use the same learning rate for baselines and the proposed algorithms for a fair comparison. However, in the experimental details, the authors provide the best learning rate pairs for different baselines, which seems unusual.**\n\n**A2.** We would like to clarify that it is indeed a common practice in the bilevel optimization literature to compare different baselines using the best-tuned learning rate pairs. For example, see Appendix A and B of [(Ji et al., 2021)](https://arxiv.org/pdf/2010.07962), Appendix B of [(Yang et al., 2021)](https://arxiv.org/pdf/2106.04692), Section 5 of [(Hong et al., 2023)](https://arxiv.org/pdf/2007.05170), Section 4 of [(Khanduri et al., 2021)](https://arxiv.org/pdf/2102.07367), and Section 4 of [(Chen et al., 2022)](https://arxiv.org/pdf/2102.04671).\n\n**Q3. Regarding the main challenge, the authors state why previous algorithms and analyses do not work. However, this explanation is not clear to me. Can you elaborate on how your work addresses the problem of hypergradient bias? Also, how does your potential function argument differ from previous work?**\n\n**A3.** Thank you for your insightful question, and we apologize for the ambiguity. Most previous works, such as [(Khanduri et al., 2021](https://arxiv.org/pdf/2102.07367); [Yang et al., 2021)](https://arxiv.org/pdf/2106.04692), assume that the upper-level objective function is $L$-smooth. Their algorithms and analyses rely on the $L$-smoothness property to leverage some nice forms of hypergradient bias, which typically depend on the approximation error of the lower-level variable, and either the Neumann series approximation error or the linear system solution approximation error when handling the Hessian inverse. Most importantly, their hypergradient bias does not depend on the (ground-truth) hypergradient $\\nabla\\Phi(x_t)$ itself. \n\nIn contrast, when the upper-level problem is unbounded smooth (i.e., $(L_{x,0}, L_{x,1}, L_{y,0}, L_{y,1})$-smooth as illustrated in Assumption 3.1), the hypergradient bias depends on both the approximation error of the lower-level variable and the hypergradient itself, for example, $\\\\|\\hat{y}_t-y_t^*\\\\|\\\\|\\nabla\\Phi(x_t)\\\\|$. Please see lines 803-804 of Lemma E.1 in Appendix E for details. These two elements are statistically dependent, necessitating high probability analysis for the lower-level problem, which means the standard expectation analysis used in previous works cannot be applied to our setting. Another recent work, [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf), studies the same setting as ours, but their algorithm does not achieve acceleration.\n\nLet us provide more details to explain how we handle the hypergradient bias (lines 803-804 of Lemma E.1). Specifically:\n- In Lemma D.6, we control the first term $\\\\|\\epsilon_t\\\\| = \\\\|m_t - \\mathbb{E}_t[\\bar{\\nabla} f(x_t,\\hat{y}_t;\\bar{\\xi}_t)]\\\\|$ by Jensen's inequality and induction.\n- In Lemma B.4, we control the second term $\\\\|\\mathbb{E}_t[\\bar{\\nabla} f(x_t,\\hat{y}_t;\\bar{\\xi}_t)] - \\bar{\\nabla} f(x_t,\\hat{y}_t)\\\\|$ by leveraging the Neumann series approximation result from [(Khanduri et al., 2021)](https://arxiv.org/pdf/2102.07367).\n- In Lemma B.5, we control the third term $\\\\|\\bar{\\nabla} f(x_t,\\hat{y}_t) - \\nabla\\Phi(x_t)\\\\|$ using the triangle inequality and the relaxed smoothness property of the upper-level function.\n\nWith a suitable choice of parameters, the hypergradient bias can be small on average.\n\nRegarding the potential function argument, we directly use the objective $\\Phi(x)$ itself as the potential function. This approach differs from previous works that incorporate both the function value and the approximation error from the lower-level problem. Our problem setting and analysis do not align with those in previous works, necessitating this different approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sHyLBtZh6s", "reviewer": "Reviewer_W5hu", "summary": "This paper investigates a class of stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness, and the lower-level problem is strongly convex. To improve the convergence rate, the authors propose a new Accelerated Bilevel Optimization algorithm named AccBO. This algorithm updates the upper-level variable using normalized stochastic gradient descent and the lower-level variable using the stochastic Nesterov accelerated gradient descent algorithm with averaging. The proof shows that AccBO has an oracle complexity of $ \\tilde{O}(1/\\epsilon^3) $, relying on a novel lemma describing the dynamics of the stochastic Nesterov accelerated gradient descent algorithm under distribution drift. Experimental results demonstrate that AccBO significantly outperforms baseline algorithms in various tasks, achieving the predicted theoretical acceleration.", "questions": "In reference [33], Assumption 2 states $|| \\nabla_y f(x, y^*(x)) || \\leq M$, while in this paper, Assumption 3.2 states$ || \\nabla_y f(x, y) || \\leq l_{f,0} $ . Can this assumption be relaxed to a less stringent form?", "limitations": "The convergence analysis for Option I of the AccBO algorithm assumes that the lower-level problem is a one-dimensional quadratic function.  This limits the algorithm's applicability to scenarios where the lower-level function deviates significantly from this simple form, especially in higher dimensions or more complex optimization landscapes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The paper introduces AccBO, a novel algorithm that leverages normalized recursive momentum for the upper-level variable and Nesterov momentum for the lower-level variable. This dual approach to acceleration in bilevel optimization under stochastic settings is a significant advancement.\n\n2.AccBO achieves an oracle complexity of  $ \\tilde{O}(1/\\epsilon^3) $ for finding an $\\epsilon$-stationary point. This is a substantial improvement over the previously best-known complexity of        $ \\tilde{O}(1/\\epsilon^4)  $            for similar problems.The paper provides new proof techniques, particularly in analyzing the dynamics of stochastic Nesterov accelerated gradient descent under distribution drift. \n\n3.The effectiveness of AccBO is empirically verified across various tasks, including deep AUC maximization and data hypercleaning. The results show that AccBO achieves the predicted theoretical acceleration and significantly outperforms baseline algorithms.\n\n4.The paper extends the bilevel optimization framework to handle upper-level functions with unbounded smoothness, which is a realistic scenario in many neural network applications. This makes the proposed algorithm applicable to a broader range of practical problems.", "weaknesses": "The convergence analysis for Option I of the algorithm is restricted to the lower-level problem being a one-dimensional quadratic function. This limitation reduces the generality and applicability of the theoretical results for more complex lower-level problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for taking the time to review our paper. We have addressed each of your concerns below.**\n\n**Q1. The convergence analysis for Option I of the algorithm is restricted to the lower-level problem being a one-dimensional quadratic function. This limitation reduces the generality and applicability of the theoretical results for more complex lower-level problems.**\n\n**A1.** Thank you for your insightful question. Please note that Option II of Algorithm 2 works for the general case of high-dimensional functions and also enjoys an accelerated convergence rate of $\\widetilde{O}(1/\\epsilon^3)$. Therefore, it can indeed handle complex lower-level problems in high dimensions and is more general than Option I. \n\nOne can regard Option I as a way to leverage the nice structure of the lower-level problem, making it easier to implement in practice. When the lower-level function is one-dimensional and quadratic (e.g., deep AUC maximization), we can invoke Option I, making AccBO a single-loop algorithm, which is easier to implement. In the general case, when the lower-level objective is a strongly convex function in high dimensions (e.g., data hypercleaning), we can invoke Option II, resulting in AccBO becoming a double-loop algorithm.\n\n**Q2. In [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf), Assumption 2 states** $\\\\|\\nabla_y f(x,y^*(x))\\\\| \\leq M$**, while in this paper, Assumption 3.2 states** $\\\\|\\nabla_y f(x,y)\\\\| \\leq l_{f,0}$**. Can this assumption be relaxed to a less stringent form?**\n\n**A2.** In this paper, we use the Neumann series approach to handle the Hessian inverse and hypergradient approximation. Therefore, we need to upper bound the bias term $\\\\|\\bar{\\nabla} f(x_t,\\hat{y}\\_t) - \\nabla\\Phi(x_t)\\\\|$ when proving the convergence of AccBO (see lines 803-804 of Lemma E.1 in Appendix E for details). The assumption $\\\\|\\nabla_y f(x,y)\\\\| \\leq l_{f,0}$ is particularly crucial for deriving Lemma B.5 in Appendix F.1 under our current analysis, which is necessary for proving Lemma E.1.\n\nIn contrast, [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf) uses the linear system approach to handle the Hessian inverse and hypergradient approximation, so bias terms like $\\\\|\\bar{\\nabla} f(x,y) - \\nabla\\Phi(x)\\\\|$ do not appear in their analysis. As a result, they only need a slightly relaxed assumption, $\\\\|\\nabla_y f(x,y^*(x))\\\\| \\leq M$, to show the smoothness properties of the bilevel optimization problem.\n\nIn fact, many existing works in the bilevel literature that use the Neumann series approach to handle the Hessian inverse require this assumption (i.e., $\\\\|\\nabla_y f(x,y)\\\\| \\leq l_{f,0}$). For example, see Assumption 1 of [(Ghadimi and Wang, 2018)](https://arxiv.org/pdf/1802.02246), Assumption 2 of [(Ji et al., 2021)](https://arxiv.org/pdf/2010.07962), Assumption 1 of [(Hong et al., 2023)](https://arxiv.org/pdf/2007.05170), Assumption 1 of [(Khanduri et al., 2021)](https://arxiv.org/pdf/2102.07367), Assumption 1 of [(Yang et al., 2021)](https://arxiv.org/pdf/2106.04692), and Assumption 1 of [(Chen et al., 2021)](https://proceedings.neurips.cc/paper_files/paper/2021/file/d4dd111a4fd973394238aca5c05bebe3-Paper.pdf).\n\n**Q3. The convergence analysis for Option I of the AccBO algorithm assumes that the lower-level problem is a one-dimensional quadratic function. This limits the algorithm's applicability to scenarios where the lower-level function deviates significantly from this simple form, especially in higher dimensions or more complex optimization landscapes.**\n\n**A3.** We have addressed your concern about this limitation in **A1**. Please see **A1** for details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2O63fpQxu0", "reviewer": "Reviewer_o6Pr", "summary": "The authors consider bilevel optimization problems under the unbounded smoothness assumption of the outer function. They propose AccBO, an AID-based method that uses Stochastic Nesterov Accelerated Gradient to approximate the lower-level solution and Neumann approximations to estimate the inverse Hessian-Vector product involved in the hypergradient expression. Then, a normalized STORM-like update is performed for the outer variable. They show a $\\tilde{\\mathcal{O}}(\\epsilon^{-3})$ complexity of their algorithm. Finally, numerical experiments are provided on the deep AUC maximization and data hypercleaning problems.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **S1**: The paper is well-written\n- **S2**: The algorithms proposed by the authors achieve SOTA complexity for stochastic bilevel optimization under unbounded smoothness assumption.", "weaknesses": "### Major\n\n- **W1**: Some errors in the code may invalidate the experimental results. See the comment **C2** in the Code section for details.\n\n- **W2**: AccBO comes with many hyperparameters, which can be a concern for practical applications.\n\n- **W3**: l.219: \"is nearly optimal in terms of the dependency of $\\epsilon$\". The authors should be careful when talking about optimality of an algorithm. In particular, the algorithm AccBO does not belong to the algorithm class considered in [1] which does not take into account the biasedness of the hypergradient estimate due to the approximation of the inverse Hessian-vector product and the solution of the inner optimization problem. To my knowledge, the only works considering lower bounds for bilevel problems are [2, 5].\n\n- **W4**: The works [2, 3, 4] also use Nesterov acceleration for the inner optimization problem, but in the deterministic setting. They should be mentioned in the paper.\n\n### Code\nEven though it is a theoretical paper, I have several comments regarding the experiments code:\n\n- **C1**: In the checklist, the authors indicate \"The code and data are attached as a supplement with instructions for reproducibility.\" However, the code documentation is insufficient to run the experiments. The data are not present in the folders and there is no instruction indicating where to download them. As a consequence, when I launch the commmand `python main.py --methods accbo ` as indicated in the `README.md`, I get an error.\n\n- **C2**: It seems that the implementation of the different methods do not correspond to the one described in their respective original paper, which might invalidate the empirical results:\n    - For `TTSA`, `SUSTAIN` and `AccBO`, the estimation of the inverse Hessian-vector product is computed by the formula \n    $$\n        v = \\eta\\sum_{q=-1}^Q\\prod_{j=Q-q}^Q(I-\\eta \\nabla^2_{yy}G(x,y;\\zeta^{(j)}))\\nabla_y F(x,y;\\xi)\n    $$\n    while in the original paper (and even the present paper for AccBO), the authors use the formula\n    $$\n        v = \\eta\\prod_{j=1}^{q(Q)}(I-\\eta \\nabla^2_{yy}G(x,y;\\zeta^{(j)}))\\nabla_y F(x,y;\\xi)\n    $$\n    with $q(Q)\\sim\\mathcal{U}{\\{1,\\dots,Q-1\\}}$.\n\n    - For `SABA`, the SAGA-like variance reduction is absent in the code while being the core of the algorithm. Moreover, `SABA` uses constant step sizes.\n\n    - For `VRBO`, the oracles in the case `step % self.args.update_interval == 0` should be computed with a larger batch-size (or even with full batches) than in the inner for-loop.\n\n- **C3**: The code of `VRBO` for the datacleaning task is missing. The method to compute the hypergradient in `ma_soba.py` is missing as well for the datacleaning task (but not AUC experiment, thus I assume it is almost the same).\n\n### Minor\n- l.41: \"transforms\" -> \"transformers\"\n- In `README.md` (both): `python main.py --medthods [algorithm] ` -> `python main.py --methods [algorithm] `\n\nI am inclined to raise my score if my concerns, particularly regarding the experiments, are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for taking the time to review our paper. We have addressed each of your concerns below.**\n\n**W1. Code issue.**\n\n**A1.** Please see **A5** to **A7** for details.\n\n**W2. AccBO comes with many hyperparameters.**\n\n**A2.** Please note that existing literature on bilevel optimization with variance reduction [(Khanduri et al., 2021](https://arxiv.org/pdf/2102.07367); [Yang et al., 2021](https://arxiv.org/pdf/2106.04692); [Guo et al. 2021)](https://arxiv.org/pdf/2105.02266) all involve many hyperparameters. Compared to previous works, AccBO has more hyperparameters since our bilevel problem setting is more challenging: our upper-level problem is unbounded smooth, while others consider $L$-smooth upper-level functions. Hence their algorithm designs cannot be applied to our setting.\n\nTo achieve acceleration in our problem setting, we update the lower-level variable $y_t$ using the SNAG method with averaging, resulting in additional hyperparameters $\\gamma$ and $\\tau$ (line 8 and 21 of Algorithm 2), as well as $I$ and $N$ (only for Option II). In practice, $\\gamma$ and $\\tau$ need tuning, while $I$ and $N$ are set to default values as in [(Hao et al., 2024)](https://arxiv.org/pdf/2401.09587.pdf).\n\n**W3. Optimality and lower bound issue.**\n\n**A3.** Thank you for your insightful question. First, please note that existing literature on bilevel optimization with variance reduction [(Khanduri et al., 2021](https://arxiv.org/pdf/2102.07367); [Yang et al., 2021)](https://arxiv.org/pdf/2106.04692) state that their $\\widetilde{O}(1/\\epsilon^3)$ complexity results are near-optimal in terms of the dependency on $\\epsilon$; see Section 1.1 of [(Yang et al., 2021)](https://arxiv.org/pdf/2106.04692) and Section 1 of [(Khanduri et al., 2021)](https://arxiv.org/pdf/2102.07367) for details.\n\nRegarding existing works considering lower bounds for bilevel problems, please note that the lower bounds in [(Ji & Liang, 2023)](https://arxiv.org/pdf/2102.03926.pdf) apply only to deterministic and convex/strongly-convex upper-level problems, and the lower bounds in [(Dagréou et al., 2023)](https://arxiv.org/pdf/2302.08766.pdf) apply only to nonconvex smooth finite-sum objectives in the stochastic setting. In contrast, we study the general expectation form in the stochastic setting, where the upper-level problem is nonconvex and unbounded smooth. Therefore, their lower bounds cannot be applied to our problem setting.\n\nNow we will establish a $\\Omega(1/\\epsilon^3)$ lower bound via a simple reduction to single-level stochastic nonconvex smooth optimization, assuming the stochastic gradient oracle has mean-squared smoothness.\n\nIt is shown in [(Arjevani et al., 2023)](https://arxiv.org/pdf/1912.02365.pdf) that with the mean-squared smoothness assumption, $\\Omega(1/\\epsilon^3)$ complexity is necessary for finding an $\\epsilon$-stationary point when using stochastic first-order methods for single-level stochastic nonconvex optimization problems. Note that our problem class is more expressive than the function class considered in [(Arjevani et al., 2023)](https://arxiv.org/pdf/1912.02365.pdf), making our problem harder. This is because standard smoothness is a special case of relaxed smoothness and single-level optimization is a special case of bilevel optimization. \n\nFor example, if we consider an easy case where the upper-level function does not depend on the lower-level problem (e.g., $\\Phi(x) = f(x)$ such that $\\Phi$ is independent of $y^*(x)$) and is mean-squared smooth, then the $\\Omega(1/\\epsilon^3)$ lower bound in [(Arjevani et al., 2023)](https://arxiv.org/pdf/1912.02365.pdf) can be applied in our setting. Therefore the $\\widetilde{O}(1/\\epsilon^3)$ complexity achieved in this paper is already optimal up to logarithmic factors in terms of the dependency on $\\epsilon$.\n\n**W4. The works [2, 3, 4] should be mentioned in the paper.**\n\n**A4.** Thank you for your suggestion. We will mention [2, 3, 4] in the related work section. However, could you please clarify what [2, 3, 4] refer to? It seems that the references you mentioned are missing in your review.\n\n**C1. Data and instructions are missing.**\n\n**A5.** Thank you for catching this issue. We forgot to include the instructions on how to download the data. We have fixed it (including the data and instructions) in the revised version of the code. Please reach out to AC for the code link.\n\n**C2. Implementation issues.**\n\n**A6.** Please refer to the global rebuttal PDF file for new experimental results and hyperparameter settings.\n\n- **Neumann series.** In practice, we have fixed the implementation of Neumann series using random $\\texttt{q}(Q)$ and it does not affect the performance too much. In theory, the expectations of $v_1$ and $v_2$ (defined as the two formulas you wrote) are the same. This means that both $v_1$ and $v_2$ can be applied to our algorithm and analysis, and using either one does not affect the convergence rate of AccBO. We prefer $v_1$ over $v_2$ in practice due to less randomness in $v_1$, leading to slightly better and more stable performance.\n- **SABA.** We have fixed the implementation of SABA and now use a constant step size for SABA. See results in the rebuttal PDF file.\n- **VRBO.** We choose a larger batch size for the outer loop (i.e., at the checkpoint) than for the inner loop. In experiments, we tune the batch size for the outer loop and set it to be twice that of the inner loop. We rerun the two experiments, see results in the rebuttal PDF file.\n\n**C3. The VRBO code and the hypergradient computation method in `ma_soba.py` are missing for the datacleaning task.**\n\n**A7.** The file `ma_soba.py` used in the data-cleaning task is similar to the one used in the AUC task. We have added the implementation of VRBO and the hypergradient computation method in `ma_soba.py` for the data hypercleaning task. **Please reach out to AC for our anonymized code link.**\n\n**Minor Issues**\n\nWe will fix the typos in the revised version of the paper and code.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gsE9gt0TbW", "reviewer": "Reviewer_2WtS", "summary": "This work develops the first algorithm that achieves the near-optimal oracle complexity $\\widetilde{O}(\\epsilon^{-3})$ (the number of evaluations to gradient or Hessian/Jacobian vector product) to achieve an $\\epsilon$-stationary point of a stochastic bilevel optimization problem with unbounded smooth nonconvex upper-level function and strongly-convex lower-level function. The algorithm design is novel which updates the upper-level variable by normalized stochastic gradient descent with recursive momentum and updates the lower-level variable by the stochastic Nesterov accelerated gradient (SNAG) method.", "questions": "(1) **My major concern** is that Assumption 4.2 is made on algorithm-generated variables not on problem setting, which cannot be verified. Is it possible to bound $\\Delta_t$ in terms of $\\|x_{t+1}-x_t\\|$ to get rid of Assumption 4.2? If not, at least Assumption 4.2 should also be mentioned in the main result (Theorem 4.1). **I would like to raise my rating if all the assumptions become problem-related.**\n\n(2) In line 48 \"each realization of the stochastic oracle calls is Lipschitz with respect to its argument\", do you mean $F(x,y,\\xi)$ and $G(x,y,\\xi)$ are Lipschitz continuous functions of $(x,y)$ for each $\\xi$? You might express in formula to make it more clear. \n\n(3) You could also cite [1] as a paper on relaxed smoothness:  \n[1] Convex and Non-convex Optimization Under Generalized Smoothness\n\n(4) In line 127, do you mean \"... is a good approximation of $\\nabla \\Phi(x)$ **if $y\\approx y^*(x)$**\"? \n\n(5) Is there an intuition why line 21 (averaging of y) is needed in Algorithm 2? Is it possible to implement $N=\\mathcal{O}(1)$ steps of SNAG such that $\\mathbb{E}\\|y_{t+1}-y^*(x_t)\\|\\le \\frac{1}{2}\\mathbb{E}\\|y_t-y^*(x_t)\\|$ and remove averaging of y for every outer iteration t, and obtain convergence result purely in expectation instead of high probability? This yields the same oracle complexity per round since $I,N=\\widetilde{\\mathcal{O}}(\\epsilon^{-1})$ are of the same order, and may get rid of Assumption 4.2 by bounding $\\Delta_t$ in terms of $\\|x_{t+1}-x_t\\|$.\n\n(6) You said your upper-level algorithm design is inspired from [17,49]. However, in line 23 (STORM variance reduction) of Algorithm 2, your second and third additive terms use the same samples $\\overline{\\xi}_t$ while [49] uses different samples. The algorithm design differs from [17] more. Such difference still exists even if Algorithm 2 is reduced to single-level. Why do you use such different design? \n\n(7) Also in line 23, does $\\overline{\\nabla}f(x_t,\\hat{y}_t;\\overline{\\xi}_t)$ denote  the average of the expression right below Eq. (2) over samples $s=1,\\ldots,S$? You could define more clearly. \n\n(8) At the beginning of Section 5 experiments, $ph(w; x)I_{[y=-1]}$ appears in your AIC maximization. Do you mean $rh(w; x)I_{[c=-1]}$? If not, what do $p$ and $y$ mean?", "limitations": "The conclusion section mentions the limitation that the convergence analysis for the Option I of Algorithm 2 relies on the lower-level problem being a one-dimensional quadratic function. Actually I think this is fine since Option II works for more general strongly convex lower-level function. The major limitation from my perspective in mentioned in my above question (1) about the undesired Assumption 4.2. \nThe authors said in the checklist that they do not see any negative societal impacts in their theoretical work, which I agree.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work studies a specific stochastic bilevel optimization problem with significant applications in sequential data learning. The upper-level function has unbounded smoothness which is more general than the widely used Lipscthiz smoothness assumption. The oracle complexity is improved on this specific bilevel optimization problem compared with existing works. The algorithm design not only combines but also adjusts STORM variance reduction and Nesterov acceleration. The 2 real-world experiments look convincing. The presentation is clean and clear.", "weaknesses": "The major weakness is Assumption 4.2 as mentioned in the question (1) below. Some points could be clarified as mentioned in other questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for taking the time to review our paper. We have addressed each of your concerns below.**\n\n**A1.** Assumption 4.2 used in Section 4.3.1 is **indeed problem-related and can be verified** when applied to the bilevel optimization setting. Note that the main goal of Section 4.3.1 is to provide a **general framework** for proving the convergence of SNAG under distributional drift. This framework can be leveraged as a tool to control the lower-level error in bilevel optimization and derive Lemma 4.7. In other words, we can view the lower-level problem of bilevel optimization as a **special case** within the more general framework provided in Section 4.3.1. We have mentioned the connection between Section 4.3.1 and Section 4.3.2 at lines 232-239 and lines 270-273.\n\nNow we verify that Assumption 4.2 holds in the bilevel optimization setting. We can regard the change of the upper-level variable $x_t$ at each iteration as the distributional drift for the lower-level problem. Thus, using the notation in Section 4.3.1, we can set the objective sequences as $\\phi_t(y) = g(x_t,y)$, the minimizers at time $t$ and $t+1$ as $w_t^* = y^*(x_t)$ and $w_{t+1}^* = y^*(x_{t+1})$, the minimizer drift at time $t$ as $\\Delta_t = \\\\|y^*(x_t) - y^*(x_{t+1})\\\\|$, and the stochastic gradient as $g_t = \\nabla_y G(x_t,z_t;\\pi_t)$. Moreover,\n- By Assumption 3.2, $g(x_t,y)$ is $\\mu$-strongly convex and $l_{g,1}$-smooth in $y$.\n- By Assumption 3.3, the noise $\\nabla_y G(x_t,y_t;\\pi_t) - \\nabla_y g(x_t,y_t)$ is norm sub-Gaussian conditioned on $\\widetilde{\\mathcal{F}}\\_t\\^1$ with parameter $\\sigma_{g,1}/2$.\n- By Lemma B.1 at Appendix B and line 24 of Algorithm 2 (i.e., update for $x_t$), $y^*(x)$ is $\\frac{l_{g,1}}{\\mu}$-Lipschitz continuous, and $x_{t+1} = x_t - \\eta\\frac{m_t}{\\\\|m_t\\\\|}$. Then for all $t$, we have $\\\\|y^*(x_{t+1}) - y^*(x_t)\\\\| \\leq \\frac{l_{g,1}}{\\mu}\\\\|x_{t+1}-x_t\\\\| = \\frac{\\eta l_{g,1}}{\\mu}$. This implies that the minimizer drift $\\Delta_t = \\\\|y^*(x_{t+1}) - y^*(x_t)\\\\|$ is almost surely bounded by $\\frac{\\eta l_{g,1}}{\\mu}$. Hence, $\\Delta_t^2 = \\\\|y^*(x_{t+1}) - y^*(x_t)\\\\|^2$ is also sub-exponential conditioned on $\\widetilde{\\mathcal{F}}\\_t\\^1$ with parameter $\\Delta^2 = (\\eta l_{g,1}/\\mu)^2$.\n\nThus the lower-level problem of the bilevel setting satisfies Assumption 4.2 with $\\mu = \\mu$, $L = l_{g,1}$, $\\mathcal{H}\\_t = \\widetilde{\\mathcal{F}}\\_t\\^1$, $\\Delta = \\eta l_{g,1}/\\mu$ and $\\sigma = \\sigma_{g,1}/2$. Then we can apply the general lemma (i.e., Lemma 4.3) provided in Section 4.3.1 to establish the lower-level error control as stated in Section 4.3.2 (i.e., Lemma 4.4-4.7). We will make it more clear in the revised version of this paper.\n\n**A2.** Yes, your understanding is correct. It is formally stated in Assumption 3.4 that $F(x,y;\\xi)$ and $G(x,y;\\zeta)$ are Lipschitz continuous functions of $(x,y)$ for each $\\xi$ and $\\zeta$. We will mention it at line 48 in the revised version.\n\n**A3.** Thank you for your suggestion. We will mention [(Li et al., 2023)](https://arxiv.org/pdf/2306.01264) in the related work section.\n\n**A4.** Yes, we will fix it in the revised version.\n\n**A5.** Thank you for your insightful question. First, the main reason for the averaging step is that we need to ensure the condition $\\\\|\\hat{y}\\_{t+1} - \\hat{y}\\_t\\\\| \\leq \\vartheta = O(\\epsilon^2)$ for all $t$. We achieve this in Lemma 4.7 by choosing a small $\\tau$ to make $\\\\{\\hat{y}\\_t\\\\}$ change slowly. This condition is crucial for controlling the average hypergradient estimation error in Lemma 4.8, which depends on $\\sqrt{1-\\beta} + \\sqrt{\\frac{\\eta^2+\\vartheta^2}{1-\\beta}}$. Thus we need at least $1-\\beta = O(\\epsilon^2)$, $\\eta=O(\\epsilon^2)$, and $\\vartheta = O(\\epsilon^2)$ to guarantee $\\frac{1}{T}\\sum_{t=0}^{T-1}\\mathbb{E}\\\\|\\epsilon_t\\\\| \\leq O(\\epsilon)$. \n\nSecond, we indeed need high probability analysis for the lower-level variable. When the upper-level problem is unbounded smooth, the hypergradient bias depends on both the lower-level approximation error and the hypergradient itself, $\\\\|\\hat{y}\\_t-y_t^*\\\\|\\\\|\\nabla\\Phi(x_t)\\\\|$, see lines 803-804 of Lemma E.1 for details. These two elements are statistically dependent, necessitating high probability analysis for the lower-level problem. Moreover, Appendix D.3 shows that when $\\\\|y_t-y_t^*\\\\| = O(\\epsilon)$, we need $N=\\widetilde{O}(1/\\epsilon)$ steps to guarantee $\\\\|y_{t+1} - y_t^*\\\\| \\leq \\frac{1}{2}\\\\|y_t-y_t^*\\\\|$ with high probability (lines 749 and 755). Please refer to the proof of Lemma 4.6 (lines 748-757) in Appendix D.3 for details.\n\nThird, as mentioned in **A1**, we can show that our bilevel problem setting satisfies Assumption 4.2. This allows us to apply Lemma 4.3 in Section 4.3.1 to control the lower-level approximation error with high probability.\n\n**A6.** Please note that in Corollary 3.2 and 3.4 of [(Liu et al., 2023)](https://arxiv.org/pdf/2302.06032), they set $k=K$ in Algorithm 1. This means their second and third additive terms use the same samples. Our algorithm differs from that in [(Cutkosky and Orabona, 2019)](https://arxiv.org/pdf/1905.10018) mainly in the update for $x_t$, where we use normalized SGD and they use SGD (both with recursive momentum). This difference is due to our assumption that the upper-level problem is relaxed smooth, necessitating the use of normalization to reduce the effect of noise. In contrast, [Cutkosky and Orabona (2019)](https://arxiv.org/pdf/1905.10018) assumes the single-level objective is $L$-smooth, thus SGD (with recursive momentum) is sufficient for their algorithm design.\n\n**A7.** Thank you for catching this issue. In the revised version, we will use $\\widetilde{\\nabla}f(x_t,\\hat{y}_t;\\bar{\\xi}_t)$ to denote the average of the stochastic hypergradient estimators more clearly.\n\n**A8.** Thank you for noticing this, and we apologize for the typo. It should be $rh(w;x)\\mathbb{I}\\_{[c=-1]}$ instead of $ph(w;x)\\mathbb{I}\\_{[y=-1]}$. We will fix this typo in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**General Response to All Reviewers**

Thank you to all the reviewers for taking the time to review our paper and provide valuable feedback. We have addressed each of your concerns individually, and below is a summary of the key changes made during the rebuttal phase.

1. We would like to clarify that Option I of AccBO is not a drawback of our approach, it is actually a benefit. Option I leverages the simpler structure of the lower-level problem, making it easier to implement. For one-dimensional quadratic functions (e.g., deep AUC maximization), Option I turns AccBO into a single-loop algorithm, simplifying implementation. Option II makes AccBO a double-loop algorithm, which works for the general case of high-dimensional strongly convex functions (e.g., data hypercleaning) and also enjoys an accelerated convergence rate of $\widetilde{O}(1/\epsilon^3)$, the same as Option I. This makes it capable of handling complex high-dimensional lower-level problems and more general than Option I.

2. We have updated the code and experiments, and our original implementation on Neumann series is not wrong. We have added new experiments based on the reviewer's request (e.g., different learning rate schemes and batch sizes), and the results are reported in the global rebuttal PDF file. It shows that our algorithm AccBO still significantly outperforms other methods. If you want to check the updated code, please reach out to AC (we have sent the anonymized code link to the AC).

3. We have fixed the typos and minor issues, and we will update them in the revised version of the paper.

Meta-review: There was some disagreement among the reviewers about this submission. Based on re-reading the whole discussion (taking into account reviewer's levels of expertise) and my own evaluation of the paper, I recommend to accept.
Decision: Accept (poster)