Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Authors: Parvin Nazari
Bojian Hou
Davoud Ataee Tarzanagh
Li Shen
George Michailidis
Venue: NeurIPS 2025 poster ()
Keywords: Online  Learning
Bilevel Learning
Zeroth- and First-Order Methods
Primary area: general_machine_learning
TL;DR: We propose a novel search direction for stochastic online bilevel optimization, enabling first- and zeroth-order algorithms to achieve sublinear regret without window smoothing.

Abstract: Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic \textit{window-smoothed} regret minimization, which may not accurately reflect system performance when functions change rapidly. In this work, we introduce a novel search direction and show that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear {stochastic bilevel regret without window smoothing}. Beyond these guarantees, our framework enhances efficiency by: (i) reducing oracle dependence in hypergradient estimation, (ii) updating inner and outer variables alongside the linear system solution, and (iii) employing ZO-based estimation of Hessians, Jacobians, and gradients. Experiments on online parametric loss tuning and black-box adversarial attacks validate our approach.

Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Parvin Nazari
Bojian Hou University of Pennsylvania boj mojjinn@upenn.cmm edu
Amirkabir University of Technology p. w..aaarri17 170gmai1 com
Davoud Ataee Tarzanagh Samsung SDS Research America d. tarzanaghhsamsunn com
Shen
University of Pennsylvania
1i wwwnehenneeedeeeeeeeeeeeeeeee cine. upenn edu
edu
George Michailidis
University of California, Los Angeles gmichail wwccchaal@cllcccc @ucla.
Abstract
Online bilevel optimization (OBO) is powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic window-smoothe minimization, which may not accurately reflect system performance when functions change rapidly. In this work, we introduce a novel search direction and show that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear stochastic bilevel regret without window smoothing. Beyond these guarantees, framework enhances efficiency by: (i) reducing oracle dependence in hypergradient estimation, (ii) updating inner and outer variables alongside the linear system solution, and (iii) employing ZO-based estimation of Hessians, Jacobians, and gradients. Experiments on online parametric loss tuning and black-box adversarial attacks validate our approach.
regret
Introduction
Bilevel optimization (BO) minimizes an outer objective dependent on an inner problem's solu- tion. Originating in game theory [64] and formalized in mathematical optimization [9], BO finds
applications operations research, engineering, economics [16], and image processing [14]. Re-
cently, BO has gained traction in machine learning, including hyperparameter optimization [22],
meta-learning [18], reinforcement learning [65], and neural architecture search [51].
In the offline setting, BO solves the following problem:
x argmin y(x,)(xx) subj. to yx(x) argmin (xx, y),
(BO)
where / and y are the outer and inner objectives, with and as their respective variables.
OBO [67] addresses dynamic scenarios where objectives evolve over time, requiring the agent to update the outer decision in response to the optimal inner decision. Similar to online single- level optimization (OSO) [72], OBO involves iterative decision-making without prior knowledge of outcomes [67, 50, 8]. Let T' be the total number of rounds. Define x, E X' C Jdd as the
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

OBO
Window Size in Regret (w)
System
Stochastic
Const.
Only Fune.
Local
Method
Iters,
Regret
Regret Min.
Feedback
Regret Bound
OAGD [67]
o(T)
N.A. (Exact)
X
X
X
I + Hi HaT
SOBOW [50]
o(T)
ONg log
X
x
x
Vp 12r
SOBBO [8]
o(I)
(Ng log
x
_ + Vr H2T
SOGD
1
T+ 1 Ar) Thte
70-s0GD
(di + d,) Ar) +(d + dz) d,)8r
Table I: Comparison of OBO algorithms based on regret window w, solver iterations, stochas- tic/constrained regrets, feedback type, and local bounds. Kig denotes the condition number of the inner objective 9t- Vr, Hp.r, Ar, Vr, År, Lr, a, and â are defined in (11), (14), (30), (10), and (28), respectively.
decision variable and ft X x Rd + R the outer function. Similarly, define Yr RRd and X' x Rd + R for the inner problem, where yf argminyeR<> (x, OBO can be seen as a single-player problem, where the player selects x; without knowing y (x). using y: as an estimate based on ft. Alternatively, can be framed a two-player game [64], where the leader (x₂) competes with the follower (y:), who selects y; (x) based on limited knowledge of g:. This framework includes online and adversarial variants of (BO), such as online actor-critic algorithms [71], online meta- learning [19], and online hyperparameter optimization [50]. The inner and outer functions may be time-varying, adversarial, unavailable a priori, and require nonstationary optimization.
Our Contributions. This paper addresses stochastic OBO, introducing novel first - and zeroth-order methods minimize stochastic bilevel regret. Key contributions are summarized below.
Stochastic regret minimization without window-smoothing. Existing OBO methods [67, 50, 40, 8] rely on deterministic window-smoothed regret minimization, which may not accurately reflect system performance when functions change rapidly. We address these limitations by introducing a novel search direction (Section and proving that both first-order and ZO methods achieve sublinear hindow-smoothing smoothing (w = 1); see Theorems 2.6 and 3.2 and Table 1.
stochastic bilevel regret without window-
OBO with function value oracle feedback. In large-scale and black-box settings [11, 58), first- and second-order information often unavailable or costly. Constructing accurate (hyper)-gradient estimators using only function value oracles is particularly challenging due to BO's nested structure. Existing methods rely on gradient, Hessian, and Jacobian oracles, limiting scalability [21, 27J. We propose Algorithm 2, which estimates Hessians, Jacobians, and gradients using function value oracles, achieving sublinear local regret (Theorem 3.2).
OBO with one subproblem solver iteration. A major challenge in BO is solving implicit systems approximate the hypergradient [43, 12]. While efficient offline BO methods exist [43, 15], extending them to OBO is difficult due to time-varying objectives. SOBOW [50] partially addresses this using a conjugate gradient (CG) algorithm with increasing iterations (Table 1). We improve upon SOBOW by introducing Algorithms I and 2, which require only single subproblem solver iteration.
2 Stochastic OBO with Access to First- and Inner Second-Order Oracles
Notation. Rdd is the d-dimensional real space; R4 and R4 denote its nonnegative and positive orthants. Bold lowercase letters (e.g., x) represent vectors, (x,y) is the inner product, and |I-Il the Euclidean norm. Vx denotes the gradient, and V2 = Vx A function is L-smooth its xy gradient is L-Lipschitz. The projection onto a convex set X' is (z) argmin 2||x z|I2. We use [T] for {1.... T). E|-] for expectation, and ((-) to hide
constants.
Stochastic OBO Setting, Let T be the total rounds [67]. Define x, E X Id as the decision variable and fe : X' x Rdd as the outer objective. The inner decision variable and objective are y: dd and gr X x d2, where the optimal inner decision is:
(x) E argmin go ()(x,)) == SanDoit (x(xx.))))) yERd,

---

Further, we have
==
Here, (D)., Dg.t) denote data distributions time Our setting is stochastic, with only noisy evaluations of functions, gradients, and Hessians. Unlike OSO [72], where true losses are revealed, in OBO the outer function fx(x, y7 (x)) inaccessible for updating x, and is generally non-convex
in x, making standard regret notions from online convex optimization [33] unsuitable.
Given sequence {ar E R ) we define the following notion of bilevel local regret:
T Σ
BL-Regr ==
E
Px,a,
(xi; XX
with
(2a)
t=1
Px.a. (x4; yx
x; 1x--11x(x - (F a4
(2b)
The local regret (2) compares the leader's decision x₁ to the stationary points x satisfying yf (xF))) = 0. This can also be viewed as dynamic local regret, as the baseline Px.a, (xt: [x yf
corresponds to a stationary point of the leader's 's objective ft.
Previous work (nonconvex) OBO examined un- constrained local regret using window-smoothed ob- jectives: Fr y) = (1/w) E (x. For w. and X' = Rd, this reduces to (2). [67, 50] showed that ofT) ensures sublinear regret under while rapid changes
Fix, v:) 2- -0G+ - a,l' sin(bare") y,)= -0x+ ax)" sin(e-y))
slow variations in can lead to deviations. However, smoothing may mis- represent regret (Figure 1). This paper introduces new projection-basse local regret notion (2) with- out smoothing, and establishes sublinear regret for constrained OBO.
Online Gradient Descent (OGD). One of the most widely used algorithms for online (single-level) op-
Figure 1: Smoothly and rapidly changing fr in OBO with ge( yr) = (yt cos( (r,)) )
timization is OGD [72]. The procedure for OGD is as follows: For each E [T], the algorithm selects
ae + 0.5 sin((), b. + sin(0.5(). and G. 10b,
X, X, observes the function fo X C Rd R,
and updates according to
X = Ixx (x: at (x))),
a2 > 0.
(OGD)
In the following, we adapt OGD to OBO and introduce a novel framework that requires limited feedback and can utilize 70 updates within single-loop structure.
To adapt OGD to OBO, [67, 50, 8] developed a variant alternating between inner and outer OGD, achieving sublinear bilevel regret bounds. We introduce new search direction that enables sublinear bilevel regret without window smoothing. To compute the hypergradient V fx y (x)) where ył (x) is defined in (I), since Vygr yJ (x)) O, using the implicit function theorem, yields
yz = Vxfi (x, yx + Vyy (x, (x).
(3)
where vx) E Idd is the solution to the following linear system:
V&gi (x, yx)) (x) + Vy.i (x. yx))) = 0.
(4)
As the exact yJ (x) is not available, we estimate the hypergradient of ft at (x, y) and introduce an auxiliary variable == v(x,)) y) effectively decouple the nonlinear structure in V fe(, y7 (x)), i.e.
fx( == Vxfí(x, + V2 (x V..
(5a)
where serves as an inexact solution to the linear system
y. (x,y) v. vyf((x,)) =
(5b)
3

---

Algorithm SOGD
Require: (X1, V1) E X x Rd x 2p: E R4+:T E N; stepsizes {(ar. 3z, 5e) E R ME
parameters {(7h, X1; To) m)]E= E (0, 1); 24 == (x), For 1. to T do:
S1. Draw samples B, and B, with batch sizes b and b. Get search directions d'. d.. and d.:
(z B.) (z:
(9a)
d' d (z:: [3) + (1 1) (dd diy (z.-1;
d (z;; B,) fyf((z;; Vzgi (zz; B:) Vtn
(9b)
d' d (z:; B,) (1 (d - d!' (2 BB)): d (z;; B,) f (B)) xy (z B:) Vt:
(9c)
d. dxx (z:: B.) + (1 (1-1)) (d] - -d, ( B,)).
S2. Update inner, system, and outer solutions:
ye+1 = Yt B,dy, vi+1 IT z, [vr - 6,dM], X++1 = Txx(x, a.d,).
An accurate solution of (5b) is crucial for tight regret bounds. [67] assumes an exact solution, which is restrictive in large-scale settings. To address this, [50] proposed an efficient OBO algorithm with window averaging, using CG methods solve (5b), which is equivalent
1 || (x, + Vyfi(x,y)
min
2
Next, we introduce novel search direction that enables both first- and ZO stochastic OBO algorithms to achieve sublinear bilevel regret without smoothing. We first state the following lemma:
Lemma 2.1. Let w = 1, W = 1/1 and v = 1) fofor Tj (0, in the window-smoothed
gradient V (X,, B,) = W ΣE ( B)- where B. = -E.,,,....,6 Lr,b} is
1
drawn ii.dd from DJ.-- Then, Ft, y:: B.) EE= 711 7)' V (x, yj; and we have
V F yti B,) di with dØ = fe yr; B,) + (1 n) and df = w (xx for all t 2.
Proof is given in Appendix C.I. As shown in Lemma 2.1, for a specific choice of w and W, the time-smoothed gradient forms a recursive momentum-type search direction. However, achieving sublinear regret in stochastic OBO requires large-window smoothing (w = o(T)) [67, 50, 8). To address this, we propose the following search direction:
de (x,,, yr; B.) + (1 m)d; + +(1 () Yti B.) 11
(7)
This direction is used for updating x, with similar updates for y and v, as discussed below and detailed in Algorithm 1. The quadratic formulation of (5b) in (6) motivates single-loop methods such as [15].
Building on this, we propose Simultaneous Online Gradient Descent (SOGD) for constrained OBO, presented in Algorithm 1. At each step, SOGD jointly updates the follower variable yr, auxiliary variable Vt, and leader variable x; using batches B, sampled i.i.d. from D,, and Dg... Step S1. only requires computing Hessian-vecto products, avoiding explicit computation of Vigge or V2y Step S2. uses the projection: where
Et, and B, = . C,,
1 Il,, (v) argmin 2, 1-vv-- 2|2= min {1, P |
V.
Zp = {v d2 || S pp.
(8)
Unlike OAGD [67] with alternating loops, and SOBOW [50] using CG, SOGD performs a single OGD step for all variables.
Assumption 2.2. ge (x(x,)) y) is twice continuously differentiable and sty-tronggyy convex y for all E X,t [T].

---

Assumption 2.3. Let z = y and z' |x where x, x' E A' A'and y.y's E R2,, For any 2, z'.
and E [T]:
B1. 36,00 E R4 s.t.
[z) fx(x <
B2. 76,1 R4 s.t.
Vf((2: {s) V 61)
B3. 36,,1 E4, s.t.
(gi(z; (t) (g) - 6.2
B4. 3gy E R2 s.t.
Vigi(z; (:) - (2
Assumption 2.4. For any E [T]. (x, S M for some M E R++ and any x E X.
Assumption 2.5. There exist constants Øg. Byy gwy Sy: fx such that, for all z = yx Vyfe(2)]12 s of C5. V(((((() Vxfe(z)]1 Jx
CI. E V V (z: () < 0
C4. V
C2. E V (1) (2)( S Jwy
C3. E Xy (x (z)]l I Dxy
Throughout this paper, we define
0² 2
6 Syy 1
+
2
+ 0 8xy
+ to²
fx
(10)
Assumptions 2.2 and 2.3 standard in BO [12, 43] and OBO [67], and hold for many bilevel
ML problems [22]. Assumption 2.4 is typical in non-convex OSO [36, 50), while Assumption 2.5
assumes unbiased stochastic gradient, Hessian, and Jacobian estimators with bounded variance [12].
Achieving sublinear dynamic regret is generally infeasible under arbitrary time variations [7]. Prior analyses [67, 50] bound regret by enforeing regularity on the comparator sequence. To attain sublinear regret, [67] introduces the following regularity metrics for bilevel sequences:
Hp.
sup I (x)]I", xEX
VT VT=
Σ sup sup (x. (x))) (II) XEX
Path-length Hy.7 measures changes in the follower's costs, while Vr captures the leader's objective smoothness. We use path-length for the follower and function variation for the leader due to the follower's strong convexity (Assumption 2.2) versus the leader's nonconvexity, Another regularity is the sequential gradient difference of the outer objective:
Dx.T
sup (x (xI((x,)))* x.y
(12a)
Dy.: = Σ sup Vyll/ - vyfr(x, x.y
(12b)
As in [41, 31J, Dx.T and Dy, measure the gradient drift of ft relative to ft-1 for x and y, respec- tively. We define deviations in the gradient, Hessian, and Jacobian of the inner objective as:
T
Gy.r Vy9h (x). (x).
Gyv.T
Vy (xx, vn) (x)(
Gxy.T
Σ (2 xx).
(13)
1=2
We introduce the following notations for simplicity:
Ar = E₁ + Vr, where (Vr, Hp.r) are defined in (11), and
Vr = H2r + Gr Dr,
(14)
Ei = |y (x + [[v - vI Gr Gy.r + Gyy.T + Gxy.T,
(15)
Dr = Dx,T Dy.T.
By accounting for both Dr and Gr, we can represent the variations in the environments of OBO.
Theorem 2.6. Let ( 9 be the sequence of functions presented to Algorithm 1, satisfying Assumptions 2.2.. For all t E [T], let
1
a = (c t)1/3
Bg = Cga4,
de = =cat; b= b 1,
2+11 = C,
Mht1 c
det1 = cxa2
(16)
5

---

Here, c, CB, Cay Cpp and ex are specified in (107). Algorithm 1 guarantees:
BL-Reeg S ( + Ar) + +T)
(17)
where a and (Ar, 1r are defined in (10) and (14).
Remark 2.7 (Stochastic Regret Guarantee for OBO and OSO with 1). Theorem 2.6 bounds the regret of Algorithm 1 without window-smoothing, based on the regularities in (14). We note that the average dynamic regret Bl.-Rgry/ T O (O + Ar) T-1/3 remains sublinear under suitable conditions on Âr, Vr, and a. Specifically, if ÅT - o(T2/3), Vr o(T2/3), and (TT23)) then the dynamic regret grows sublinearly, i.e., BL.-RegT oT)); see Appendix B.2 for further examples and discussion. This result also yields sharper 7 T regret- improving over the T- o² bound for stochastic OBO [8] and removes the need for window-smoothn [8, 67, 50, 40]. For OSO, this result surpasses the 7-1/2 rate in [31].
Stochastic OBO with Zeroth-Order Oracles
Black-box optimization arises when gradients unavailable [11]. We study ZO-OBO methods with limited access to leader and follower objectives. Let s E RR and E ddd be vectors uniformly sampled from unit balls and B2. Given smoothing parameters p (Pa Pr), we define Gaussian- smoothed objectives using [59]:
St.p (x)))
E [f(( + P28. (x) + (r);
where
(18)
(s.r.E.)
(7(x) arg min Sr. (x, y) == E
( + por;
(19)
yEad2
(s.r.C.)
To solve stochastic OBO with (18), need obtain the hyper-gradient of ft.p in (18) (x,
Vle,(xx = (x. + Sy (x, (77 (x). where
v.7 is the solution to Vigt. (x, (x)) (x) ft (7)) O.
(20)
Obtaining y (x) closed-form usually a challenging task, so it is natural to use the following gradient surrogate. At any (x, y), introduce auxiliary variable v(x,y) and define:
ft,p(x, == V vxft,p(x,y) + xy It. (x,
where
(2la)
v is the solution to Vy (x V Vyft,p(x,)) =0
(21b)
To do so, we also introduce di d',p and di,p as follows:
(x (x,)) Vysr,o(x,y),
(22a)
d x, v) = Vyft,p(x))) + Vyge (x,y) v, d (x (xft,p(x,)) + V (x,y)
(22b)
(22c)
Next, we approximate these directions using stochastic zeroth-order oracles (SZO), which produce the quantities V. fx,, y: Et), (x y:), (x &t), and (x, y:). These are unbi- ased estimators of the true gradients (x.,), V px y), (xfr,p(x.y) y), and V (x.t,p(x,)) respectively, shown in [20], such that the following assumption holds:
(r.5.) fxx((x = Vylt,(x,)),
(x = Vxft,((x
(x.E.)
E (n.5.)
((g((x.):Gi) = (x
IE (B.Ce)
Vx9i(x y: = Vx (23)
Specifically, following [62], we estimate the gradient of function h Rd R. querying at x As and x + As, yielding an estimator (d/2A) (h(x As) - h(x As)) s. Using this strategy, the finite- difference estimation of Vgt y), denoted by Vg, y), is constructed for given smoothing

---

Algorithm 2 ZO-SOGD
Require: In addition to parameters in SOGD, choose Pv, Pro Ps E R++. For & to do:
$1. Draw samples B, and B, with batch sizes b and b. Using (24)-26),, get:
d (z:: B.) Vygr(zz: Bi),
(27a)
ay = di (z:: B.) + (1 v) (d) (2(-1; (zri
d (z B,) (z; + V,99 (zz; B.).
(27b)
(1-x) (d) - dxy (z Be)), d (z:: B.) Vxfi ()) V (zr Bb)
ay =
(B)) + -
(27c)
d = d (ze: 1B.) + (1-m) )d d, (zt BB)),
S2. Update inner, system, and outer solutions:
Y++1 y - B,dy, Vi+1 = 2lz, |v. - 6,d7), Xt+1 = 11x xt a,d
[v,
parameters (Ps: Pr), and set B, - (S..1.... Se. drawni.ia from Dg.t, as follows:
b
(y = d2
Σ
( - 90(x. Per:: (ta))
(24a)
2hpr
i=1
(x Br) = d1
(x PaS,, - gx(x Pass, yi,,)) s;.
(24b)
2bps
i=1
Similarly, we estimate fc,i,e(x. y; B,) and yx respectively, using a batch B, Er,b) drawn i..d. from Dy by
d2
y;;
Σ + - Jx(x, pert: pere)
(25a)
2hpr
i=1
d1
Vxf((x,y;B)) B.) 2bps 1=1
Σ ( + p - f((x PeSi, y:
(25b)
Furthermore, given a smoothing parameter Pv > O, we approximate the Hessian-vector product Vz and the Jacobian-vector product V2 py y)v the finite difference between two gradients, respectively, as
(x: = 1
+ - G.,:
(26a)
2bpv
22 (x = 26p
1
V (x, + (.)) - -
(26b)
1=1
Using (24)-266), the first-order terms in (9) are approximated by dy. åy and d in (27). The approximations in (26a) and (26b) introduce errors in the hypergradient, which must be controlled. (26) depends on the dimension of y. as ZO optimization [59, 62]. The projection IIz, (8) bounds v, controlling variance in and updates for convergence.
Assumption 3.1. There exist constants 7gy o oz, o such that, for all |x y):
DI. E (2; - (v9t,p(2))) 5 "y'
D3. ElIVy/((;;E)) (2))2 S 00,,
D2. E (x (z; G+) Vx9t,p<>)1 62 9x'
D4. ((IV))((Z;E.) (xfr,p(2)12 s S0
7

---

Assumption 3.1 is analogous to the upper bound on the variance of stochastic partial gradients discussed in [54, 68]. We simplify the notation by introducing the following shorthand.
8² 0 : + o Sx + +0j, + +
(28)
Next, we establish regret bound for ZO-SOGD. Similar the previous results, we introduce regularity conditions for the smoothed functions defined in (18) and (19).
set of gradient variations at the perturbed point Inner Gradient Variations: In ZO setting, as follows:
T
T
Gv,T == Σ
(x + X21):
Gx.T ==
Σ
(xt + Xui),
(29)
1=2
1=2
where z ; (Xt- Y + Pv Vt-)), 2s ;= (x--1181-1 Pv Vv and
X1t Vygi Vygt-1 )1,
X2t == V (2,
Vygt- 12g )|(
X3t == (x - Vx9t-1 ||
Xat = Vxgi Vx9t-1 (z )ll
Further, for simplicity of notation, we define
+ Dr Gy,T, where (Vr, HnT)) and (Fi, Dr) are defined in (11), and (15), respectively. Moreover, Gy,r and (Gv,T' Gx,T) are defined in (13) and (29), respectively.
å-:= F1 + VT
TT= H2, + GV. Gx.T:
(30)
Theorem 3.2. Let ((t,g:)) be the sequence of functions presented to Algorithm 2, satisfying Assumptions 2.2-2.4 and 3.1. For all E (T). let
0 = (d1 d2) (c+
B = Cg0+ts
= =c
741 = C,
Mt+1 = C,at:
A411= = Cx0
Pv = cras,
dTT
PS
d
T1/3
T2/3
b (d1 + d2)3/2'
b
(31)
(d1 d2)33/4
where c, cg, Co, Cup, Cy. Cv. and eλ are specified in (226). Let p = f/,0/ Mg for the set Zp defined in (8). Then, Algorithm guarantees:
BL-Reg, 00 ((d dz) Tb (0² + Ar) +(d1 + +
(o²+
where 8² and (Ar, (T) are defined in (28) and (30).
Theorem 3.2 bounds the regret of Algorithm 2 without window based the regularities in (30). We note that the average dynamic regret BL-Regr/T - ((di, + //2)3/4T-22 2/3 (02 + Ar)+
(d1 +
remains sublinear under suitable conditions on Åz. Lr, and &. Remark 3.3 (Regret Guarantee for Zeroth Order OBO). Theorem 3.2 provides the first regret guarantee for OBO with access only to noisy function evaluations of the leader and follower. The dimensional dependence Old, + d2) in Theorem 3.2 aligns with optimal results for simpler offline min-max problems [39]. The bound also depends on the sample sizes 6, b and smoothing parameters Pr: Ps at each iteration.
Remark 3.4 (Improved Regret for OSO). Our dynamic regret for single-level non-stationary optimization is O(d, + /2)33/77-2/3 + Es + V₂ + Dr)), improving the result in [60], which is O(T-1/2/2V)) [60] proposed zeroth-order stochastic gradient descent algorithm for unconstrained, non-convex, time-varying objective functions, achieving a regret bound of OTT-1/202 (dWr) using a two-point gradient estimator, where Wr bounds the nonstationarity. Additionally, [29] showed that the local regret for standard online stochastic gradient descent with the standard two-point gradient estimator [1] is V/2-
4 Experimental Results
In this section, present experimental results for two applications: online black-box attacks on deep neural networks and parametric loss tuning for imbalanced data. Code is available at a Additional experiments and details on hyperparameter tuning are provided in Appendix E.
8

---

1.0
4.0
Z0--GD
Rurdire (secords)
1.5
20.0 CostrvGD
20.0 Adan
20 G Sge6G
I1.9
3,5
70-0 StrGD
20-G-Adam
Co00-CaaevGD
1.0
20 506D (jers Mbke)
[sars]
Texting
0.5
20.0.6D
20.0-SgrCD
2.0
Z0,00GD jours Adam)
20:500 (ours]
11.5
0.4
13
20-50GD
10
70-5001
(exes Adam)
1150
150
175
125
175
Figure 2: Performance comparison (tean of optimizers including ZO-O-GD, ZO-O-Adam, ZO-O-SignSGD, D0--O-ConservSGDD, ZO-SOGD, and ZO-SOGD (Adam) on online adversarial attack for MNIST data across five runs.
Bilevel Optimization for Black-Box Adversarial Attacks (BBAA) Deep neural networks are subtly perturbed to mislead classifiers. These examples can fool models without access to their internals, as in [11,52, 13]. We first review the 7O single-level formulation for BBAA [11]. Let (a, be clean image IRd with label define a' = + where is the adversarial perturbation. Let ) == [-5, 5]6, and L Rd R be the black-box attack loss. For a given hyperparameter O, the BBAA problem is:
vulnerable to adversarial examples-inpee
{1,-... J), and
min YEY
Σ l(a, + y) A////12.
(32)
m
To adapt (32) to our OBO, consider OBO for supervised learning: each timestep t, new samples (a,, by) E DD == (Dyal D are received, where a, Tada is the feature vector (image) and by E R is the corresponding target. Note that the correct decision change abruptly. We consider S-stage scenario where (x,, y (xt)), represents the best decisions for the s-th stage, for all E [S]:
x argmin XEX
f (x):
(x( argmin yEy
g Y!)
(33)
Vr; g y(; D
f(a
+y.) +
Joc [ye]i
DD
IDD
f(y:(x)):
Σ
f(a (4)
+y).
(34a)
D
Here, (2) REDY and {a (6) Ne are batches of training and validation samples timestep I; a the ith sample in that batch; and [x:]. and [yr], denote the ath component of x2 and yı, respectively.
We normalize the pixel values to y. For an untargeted attack, the loss in (34) is {(aa) ma Z(a -x,, where Z(a{); is the prediction score for class given input a/ = a, + Yr. and > 0 controls the confidence gap. In our experiments, we set к 0. Eq. (33) introduces the first OBO formulation of BBAA, Using a vector x E R for hyperparameters instead of R++ in (32) enables finer control over model components, enhancing performance for complex models and heterogencous data [53]. For a fair comparison with single-level BBAA, we replace with a fixed vector multiplied by each component of y in (32). We compare our Z0-SOGD and ZO-SOGD (Adam) with the following competing methods in the online setting: ZO-O-GD, single-level method that updates y: with fixed x at each timestep using ZO gradient descent [59]; Z0-O-Adam, single-level method that updates y; with a fixed x at each timestep using 70 Adam [45, 13]; ZO-0OSSigNGDD a single-level method that updates yr with a fixed x at each timestep using 70 SignSGD [6]; and Z0-0-ConseerSGD. single-level method that updates y, with fixed x at each timestep using ZO Conservative SGD [44]. Note that RO-SOGD (ours, Adam) is a variant of our algorithm with adaptive stepsize, similar to that of [45].
max(2
We evaluated the proposed algorithms based on runtime, test accuracy on perturbed samples, and the infinity norm of y,. Figure 2 compares the methods. The left panel shows that ZO-SOGD has slower runtime than single-level baselines due to outer-level optimization on x. The middle panel illustrates that accuracy decreases as the adversarial attack strengthens, with ZO-SOGD outperforming ZO-O-GD and -Do--onner,GGD, while ZO-SOGD (Adam) surpasses Z0-0-Adaa and all baselines. The right panel indicates that the infinity norm of y, increases over time for all methods, reducing accuracy. However, perturbations remain minor, with max yt not exceeding demonstrating that ZO-SOGD achieves effective attacks with superior performance.

---

OAGD (Neumann) SOBOW (CG)
Balanced Training Accuracy
1.
Belerced Testing Accuracy
1.13
Runtime (secords)
0.5
0.6
9.4
2.1
(Neumann)
(Nrumann)
00
02
S0BOW
SOBOW (0G)
50GD
50GD
100
150
200
250
9.0
350
600
50
100
150
200
250
300
350
600
50
100
150
200
250
300
350
400
Figure 3: Performance (mean on online parametric loss tuning with distribution shift on MNIST across five runs, comparing OGD [72], OAGD [67]. SOBOW [50], and our SOGD,
Parametric Loss Tuning for Imbalanced Data Imbalanced datasets are common in modern machine learning, causing challenges generalization and fairness due underrepresented classes and sensitive attributes. Deep NNs often overfit, seeming accurate and fair during training but performing poorly during testing. common solution designing a parametric training loss that balances accuracy and faimess while preventing overfitting [49]. We consider an optimization problem similar to that in (33). For a new sample (a;, bt), the follower and leader incur a parametric and balanced cross-entropy loss, respectively:
e (nllss
elrc(as))o,
((; log
((x((x));DT")) -Uh, log Σ elvx(ai)l,
(35)
E/= eulii(aa)ls
Here, X, = ( represents the logit adjustments, with j indexing the J classes, and uy is the reciprocal of the proportion of samples from the j-th class to the total number of samples [49].
In (35), (x,) is the follower conditioned on the leader, and (a))), the logit for class be on sample tive. We compare SOGD with OAGD [67]. a static method using the Neumann series, and SOBOW [50], a dynamic method using conjugate gradients (CG). Experiments were conducted on MNIST [48] with batch size 64. We evaluated cumulative runtime, test accuracy, and balanced accuracy, defined as + Σ PaIND, [argmax, ; (a))()))).) = = where DD is the class-j sample distribution [49]. Learning rates were tuned as 3g = 6, = E f0.001. 0.005, 0.01, 0.05, 0.1), a, = a {0.0001, 0.0005, 0.001, 0.005, 0.01). and % de 17. = y E {0.9, 0.99, 0.999). Both OAGD and SOBOW used 5 iterations for their respective system solvers.
The follower Y: uses 4-layer CNN, inducing nonconvex bilevel objec-
We evaluated performance imbalanced (0.4') to a balanced (0.8*) distribution for each class (i = 0, 1.....9) 9). Figure 3 (left) shows SOBOW's longer runtime due to CG complexity, while SOGD is the fastest with simultancous updates. Figures (middle, right) show accuracy gains as balance increases, with SOGD achieving competitive accuracy.
400 timesteps in four 100-timestep phases, transitioning from
Conclusion
This work introduced a novel online bilevel optimization framework that overcomes the limitations of existing algorithms, which often depend on extensive oracle information and incur high computational costs. Our method leverages limited feedback and zeroth-ore orderr updates for efficient hypergradient estimation and simultaneous updates of decision variables, achieving sublinear bilevel regret without window smoothing. Experiments on online parametric loss tuning and black-box adversarial attacks validate its effectiveness. A limitation of this study is that the results focus nonconvex regret bounds, without extending guarantees to convex settings.
Acknowledgments and Disclosure of Funding
We thank the reviewers for their valuable comments. The work of DAT was supported by Samsung SDS Research America, Mountain View. The work of GM was supported in part by NSF grants DMS-20 RMS-23486440 and
10

---

References
[1] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28 40. Citeseer, 2010.
[2] Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pages 18-29. PMLR, 2019.
[3] Alireza Aghasi and Saeed Ghadimi. Fully zeroth-order bilevel programming via gaussian smoothing. arXiv preprint arXiv:2404.00155 2024.
[4] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances in Neural Information Processing Systems, 31, 2018.
[5] Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pages 257-283. PMLR, 2016.
[6] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. Signsgd: Compressed optiiiaation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[7] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- fions research, 12255:1227-1244 2015.
[8] Jason Bohne, David Rosenberg, Gary Kazantsev, and Pawel Polak. Online nonconvex bilevel optimization with bregman divergences. arXiv preprint arXiv:2409. 10470 2024.
[9] Jerome Bracken and James McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44) 1973.
[10] Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, and Rémi Munos. Online optimization in x-armed bandits. Advances in Neural Information Processing Systems, 21, 2008
[11] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26,
2017.
[12] 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, 34, 2021.
[13] Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zeroth-order adaptive momentum method for black-box optimization. Advances in neural information processing systems, 32, 2019.
[14] Caroline Crockett, Jeffrey A Fessler, al. Bilevel methods for image reconstruction. Founda- tions and Trends@ in Signal Processing, 15(2-3):121-22) 2022.
[15] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXi::2201.13400 2022.
[16] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
[17] John Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions Information Theory, 61) 2015.
[18] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1 135. PMLR, 2017.
11

---

[19] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online letanng In International Conference on Machine Learning, pages 1920-1930. PMLR, 2019.
[20] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprini cs/0408007, 2004.
[21] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning, pages 1165- 1173. PMLR. 2017.
[22] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Muchine Learning, pages 1568-1577. PMLR, 2018.
[23] Xiand Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and con-stationary regret. In International Conference on Artificial Intelligence and Statisties, pages 233-243, PMLR, 2018.
[24] Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the information-adaatiie variants of the admm: an iteration complexity perspective. Journal of Scientific Computing, 76:327-363, 2018.
[25] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-25 2368, 2013.
[26] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1- 2):267-305, 2016.
[27] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1802.0280..02244 2018.
[28] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32, 2019.
[29] Ziwei Guan, Yi Zhou, and Yingbin Liang. On the hardness of online nonconvex optimization with single oracle feedback. In The Twelfth International Conference Learning Representa- tions, 2023.
[30] Ziwei Guan, Yi Zhou, and Yingbin Liang. Online nonconvex optimization with limited instan- taneous oracle feedback. The Thirty Sixth Annual Conference on Learning Theory, pages 3328 3355. PMLR, 2023.
[31] Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via a proximal-gradient approach. In International Conference on Machine Learning, pages 4008-4017. PMLR, 2021.
[32] Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and-bound rules for linear bilevel programming. SIAM Journal scientific and Statistical Computing. 13(5):1194-12) 1217, 1992.
[33] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- tion, 2(3-4):1573325, 2016
[34] Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
[35] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learming, 69(2): 192, 2007.
[36] Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games.
In International Conference on Machine Learning, pages 1433-1441. PMLR, 2017.
12

---

[37] Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non- convex optimization with imperfect feedback. Advances in Neural Information Processing 3 33:17224-117255 2020.
[38] Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. peroth-order non-convex learning via hierarchical dual averaging. International Conference on Machine Learning, pages $192-4202. PMLR, 2021.
[39] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first- order momentum methods from mini minimax optimization. Journal of Machine Learning Research, 23(36)11-7,, 2022.
[40] Yu Huang, Yuan Cheng, Yingbin Liang, and Longbo Huang. Online min-max problems with non-convexity and non-stationarity. Transactions on Machine Learning Research, 2023.
[41] Yu Huang, Yuan Cheng, Yingbin Liang, and Longbo Huang. Online min-max problems with non-convexity and non-stationarity. Transactions on Machine Learning Research, 2023.
[42] Kaiyi Ji, Zhe Wang. Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International conference on machine learning, pages 3100-3109. PMLR, 2019.
[43] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[44] Bumsu Kim, HanQin Cai, Daniel McKenzie, and Wotao Yin. Curvature-aware derivative-free optimization. arXiv preprint arXiv:2109.13391 2021.
[45] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2014.
[46] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681-690, 2008.
[47] Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The hedge algorithm on continuum. In International Conference on Machine Learning, pages 932. PMLR, 2015.
[48] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. wwwp:lllww.c.cce.aiiiiiee wwt..//o///ee/ii....... 2, 2010.
[49] Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Au- tobalance: Optimized loss functions for imbalanced data. Advances in Neural Information Processing Systems, 34:3163-3177, 2021.
[50] Sen Lin, Daouda Sow, Kaiyi Ji, Yingbin Liang, and Ness Shroff. Non-convex bilevel optimiza- tion with time-varying objective functions. Advances in Neural Information Processing Systems, 36, 2024.
[51] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:180.0000 09055, 2018.
[52] Sijia Liu, Jie Chen, Pin-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2018.
[53] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics, pages 1550-1552. PMLR, 2020.
[54] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-stroonlyy-oom Information Processing Systems, 33:20566-20577, 2020.
minimax problems. Advances in Neural
13

---

[55] Yibing Lv. Tiesong Hu, Guangmin Wang, and Zhongping Wan. A penalty function method based on Kuhn-tucket condition for solving linear bilevel programming. Applied Mathematies and Computation, 188() (::08 813, 2007.
[56] Parvin Nazari, Ahmad Mousavi, Davoud Ataee Tazzanag,, and George Michailidis. A penalty- based method for conmumication-effiiee decentralized bilevel programming. Automatica, 173:112039, 2025.
[57] Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Adaptive first-and zeroth-order methods for weakly convex stochastic optimization problems. arXiv preprint arXiv:2005.09261, 2020.
[58] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming. 103:127-152, 2005.
[59] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2)527-5666 2017.
[60] Abhishek Roy, Krishnakumar Balasubramaniaa, Saeed Ghadimi, and Prasant Mohapatra. Stochastic zeroth-order optimization under nonstationarity and nonconvexity. Journal of Ma- chine Learning Research, 23(64): 2022
[61] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[62] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
[63] Daouda Sow, Kaiyi Ji, and Yingbin Liang. On the convergence theory for hessian frree bilevel algorithms. Advances in Neural Information Processing Systems, 35:4136-4149, 2022.
[64] Heinrich von Stackelberg. Theory of the market economy. Oxford University Press, 1952.
[65] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. Learning intrinsic rewards as a bi-level optimiza- tion problem. In Conference on Uncertainty in Artificial Intelligence, pages 111-120. PMLR, 2020.
[66] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pages 845-861, PMLR, 2020.
[67] Davoud Ataee Tarzanagh, Parvin Nazari, Bojian Hou, Li Shen, and Laura Balzano. Online bilevel optimization: Regret analysis of online alternating gradient methods. In International Conference on Artificial Intelligence and Statisticy, pages 2854-2862. PMLR, 2024.
[68] Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian Ma, and Meisam Razaviyayn. Zeroth- order algorithms for nonconvex minimax problems with improved complexities. arXiv preprint arXiv:2001.077 1099, 2020.
[69] Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Achieving (c-115) complexity in hessian/jacobian-free stochastic bilevel optimization. arXiv preprint arXiv:2312.03807, 2023.
[70] Yan Zhang, Yi Zhou, Kaiyi Ji, and Michael M Zavlanos. Boosting one one-point derivative-free online optimization via residual feedback. arXiv preprint arXiv:2010.07378, 2020.
[71] Wei Zhou, Yiying Li, Yongxin Yang, Huaimin Wang, and Timothy Hospedales. Online meta- critic learning for off-policy actor-critic methods. Advances in Neural Information Processing Systems, 33:17662--1666 17673, 2020.
[72] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
14

---

Contents
1 Introduction
2 Stochastic OBO with Access to First- and Inner Second-Order Oracles
3 Stochastic OBO with Zeroth-Order Oracles
4 Experimental Results
5 Conclusion
10
A Related Work
16
Additional Preliminaries and Notations
16
B.1
Preliminary Lemmas
16
B.2 Examples Illustrating Regularity Conditions
17
Proof of Regret Bounds for Simultaneous Online Gradient Descent (SOGD)
19
C.1 Proof of Lemma 2.1
19
C.2 Bounds the Inner Decision Variable
19
C33 Bounds on the Linear System Solution
24
C,4 Bounds on the Gradient Estimation Error of Outer Objective
30
C.5 Bounds on the Outer Objective and its Projected Gradient
33
C.6 Proof of Theorem 2.6
35
D Proof of Regret Bounds for Zeroth Order SOGD (ZO-SOGD)
43
D.I Auxiliary Lemmas for Proof of Theorem 3.2
43
D.2 Perturbation Bounds for OBO Objectives and Their Smoothing Variants
D.3 Bounds on the Zeroth-Order Inner Solution
47
D.4 Bounds on the Zeroth-Order System Solution
51
D.5 Bounds on the Zeroth-Order Estimation Error of Outer Objective
60
D.6 Bounds on the Zeroth- Zeroth-Order Objective Function and its Projected Gradients
64
D.7 Proof of Theorem 3.2
70
Hyperparameter Tuning Results
80
15

---

A Related Work
BO was introduced in game theory by [64] and modeled mathematically in [9]. Initial works [32, 55] reduced it to single-level optimization. Recently, gradient- based approaches have gained popularity for their simplicity and efficacy [21, 27, 43, 12, 56], though they assume offline objectives.
OBO was initiated by [67]. proposing the OAGD method with regret bounds. [40] developed algorithms for online minimax optimization, special cases of OBO with local regret guarantees, [50] introduced SOBOW, a single-loop optimizer using window-smoothed functions and multiple CGs for nonconvex- wwwpeeeex-ttoogy-ooooo more general performance measure for constrained objectives, focusing on the original functions and their regret; See Table for comparison.
cases. Unlike these works, we propose using projected gradient as
Single-Tevel Regret Minimization. Single-level online optimization predominantly focuses on convex problems, either with static or dynamic convex regret minimization [72, 34, 61]. Non-com Non-convex
online optimization [36, 30, 29] poses greater challenges than its convex counterparts [61, 72, 35, 7]. Notable contributions in this field include adversarial multi-armed bandit algorithms [10, 37, 38, 47] approach [2, 46, 66]. Hazan et al. [36] introduced window-
and the Follow-the- -eroowtte--eruuree----e Pe-tt-rer-----aeeeee smoothed local regret for gradient averaging in non-convex models, which Hallak et al. [31] extended to non-smooth, non-convex problems. Inspired by their work, we employ local regret for Online Bilevel Optimization (OBO) without window- window-smoothing.
Zeroth-Order Optimization. Single-Level ZO Optimization has been widely studied in both offline [25, 17, 59, 57] and online settings [52, 29, 30, 70, 5]. We next review closely related work. Liu et al. [52] proposed ZOO-ADMM, a gradient-free online optimization algorithm utilizing ADMM. Guan et al. [30] studied online non-convex optimization with limited oracle feedback. Research on online non-convex optimization with bandit feedback includes work by Heliou et al. [37], which established bounds on global static and dynamic regret using dual averaging, further refined in [38]. Gao et al. [23] extended these ideas to ZO algorithms. Flaxman et al. [20] provided algorithms for bandit online optimization of convex functions using 70 gradient approximation. Our work closely relates to [63], which proposes a Hessian-fire method approximating the Jacobian matrix using a ZO method based finite differences of gradients. In contrast, method uses function oracles to approximate both the Hessian and gradients and is derivative-free We also point out the recent work [3] ZO stochastic algorithms for solving bilevel problems when neither the upper/lower objective values nor their unbiased gradient estimates are available. Their approach, limited to the offline setting, does not include numerical results, thus leaving its practical efficiency unclear.
B Additional Preliminaries and Notations
B.1
Preliminary Lemmas
We first provide several useful lemmas for the main proofs.
Definition B.1 (Projected gradient [26]). Let X' C Rd be closed convex set. Then, the projected gradient for any a4 > O and p E Rd4 is defined as
1
Px.,, (x:p) = _ (x-xt))
at
where
Ixx - (x-xxp)
(36)
and 1Ix H denotes the orthogonal projection operator onto set X.
Lemma B.2. [28, Lemma 13) I X - IR is a u stroonnyyyy convex function with respect to some norm || ||. and x" is the minimizer of f (i.e. x" arg minxex f(x)), then we have V x E X,
MI 11 < fxx f(xx) < 1 [VV((x))?
2
2μs
Lemma B.3. Suppose f(x) is Lmoothh, and x" E x Then, we can upper bound the magnitude of the gradient at any given point x E IRd terms of the objective sub optimality at x, as follows:
| < f(x) f(x*)= < -1 ||- x" x*112
(37)
2L
16

---

Lemma B.4. For any x, y E R the following holds for any >> 0:
(1 (1+2) |tyl
xx y| & (1 + +]|x|| +
We also utilize basic yet important property of the projected-gradient mapping.
Lemma B.S. [26, Proposition 1] Let Px,a, (x: (x; p) denote the projected gradient as defined in holds that
Definition I. For any x, P1, P2 E Rd and 04 >
(p (x:Pi) Px,, (x; S llpI - ppll-
Lemma B.6. [36, Proposition 2.4] Let Px,a, (x:p) denote the projected gradient as defined in Definition B.1. For any x, P1, P2 E Ra and 0q > 0, it holds that
(xx,o,(;;)) + p2)ll S 1Pxx, (x:Di)] ||p2||-
Lemma B.7. Let Px, (x: p) be as given in Definition B.I. Then, for any p E IRd and 042 > 0, we have
(p, Px,o, (x: 2 Pxx,o, (x:p)]
Proof. By the definition of xt, the optimality condition of (36) is
p+ aq
(x - x), xx 0, Vz E X.
Letting x, we obtain
(p.x- xxxxxx)2200 2 xx-x x x xx),
which can be rearranged to
(p, Px,a p)) = (p.x (p.x-xt)
2 o x x-x x x xt)
di
(x:
B.2 Examples Illustrating Regularity Conditions
Theorem 2.6 achieves sublinear bilevel regret when the variations VT and H2.r are o(T2/3) and /3T respectively. Below, we provide some examples of online optimization in both single-level and bilevel settings to illustrate when this occurs.
Example B.8. Consider function f((x) = ||A b1 where A, = [1,0; 71. b (1.
follows from (11) that VT
Et= maxx (xx f = 1l ( 1. and
T
1 (- - (++
V4
8
(w--))
(++1))
(---1) 1
(++
1-1+t
i(t -1) f(t 1(t-1)
T
t(t 1)2
Then, Vr s E 1- d1 =
As T + oo, Vr becomes bounded and approaches constant value, indicating that Vr grows slower than T itself.
17

---

Example B.9. Let
fi(x) [(-7.0) 0) if is even;
10,, (0,-
if is odd.
Then, VT= Er maxx [f((x) f(-1(x)) = (L)..
Example B.10. Let æ E X = |-1,1] C R. y I. and consider a sequence of quadratic cost functions
()) = 1
x 20( 20
+ 1 (v a(²)) 2
2
2
(x, = y (s (x-a;) ae
where af" = 1/t and (2) = 1/vl for all i E (T].
We have
(x) -,a
and
[e Di (x)) - 1x-1(x,iii111
1
(o+ + (1) - (x+ 20 (1)
1
(M](x)) -((i)) -21)²= - (z) 27
+ 2
2
1
(x2 + Axa, (1) + 4(a; 11))))
(x² + +4xa (1) + =((af_1)11]
2
+ ((x- de (2))22 2(x d )a + (a: (a()))2
(2) (2)
- -1--001---2-----00000-- + (a.ti
2x (ag a;- - di + 2 (a/ (a()))= (a
(1)
(2)
Taking the maximum over x and using x E 1-11,1]
(x)) x
= 2 a - 0-1 +
(1)
d + +
(2)
4-1
+2 [at ))) - (4 2 +2 (a 2
Since ut =
=1/( 1/l and (2) = 1/vi for all / E [T]. then we have
la," 1)) - a ~
1
|0
2 ~ 213/2'
(2
1/a - (a(h))
RM
1
1(a
02) (2)
2
~
1
131
7
Then, we get
T
T
Vr = Σ
sup |f( (x)) - fi-1
(i)) =
Σ
2
+
1
f2
2F3/2
(3
2=
1=2
The series DT 2 (2 + 207 + # converges, implying V7 = (1). Moreover, we have
T
T
H2T =
sup
- (z) (2)1 Σ
sup
|
a
(2)
- x + a
(2)
t=2
1=2
T
T
(2)
2
(2)
2
4t3
t=2
t=2
which implies 112T = =0(==)
To achieve Vy = o(3233) and H2, = (TT133), the changes the cost functions fr yI (x)) and y7 (x) should decay to zero faster than (1/tt)) with a > 1/3. For example, if the coefficients in the functions change as (1/t") with > 1/3, then the cumulative sum over T will be 2/33. When fc yi (xx) and y. (x) decay 0 then the total variation grows at most O (VT)..
18

---

C Proof of Regret Bounds for Simultaneous Online Gradient Descent (SOGD)
Proof Roadmap. We introduce Lemma C.2, which quantifies the error between the approximated gradient estimator, d'. and the true direction, y (x,, at each iteration. To bound the error of the lower-level variable, we provide Lemma C.4, which captures the gap yy -y? (xx) and incorporates the error introduced in Lemma C.2. Moreover, we provide Lemma C.6, which quantifies the error between the approximated direction of the momentum-basee gradient estimator, dy. and the true direction, Vigtt (2r) V. + Vyf((Zr), at each iteration. To bound
direction the momentum-bass
the error of the system solution, we provide Lemma C.8, which captures the gap ||ve+1 (x,)] and incorporates the error introduced in Lemma C.6. Moreover, we provide Lemma C.9, which quantifies the error between the approximated direction of the momentum- based hypergradient estimator, d,, and the true direction, Vxfi(z;) + V St (z:) vg, at each iteration. We also present Lemma C.I1, which provides an upper bound for the projection mapping and relates the three errors discussed in Lemmas C.4, C.8, and C.9. Finally, by combining these lemmas and appropriately setting the parameters, we achieve the desired result.
C.1 Proof of Lemma 2.1
Proof. By letting 1) for 1) E (0, 1), the window-smoothed gradient
1 w-1
VX, Yoi B,)
W
is equivalent to
1
Σ
(38)
W
j=t-w-1
Let d Ve,,o yr; B.). Then (38) is equivalent to
t-1
d. = W
1 V( + W
Σ
(1- (1=n))~(([(()),;;::))
j=t-=+
Since
(1 11)
[1-n)d]]
Σ
(1 - ---m)~--V(
W
j=t-w
we have
(1 1)
d
W v f BB) + n)d
( (X N
W
with f((-) = 0 for all < 0.
If w / and W then, we have
d = B,)
C.2 Bounds the Inner Decision Variable
In the following, inspired by offline BO [69, 15] and OBO [67, 50), we provide set of lemmas for the analysis of SOGD. We first present lemma that characterizes the Lipschitz continuity of the approximate gradients, as well as the inner and system solutions.
19

---

Lemma C.1. Under Assumptions 2.2 and for all x, E R. and the search directions
|d
and {d)) Jt=1 generated by Algorithm 1. we have
|| - y = M (1v: - -1ye-y((x:)) (xx))] + llve- vi(xx))))))
(39a)
||ay]] s M² (1xx- 1119--7766 x(x,)l + llv - -x((x)))))
(39b)
(x, - Vf((x' xf || - Ly ||x - x'11
(39c)
(x) - vi(x'] $ L ||x- x') ||;
(39d)
(x) - v[(xx)l S Lv || 1|1-xx111 x || where M, Mv. and (Iyy L Ing) defined in (42), (43), and (44), respectively.
(39e)
Proof. We first show (39a).
Using Assumptions 2.2 and 2.3, we have Vzg (x = Mg and
[1v (V3g (xx))) "Vy)
yyft (x,, (xx)))
6100
(40)
Mg
Observe that
| Jx
S IV -W..///.....-V//..........
|/v; Vx - (x,, St (I,, (x,))
V yo) (x,
V It (x,, yr Il1[v V2 - (xxxl
+ [Iv (xx) V2 xy yo) - (x.
f + f 11 - vx,(xx) + + - (x)))
Mg
3 (lyr - yx(xx)l + llv, vxxx)ll),,
(41)
where
My == V2 (e,s + l02610 ..
(42)
Mg the third inequality is by Assumption 2.3, and the last inequality follows from (40).
Next, we establish (39b). Since dy" == yx (x.)) + V3 (xt,
y
(X,, y7 (x:)) (x.,) O. we have
||d||
||d|- - dI
1|ve Vzggn (xt, yi) yx)(
(vi (xx:) V2 (xe, (x())) + xx
< (V399 (Xt, N1) (x. (x:)l
V (XL, Vi) (v. vx,(x)))
fx y1) Vy.f(xx,.,xx))))).
Then, from Assumption 2.3 and (40), we have
|| < 2, ll= - yi (x: vi (xx)) + lg ||, - vi (xx)ll + -
2 + t5,11 |ly: - xxx)))l + tg.
Mg
s My (lly: - (xx))] + 1|ve - vxx())))
where
My = /2 (92261 + t
(43)
Mg
20

---

The proofs of Eqs. (39c)-(39e) follow from [67, Lemma 17] by setting
byy Ng
Lv -1,,1- 1911
+
(la2
+
(44)
Mg
Mg
Mg
L, = 111 10
210
l9.26.12
(9/2 +
Ma
pg
where the other constants are defined in Assumption 2.3.
The following lemma is inspired by [69] and can be viewed as an extension of [69] to the online setting.
Lemma C.2. Suppose Assumptions B3. and C1. hold. Let {(xi, Yt, vo)) be generated according to Algorithm 1. For of defined as
el = d (x,,(x),
(45)
we have:
E|| 2 112 $ (1-77++) 48 8.1 Bllee11 + 2 o + 24(1 B x.|1?
El|x+1
+ +61 - 7 "
Vy9++124+111
+ +88(1 - (0(1-~++1) 3 (x))
(46)
Proof. From Algorithm we have
d' = Vy B441) + (1 (d) - (29+1(2;
Then, we have
E| El d V Vy 1²
E V 91++1 Z(- B141) + (1 (41) - (
E (1 N+1let + V (Vy9ti1
()9(+((2(-1)
(1 n+1) (V Vy B.41) -
which implies that
E| e (1 7411 1
()9+112(+1))
- (1 7 (Vyg++1 BB+1) - V (2:))2
< (1 7++1) 2 + V Bet1) - (y90+1
+ 2(1 7++ F
V y
B(+1)
Vydc+1 (z(+1)
V 3 (Z Be+1) + (z))11
< (1 - M+ 2 + 27/-1 b
+ 2(1 - - 3
 2e+1 B141) (y
Vyg++1 (zr; B.t1) (y))
where the second inequality follows from Cauchy- Schwartz inequality and Assumption C1.. Moreover, from Schwartz inequality, we have
E 11 1 < (1 1 + 27 -
+ 6(1 - (++1) V (z)) (2++(2+)1
+ 6(1 - P (x Vygt+ (Z
+ 6(1 "B Sy 1 B.+ - VyDc+ Be
21

---

From Assumption B3., we have
V (Z(+1) V (x,)2
S 2E| V, (x
(x
2B 2 (x)
S 260 E Xx+1 - + Blyy - -y
26 E||x++1 - x-112 + +2 3,
and
V (2 B(+1) V 111
< 2E -
V ( 1: (x
+
I 209 16 x + E1 y
26 / x(+1 10,11-x+11++ x111 26 2/
From the two inequalities above, we have
D ele2+,112 S (1 7+11) P 2B1 + 2-/21 By.
+ 6(1 - 7++1 ) V y (2++1) - 1
+ 24(1 2
226 0. (El|x(+1- - xxl1² + 1
Since of = d. Vyg (x, yt). we have
02 + 24(1 - x+1) El - xtl1
Bl < (1 - 11-+++1 E 2
+ 6(1 7 )
Vygt+1 (z++1) 1
48 - 1111--++1))) 29 E
cf 1| 48(1 m+1) 222 1 S V (xL.
$ (1- 1 )²
+ 2
8y
+ 24(1 - 22 1 E||x++1 - x
+ +6 7+11 )
Vygt+1
+ 48(1 - 76+1 02 (. V (x).
Lemma C.3. Suppose Assumptions 2.2, and B3, hold. Then, for the sequence {())
generated by Algorithm 1, we have
Pokg.1
E [llx++] (xx))1 S (1 a1
1 1-28. 23,
E B[llx- (xxx)11
1gg &g.11
28,
+ ((1+
$3
IE (x) y111
Mgg + lg.1
+ +1++ [1I=?19]]
where el defined in (45), yi (x:) is defined in (1) and is a constant.
Proof. From Lemma B.4, we have
E [[lx24 yf 11 = E [[ly: - B.d. - (x:))]
$ (1 + a)L [|ly, B V yr) (x))
+ (1+ 1 1 [bad] Vy
(47)
22

---

Next, we will bound the first term on the RHS of (47). We have
E lly: - Be V.VyyexXx,. yx xxxx = =E Ily: - (xx))l + B/ yy y.ll
23, (V ye Vr). yi (x+))]
p
25, Mg + gg1
E [Ilv (x,)1
2,3
$3
E. [ (x. y11
(48)
My + fg.1
where the inequality results from the strong convexity of gr by Assumption 2.2, which implies
(xx, - vZ 2 MgLa.1 lIy, xi(x)1
Mg + f. (xe,
Mg + fg
Substituting (48) into (47), gives the desired result.
To simplify the notation in the analysis, we introduce the definitions
0f = Ily. (x.)), and of = |v: v.
(49)
The following lemma, inspired by the offline bilevel optimization framework in [69], characterizes the descent behavior of the iterates in the inner problem.
Lemma C.4. Suppose Assumptions 2.2, and B3. hold. Let 0g be defined as in (49). Then, for the sequence V:) generated by Algorithm I, the following bound is guaranteed:
(E(O
E
(50)
Lus
T
T
41 T
1 E||x x2+1ll
3 + Lpp 1=1
B.
[1] +
Lug 1=1
3r
4
2,3
+
sup E xx(
+
+
8
E
(xx,
Tup 2
Be
XEX
1bg + fg.1
t=1
where Lug defined in (45).
Malei Ly matlost
fal is defined as in (44); H2 is defined in (11). Moreover, of is
Po
Proof. From Lemma B.4, we have for any é >>0 0
E [ll++1 8441 (x++1))1 EE [lly+1 - (x,) + yx,())) - (x+2(()))11
(1 6) [ll - y7 (xx))11
+ + 1
E (x44)) - (x;))
(51)
From Lemma C.3, we have for any a 0
s a1+ (1
1 --, 1gbg.11
E ||ye41 (xx)))1
E [llxx - (x
Mg + lg.11
23,
+
- (1 + a)
E
My + l
1
+
1
8 [|cg9113]
(52)
23

---

Substituting (52) into (51), we get
E [ly++1 - -r++1 (x(+(1111111
(1 (122. Mg Pgf
( + (1+ + +a)
E [[lxe - yē (xx))11
Mg + 9
+(((1+ (1+++)(+a)))
23r
8p ) E8 (x.,
Mgg + fg.1
+1++0)11+ 218SFE [1|e911]]
1 + 8
|lly++ (x(+1) yi (xx))11)
(53)
8 /2 /2 and
Let Lip = Agf0l Behng 1 1-2
Choose é
Then, the following equations and
1-8,1ng inequalities are satisfied.
Me th.1"
3eLra
(1 (1+ a)) (1- (1)
2
(1+aa) (1)
BeI-peg
=1 BeLua
(54)
(1+ 6) (1 - (B,b
1 < +
1 1 2
1 6 3
BeLep
Based (53) and (54), get
E [[ly++1 viti (X++ 1x++1)11 - EE [[ly= - (xx)
3,Lpg p E [lly (x(x)]1 + (-
M4g Eg11 -88 )8:) E
25
[1[V y.
2
+ BeLng
8E [|
BeLn, (x++1) - (3:)
(55)
Next, we upper-bound the last term of the above inequality.
E
(x,)
< (E []lx (xx+1) y (x, )[ + E (x))))()))))))))))))))))))))))) - yz (xx)
2 2 (L ||x, x + ( - (x,))
(56)
where the second inequality is by Eq. (39d) Lemma C.I. Substituting (56) into (55) and summing over t E [T], give the desired result.
C.3 Bounds the Linear System Solution
Lemma C.5. Suppose Assumptions 2.2 and B3. hold. Then, for the sequence ((x,, vt)
generated by Algorithm I, we have
E| Ve+1 (2.) (1+ 1 1-26 28, (6g,1 +
fg21)1g + + 6762 9.1
El
1g + Eg.1
1 + (1 + 1 c|13
for any 6> 0, where vī (xx) is the solution of the system in Eq. (4), and ey is defined in (60).
24

---

Proof. From the update rules in Algorithm 1, we have the following:
Bl[v++1 vx = T [ve
- j.d'4 - ZT [v] (xx)]11
- E - o,dg - vxx))ll
- (1 + o) (x..((X. vo) vi
(x:))
+ (1 + { )o%Elldy (x),
(57)
where (x (x)), vo) == Vz (x
v7 (xx)) + V((x)x)
For the first term of Eq. (57) above, we have
E Vt ( (xx), vo) vx(x)11
E Vi vi (xx))11 26, E(v, - vx(x),, (xt Vi (xx), v.)) ( vo))l
1 28, 1
E Eliv, vx(xx)1 (26. Mg 9,2 _ -, (x)))
My fg
Ug + fg.
(lg + 1g 1.1144g
<
1 28,
+ 626g.11 Bllv, - (xx))1?
(58)
"9 + fg.1
where the first inequality follows from the strong convexity of the function P.. which is the gradient of the strongly convex quadratic program 3v T V399 (x, y7 (x)) v + v (y Then, we have
1glg.1
Biv; - vz V., VP.(
B1[ vi (x:))1
Pg + fg.11
E EXV
Mg + fg.1
The second inequality is derived from the following incquality.
B (xx. ve)l
E|| V 39 (xe, yi (xx)) ve + (x)))
|B| V y (ve 2x
e Bl (x;)
(59)
where the second equality follows from (4). Combining (57) and (58), we get the desired result.
Lemma C.6. Suppose Assumptions B2., B3., B4., C2. and C4. hold. Let ((x,, ye, ve) be generated according to Algorithm 1. For c defined as
ex = d.- - Vel( V.,, Yr, vt) Vzga (x), Ve + yx),
where
(60a)
(60b)
we have:
11 < (1 - Aet11 1e+1) )211 726 22 6,) 4x
Mry
iz
b
12 \4+1 2 9t (x1+1,8141) V2 (x+11, 1|2
+ 12(1 \++1) 2 V f( - 1 (x++) 1)12
+ 72(1 (eg 222 + (EE|xx+11 2 + 23 2
144(11 )2 9.1 ( 288 (p'
1 2 + e, 100
(61)
for all t E [T' and (0Y,0) 0%) and eî are defined in (49) and (45), respectively.
Proof. Note that
c == dy. -
Ve+1),
25

---

where
(X V++1) = ggt+1 (x Vi41 + VyftH(((41.
From Algorithm have
d d (xe4 -e+1) (x. BB
Let u = x y: v]. Then, we have
Bl = E + - (P++1(
= E P7++1uuu41 B(+1) + (1 A+)) - Vee+ - VP
E [1 A1-1)e + (Prr)(u VPrei
(1 (1- 1+11
which implies that
B1
= (1 Aet1) El (VP:41(M44:: 1441) V P
(1 ) (V
(u:;
B
( B.41) (
Pi++ (u (P:(
$ (1 X++1 2
2(1 "
VP+++ Vi++ B441) (P.(u.))
where the inequality follows from For the first term, from Assumptions C2. and C4., we have
inequality.
V (141 Bu+1) (P(+2(u++1))
B|| (V39+1 (x++1, Y B.+1) Vyth+ (144), Ve-1
+ Vy (x41 ::41: - 1
< 2
(V (x+11, B.+1) Vygt+1 (xet1, Vetall?
+ 11 B.+1) (x41+
o2
< 2( 9vy
h
where the last inequality follows from (8).
Then, from the above inequality and ||a + 6 clI - 3[]a|]2 + ||6]| 8 + ||c|]2), we have
02 &yy p² + o7
E| Bl 21 & (1 - (1-AA41) 4
+ 6(1 ( - (P (u+++ 1|2
+ 6(1 V VP 1 (11+1)]22
+ 6(1 \+4) (1
(u, But
(62)
Moreover, from b++ < 3([|a|22+ |b6b [|]]))) we have
E| V -VP(u)
< 3E| V P, +1 V1
+ 3E V Pa V141, V(+1) - (x
+ 3 V P. (x Vts V++1) - Px,, Yr. vz
< 3E][(V) (X++1. ((+1) - V'g Y141))) Vy1((x+1, (x)x))
+ ( V141) V3.9 (Xe.
Vyf((xx,
+ 3E P. Nt, V2+1) - VP: Ne, v2
< 66,2,2111 Vc+ G22) [EE x + y.ll + +32))3222220 33,, - (63)
26

---

where the last inequality follows from Assumptions B2., B3, and B4.; From Eq. (63) and the inequality ||a + b1|² 2[||a||2 + [[b]2),
obtain
(u - (P(():)]
I (666, 9,20 (1,1)
- xz - "f
6(6y,20 - (f,,) -
+ 17 + EIV
s <6(6,,2 - 10
+ 666 (B + 2E| - V vz)l
I
x - v1)13
+ 68
9,1 80 (Bile/12 +
4(p (2, - (xx)))))
(64)
where the last inequality follows from (59). Similarly, we have
V + (u++1 B.+1) V ( 1112 - 6 + (721) [B1x*++
+ (xxx))1 + 66%,108 o8 (Ellex 1| + - + 1 -x((x)11 Substituting (65) and (64) into (62), we have
(65)
o
Blley+1 2 < (1 \ut1) )² (1 + 726 3. 83 E| 4x,
Syy
b
b
+ 6(1 - A
- VP:+ ( )|1
+ 72(1 - \et1) + e7 (Bl - x1| + 2 -ta_:-/0000011111111-1123/000030 v.))
+ 144(1 - \e+1) 1 1 (x))1 2888 1p g.2 2 -
From ||a + +12 < 2||a||2 + 2/ and (8), we have
B| VP++ = E|| V (Xe+1 V2+1 Vigen (141) Ve41
+ Ve - (y
S 2Tl (V3ge (X++1,8e+1) - ViS++ (x+1), ve+ill
+ / Vy - (y
$ 2 V.99 (84+1.8441) V3g++1 (x4+1, 1|'p
+ 2E / Vy.(( Vylez
This completes the proof.
As demonstrated in Lemma C.6, the gradient estimation error e\+1 for the linear system consists of 53 Elle 1|- which
four key components: (1) an iteratively refined error term (1- (2 depends on the stepsize dy; (2) the error arising from the variation in the Hessian of the lower-level objectiv; (3) the error resulting from the variation in the gradient of the upper-level objective, and (4) approximation error terms of order O (6 and ( associated with solving the linear system and the iterates in the inner problem, respectively.
+ (17726+
Lemma C.7. Suppose Assumptions 2.2, B1. B2 and B4. hold. Let vx) is a solution of Subproblem (4). Then, we have
22 [v](x.) - viHr(xe+1) 12 <=< (11r+1(xe41)) - yi (xx))1 + ||xe+1 - xel?²)
u2
where v :== = + fo.2fr.
27

---

Proof. Based on (4), we have that
[v((x)) (x
[V (x,((xx,
(V)
( ( (x++1))1
s (V ( V x(x,(
(66a)
+ (1
(66b)
In the following steps, we bound the terms (66a) and (66b), respectively.
For (66a), we have:
(xxx(x,))(xxx)) (
(i 11
(V (x)) (12
( 1|?
(x (xi) - V 1 (x
m
fg. (x,,) (44
14
922 (117(())) ye. (x442)1 +|xx xx+11())
(67)
where the equality holds since for any invertible matrix A and B we have ||| ||A (B A) |]. and inequalities are obtained from Assumptions 2.2 and B4..
B-
Thus, from (67) and Assumption B1., get
f1,6922 (1x)((x)) - vi+1(x++1)) + +|xx - xx+1ll?). mn
(66a)= <
(68)
For (66b), we have
1
(66b) S
V (x (tw.://wxw)))/////////////a//o
Fg
41 (xx,, (x:)) (x441))44((x4+1)) 1|)
Mg
lya (1xi+11 v7(x)11 +|xx4]++11xx11110 - -x,1??)
<
(69)
Fg
Combining (68) and (69), we have
1
(2rolo2 + t (11x2t) - -xx(x)) ||x++1 -xe(()
[x,) ( fgg
Mg
By raising both sides of the above inequality to the power and using (a + 6)2 < 2a + 262, complete the proof.
The following lemma characterizes the decrease in @y defined in (49) and can be viewed as an extension of the offline BO result in [69] to the OBO setting.
Lemma C.8. Suppose Assumptions 2.2 and 2.3 hold. Let 07 be defined in (49). Then, for any positive choice of step size de as
Lyz
(cg.1 + 23,1)M
8, <
where Lng
p2
(Mg + Eg.1
9.1
28

---

for all t E (T), the sequence F1,,, volle= generated by Algorithm satisfy
5, Lu
4
Σ (B(0 B(O0))
Bl0
8,
Blle
16r²
T
E Ily (xx) - -i((x))''
1 11 dt
[=1
8D2
T ||x++11 - xel1?
(1 + 21
(70)
where ey is defined in (60), v and Try, are defined in Lemmas C.7 and C.4, respectively.
Proof. By Lemma B.4, for any > 0, have
E Vi+1 V (x++1)|l = E V1+1 - (x() + vi(xx) viti (x
(1 + - (xx)11
+ +
13 v (x(+1)) - (xx)).
(71)
From Lemma C.5, we have for any 6>0 0:
(fg11 + 42,14a + 6,66,
E| Vo+1 vx(x))) 1| s (1 -6)
1 - 28,
Bllv, vxx;)l
vx,))1
Ug + lg.1
1
+ (1 + 8 6 EX113.
(72)
Substituting (72) into (71), we get
E [||ve - (x(+1))))) s (1 + a) (1+ +c) 1 (6 + 1g,114
+ 82 9.1
El
vx,))l?
Mg + f,1
+ +1+ a) (1 + 1
+ (1+ E Vi (x++1) vi (xx))]
(73)
In the following, we provide bound for the third term on the right-hand side of (73). To this end, have from Lemma C.7:
2²
E [i4 v2 (xx))(
E
(x(+1) (xx))1 Bl|x++1 - xx 111))
m
s 2 22
2E (x(+1) - xx+1(x))11
1
+2E || (xx) y7 (xx))l + E [|xe=1 1B||++++
xill²)
v2
< (1+21)) [ x111 + 2E ||yr+ (xx) y2 (x)))))
4g
where the last inequality follows from Lemma C.I. Combining this result with (73) gives
E. El|/e41 - (x++())))) " < (1 + (1 1-28, (Cn + 1
+ 8262
El[ - (xx))1
1gg + tz.1
1 o 12 + 4 1 a)
22 E xxx)))
+(1+a) (1
mg
1 v2
+2 1
(1
+
21
E |x4+ xel1²
(74)
a
29

---

Let [pp, = (oattggn Me al
then we have
(fg11 + E 1g,10
- 20,
+ +8.69 9.1 = 1 - -20eLin, + 63262
1g + fg
S 1 5z 8et1p
(75)
Lpg Eg
where the last inequality follows from 8, 5
Choose 8cbpp/1 and /. Then, from (75), we have 1-bckpa
1- 4.4
(I+0) (1 (1-26,
25, (fa.1 + eg, 1g,1)4
+ 82 n.1
Mg + Eg
$1+ (1 + +6) (1- (1-5,Lmg)) = dgLyn
(76)
1
4
(1+a) a)
1+
2
dct
2
1 + 6 8ehmp
1 +
S
8ehpo
Thus, from (74) and (76) we have
8,Lnn
E Vi41 (x
1
E vxx)11
4
4
16v2
5,
+
E Bllxiti xxx)]
8u²
(1 + 2T B 1 x11
Rearranging the terms and summing from to T, gives the desired result.
C.4 Bounds on the Gradient Estimation Error of Outer Objective
The following lemma, inspired by [69], provides a characterization of the descent of the gradient estimation eтror for the outer-level function.
Lemma C.9. Suppose Assumptions B2., B3., B4., C3. and C5. hold. Let ((xi, Yt, ve)) be generated according to Algorithm 1. For ef defined as
(Z of = d. -de vt), where dz(z,, Vxfe(z)) + V2ygi (zi) Vt.
(77)
we have:
0² gxy p²
Elle/411 2 < (1 N6+1 2 Bleef11 112
4m
+ 12p - M 3 V2 (1-1,1411
2 xy 9++1 91+1 (Xe+1,
+ 12(1 1 V
72(1 (
- -x +
+ +7262 g.1 (1 - 7/+++ )a 5 El
72(1 - oM
(78)
for all E [T], 8Y, ex and et are defined in (49), (60) and (45), respectively.
Proof. Note that
</11 = -, deti (X1+1, Vi-1),
30

---

where
det (x41,, Vet1) = (xStt1((:H1 + &yyltt1 (x441, Ve41-
(79)
From Algorithm 1, have
t d (x4+lsYe+1; Be+1) + 1c+1)(d[+1 d (x41i
where d (X441,y+11 B++1) Let = v. Then, we have
+ V xt (X++1. Yt-1; B(+1) Vi+1-
E Bl = BB|d d (u++1) 1|
=Eldd44 ( B1+1) + (1 (d, deti B(+1) (
E mttle + (ez1
B(+1) d(41(
(1 7ル (de+ (u,; - (u.)))??
which implies that
El 1 I1
= (1 m1+1) Bllee (1 B.+1) - (u+ti))))))
(1 Tt+1) ( (ur; B.+1) (4.1 B:11) (e+1((u44)) du:))))
< (1 Me+ 1 [ ||2 2n
(.+ - d
+ 2(1 M|{1 (
B(+1) d (4(+1) det1 Be+1) (u.)),
(80)
where the inequality follows from ||a + 6112 < 2||a||2 2 2/16
Let us bound the second term in the right-hand side of (80). Based on (79), we have
B - d
Ell (V Sy 0++ Y441; B.+1) V2 xy (Xe1), Ve+1
Vx (x11) B.41) (x
< | (V2 (2 (x:1) xy (x441, veril
2B| Vxft+ (x++1. B.+1) Vxfet
2
Rxy p² b
where the first inequality is by and ||a b|2 < 2||a||| + 2||b| Assumptions C3., C5. and (8). Substituting the above inequality into (80) and using ||a + + cll < 3(1aa|2 ||B||2 obtain
the second inequality follows from
[|c]2))
o²
E 211e/-111 2 < - - 212
4x
Bay b
p2
b
6(1 7/ 2 C (u,) d
+ 6(1 - 7 2 2
d (04+2(4433) (14+1))²
+ 6(1 M 3 d (u B.+1) d (u: By
(81)
31

---

Moreover, from ||a +a++b b + clf I 3(1||]2 + ||6]] + [|c]]2), we have
()(d)( (u)))
(x++1, v++1) d. Ye+1, V++1]]
+ 3E (x.x.. v dx Yr. ve-1l
Yc,
+ 3T ]. Yr, Vot1) - yx, Yr, ve)l
(9)
< 3EI (141,)++1) V (xt) Vx/((x+11, (xx
+ 3EI(( &y (x41)
+ 31E (x Yr, Vo+1) dx(xe,, Nr. vi)l
(9)
Σ B/ + 1) (El|x1+1 x, 1|
yrll?) + 3e 1llve4 vell
I 6(G,2p2 + (,1)) ( x1+1 - x 3
+ + o
(10)
S 6( + +G,1) [E| X1+1 x +
2
+ (B)
V v)))
6(l2 22 +
1 X
1 2, V
+ 6 03 ( vi
(82)
where the (i) follows from (79); (ii) follows from Assumptions B2., B3. and B4.; (iii) follows from (8); (iv) follows from (45) and (60): (vi) follows from (59).
Similarly, we have
(id++1(ue+1) B(+1) d++1 (u;; (u;; 11+1)11
S 6(02, + f.1) [E||x++1 x1l12 2 / (x),
+ 66 of (El e2 BlIv - (x; Substituting (83) and (82) into (81), we have
(83)
Byy p² oi,
Elle 2 < (1 M ) E e 2| + 4n
b
b
+ 6(1 7/+ (l - ( 11(+1)112
(u++1)
+ 72 - 7)+1) g2 20 + (..1) (E) X1+1 - xel12 28 c211 Vy (xx,
+ 726 (1 - 7/-1 -) )3 + 72(1 - -1(+1 1 E - vx1
From ||a + 6112 < 2||a||² + 2| and (8), we have
El(d,(u,+1) - d. (u.4
V 1141) V It (X.41,
Vayle+11 (x++1 (++1)) Ve+i
V (x (x yr-))]|
< | (V2 (X411,1141) V2yg(+1 (X441, V
+ 2 V Vx.f((X+1
Vx/++1 (x/h/
< 2E
V2 V2y (X4+1) - V2y (x441 11'p
2E (x11X Vxfe+1
(
This completes the proof.
As demonstrated Lemma C.9, the hypergradient estimator error e/41 comprises five key compo- nents: (1) the term (1 -1-77-- EE 1|
representing the per-iteration improvement achieved by the momentum-based update; (2) the error arising from the variation the Jacobian of the lower-level objectiv; (3) the error caused by the variation in the gradient of the leper-level objective (4) the error term ( + 2 (x y))ll?. which is due to solving the lower-level problem; and (5) the error term O O6 1|2 + 72(1 - M ) 9.1 57 R[OY]), which introduced by the one-step momentum update in solving the linear system problem.
32

---

C.5 Bounds on the Outer Objective and its Projected Gradient
Lemma C.10. Let Assumption 2.4 holds. Then, for the sequence of functions {fi] we have
- -
2M VT,
where M defined Assumption 2.4; Vi is defined (11).
Proof. Note that, we have
Σ (x(x V7
(ixx, fr (N -
Σ
- f -
2M + Vr:
where the inequality follows from Assumption 2.4.
Lemma C.11. Let {fe]T= denote the sequence of functions presented to Algorithm 1, satisfying Assumptions 2.2, 2.3 and 2.4. Let Px.a, be defined in Definition B.1. For any positive step size on such that a; I 1/4L, for all t E [T], Algorithm I ensures the following bound:
Σ (ar Tsaz) E Pxx,, (x, Ve yx
S 8M + 4V + +2M² Σ
(20r - Lya (B[0) + B(O)))
T
(20 - L5a E |ef
+
(84)
t=1
Here, of and 04 are defined in (49); VT, M, My and ef are defined in (11), Assumption 2.4, Eq. (42), and (77).
Proof. It follows from Lemma C.I that
yY - y((
L1
s (V y? (xx)), xx+1 xx)
||x+11 xi11
2
= -a (Vf((x,, yJ (x:)), Px, (xi; dx') + ||px (x::
(85)
2
For the first term on the right hand side of (85), we have that
xV Px,a, (xx:d))
=- (d), Px.m (x:; (z)) (VS((x,, (x:)) -d,, Px,, (xe: d)))
< Iixa, (x: x/) + 2 | - Vf((xx.
33

---

where the inequality follows from Lemma B.7. Let de (21, vz) = Vxfe(z)) + V xy (z:) Ve. Then, from Lemma C.I, we have
d (xx)x) = d de (Zc, vz) + de (ze, vo) x
2 dp - d, (ze: ve) || + |ā (2t, vo) - VXx(x)
2
of + 2 d. (21, v.) vo)- - V(((x).
MM (0% 0 where of = d. -d (z4. ve). This implies that
s |f
(86)
fe y: (xx)), Px (xx: d)))
Px ar (x d + + eel M13 (0 + 0,))
(87)
Plugging the bound (87) into (85), have that
(((x+1..((xx42)) x(x,)
< { az)
|et 1 + M7 10) + +70)aa
|x (xe; (x): 20r
2
which can be rearranged into
(a+ Lyaz) Px (xx; 1l
< 22f (x:)) - ft NI + 40s |ef
+ +21 (0% + +00)a ac.
(88)
In addition, we have
PXx (xi: V
< 2 1P (x;;d)) - Px (x Ve + 2| (x,;
$ ||dl xx + P (xx: 1
<
[d]]
+ +4M (0% 0 + 4 Px (x:; dx,:d)))²? )
(89)
where the second inequaliy follows from non-expansivennsss of the projection operator and the last inequality follows from (86).
Combining (88) and (89), we have
T
(ar L5az) ([ (x:; (xx)
<
(f((x.) -x(x))
2M
Σ
(2ar L5a?) (0 +00 + Σ (2ar Lya?) |lef|²
< 8M + 4VT
T
+2M
Σ
-an--Laa7 (0) + +X) +
> (2ar L,a7) ||o1
where the second inequality is due to Lemma C.10.
Lemma C.12. Let Assumptions 2.2, and 2.3 hold. Let {x, {x be generated according to Algorithm
1. Then, we have
I[x - 22 < 20 (IPxx, (xi; Vilxxx + M3 (0) + 08))
where 0% and 0% are defined in (49), My is defined in (42).
34

---

Proof. From the update rule of Algorithm 1, we have
|[x: - x++1 = at Prx,a (xri d/)l
$ 2a (IPx, (xri V (x (x:)))I
+ Pxxx (x:: Px.a, (x4; V
2 2a (IPx (xii
yi MI
+ + - VX
s 20 [Pxx, (xe; V yx + Mf (0% + 07))
(90)
where the first inequality is by (a + b) < 2a + 26 the second inequality follows from non- expansiveness of the projection operator; and the last inequality follows from Eq. (39a) in Lemma C.I.
C.6 Proof of Theorem 2.6
Proof. Bounding Elle/11 in (78). From (78), we have
Elle/+111
Elle/1 12
(1-741)) 1
m+112
Bllef11
4ri+1
Sxy
2 p
+
lx
at
a-11
a₁
ar
at
12p²
(1 m1411
E Ky (x411.
V V (x141,
12
(1 M111)
E Vxfi
Vxf(41(x41.
a1
72 211 m111) ) ((6,20 + f72)) [E|xx-11 -
01
72
-
72
at 9.1 (1
M 18 ||?
n141
91))
With respect to the coefficient of the first term on the right-hand side of Eq. (91), it is important to note that we have:
(1
1)(+1)
1
11++1
1
(92)
Qt
at-1
O2
0r11
Using the definition of ag in (16), have
1 (c + 1/ - (c - 1)1/3 (4)
(8)
3 + 1- 1)2/3
3 + 1)2/3
0t-1
22/3
(ai)
22/3
(iv) 22/3
(ui)
Oi
3 0
(93)
3(c + 2/)2/3
3(c + 1)2/3
6L,
where the (i) follows from (a + 6) a 1/3 < 2/a2)/3); (ii) follows from 2 (107); (ii) follows from (16); (iv) follows from < 1/4L, in (107).
Substituting (93) into (92) and using 8, = Cj and 1/+11 = G we have
1/
1
11+1
Grac S -50an
(94)
Qt
0t-11
6L,
Oe
6Lg
where the inequalities follow from Cy
1.
+ 5Ω in (106).
eL,
35

---

Then, substituting (94) into (91) yields
1
||e/11
4n yon p² +
of
S Bleff
Da, (gv
Q
at
a9-1
b
12p²
(1 7/- ( xy (Xc+1, V2 (Xc+1, (x 1|?
Qat
12
+ aox
(1 11t11 2 V Vxf( (XxII(XX
72 (1
(( "2,200 + 1,,1) [ Xt+1 - x,
V
72 22 (1 1/++1 1
72 (1 n (,,
(95)
Dot
Bounding E E in (46).
From (46), we have
E
- (1 (1 + 48 18.
Qt-1
0/--
+
141
2 02
24
(1 --((())
2
9.1 Bl|x4++1111 x111
04
b
01
6
+ (1 - 11-++1))0 2 V - (x91:
o
+ 48 - 7+11 )
E (x y.)l
(96)
9.1
at
Let us examine the coefficient of the first term on the right-hand side of Eq. (96). Specifically, for T++1 c, and 3, = C3ar, we have:
1
(1-7+1)28 21 4862 188)
(1
7--1)
4862
1,1
06-1
04
0x
1
1
7-11
48 9.1 1 M+1
at
a1-1
an
1
1
1
4,0
+
+(- -
at
a11
at
< 48
c20s c,at:
(97)
6Lg
where the last inequality follows from (93). From the selected ey in (107) and the definition of t in (106), we have
M?
48 13 he, where 25
4 6T.
T
14g
Combined this with Eq. (97) yields
(1 7+ )2 + 4862 187)
<
-hpa
(98)
a
04-1
Substituting Eq. (98) into Eq. (96) yields
1
[0
2
2
El
<
El
a--1
2 02
24
T++1
7-- 22 12,,11001i [e]|xx++111 xx
P0, b
Po..
6
+ P..
(1 - 7t+1) ) V
B E
+ 48(1 7 ) Ton
E (
(99)
36

---

Bounding E 1| 2 in (61).
From (61), we get
Bllee+1l1
11
1 (1 X++1) (1
B||e,11
a2
a-11
at
ac-1
o
12p²
4
1+1
Jyy pe +
(1
Ae+1 \+11 33
(x(+1,
Vee++ (x(+1. l|
at
at
12 (1 \141) / V f((x++1. V441)
(x
0r
2211 - \141) )2 (( + (711) (E] x x111
2,
V (xx:
01
144 (1 - - ) 9. 1 288
( 9.2 4,,10
(100)
Oz
Let us examine the coefficient of the first term on the right-hand side of equation (100). Specifically, for A241 22a² and 6, = CzOt,, we have:
1
- - (1-A 21 7 0p-1
S
-
(1 -
(++1) -222 720,,107)
ar
0t
0r-1
1
de11
Act 72 19
at
a1-1
at
at
1
+ +1 1
-caa,
g, cz00
cxa+
at
at-1
as
< + 726
a1
2
1aa cxac.
(101)
g.1
where the last inequality follows from (93). From the selected by in (107) and the definition of V in (106), we have
1 + 72 12
M²
o3 + JVV where = 90
Cx 69,
L2
Combined this with Eq. (101) yields
1
g. 87) (1 \e+1) (1+ (267
S -JDac.
(102)
ag
ac-1
Substituting Eq. (102) into Eq. (100) yields
1 Elley+1 112
JEley
1
< - Jo,
T
04
2 1+1
02
12p²
p-
+
(1 A )++1) (x:+1.
Vzg++1 (Xe+1, 1|?
Van.
Vaa
12
+ Vau
(1 ) V (x - (yf4
72
(1 - 2e01))(22 ++++0 G. (El|x++1 +
Vai
72
288
(1 (1- 22,
1 E Vo, e (p262
22 + 6,
(103)
Vai
Combining the outcomes. We recall from Lemma C.12 that we have
||x- x2 < 20 ||Px.0. (xii Ve((xxx + My (0% + 07)
(104)
Let
T
T
T
EE Ellee 11
Elle 12
A
(E
1+1 E(OOT) + r
Σ
[E -E
+
Cr-1
1=1
1=1
1
BlleYtall 1|
11
T
1Elle/11 1|2
LE
+
+
Σ
(105)
V
at
a411
?2
04
a41
t=1
37

---

Here
r 11M
22M2
(Mg + (g,1) -
T
① 2 max
48062 9,1,
1926 9.1
co)
Lpg CB
Ly,cs
r
1 c/
2886 M %
V max
144 9.20²
-771)
10+
9.1 2
M2
576(lg ST6 + (7.1)
(1/g + +6.,1)
576
9. (p g.2 + Endo88.
r
Cg.
M2
Ω max [111(2200 +7,1)
(10+
12 c3
Mg
288
9. M2
M2
c3
576(C 276(C22002 +l7.1) (1gg + 1,)2)
72
5.1 Ho
1
r
Cg.
M2
CB
(106)
where Li, = =Mgl9.1 (Ng + p22) and Eyp = (f9,1 + fy (51l)//((u + C2,2).
Here, we have
c 2 max (4L,g, Callig + 2g.1),23
My
C9 v 880
Lpd
VM5 Eeu,1/""
where v == == + 20,20,00
Ly = Eg.1
68 3520(1 +2L2))
Mg
M2
(107)
C 67,
+ 486 8.1 + -10
where h:= 25
T,2
Cn
+50,
f
M7
cx ,
+ 72
9.1 03 + nV
where J = 90
L
Using (103), (99), (95), (84), (70), and (50), along with (104) and the fact that a decreases with respect to 1, we obtain:
T
A(or, 32, 5.)E
VX + A
T
< 8M + AV + Σ
Bla Br, 8:) E(0)] + Σ Br,
(108a)
Dlar) 1 Σ F(a 3.) + Σ
(108b)
L(an 3:) V
(x,, 22)
Σ
N 5.) xEX
sup Ilyī-1(x) - (x)112
(108c)
t=2
22
gy
2
T
12
+
4
/
o
Syy
p²
+
o
T
1
+
Sxy
2
+
ofx
T
m
(108d)
b
Φ
T
b
b
Ω
b
b
02
1=1
t=1
[=1
12p²
12p
12F2
12B2 f.1
Gy.r
+
Gxy.7
Gyy.T
f.1
Dy.1
D
(108e)
Day
VOT
Ver
38

---

Here, M is defined in Assumption 2.4, VT and H2,r are defined in (11). Moreover, Gy.r, Gxy.T. and G Gyr.T are defined in (13). Let
4Ly
802
E(a,, 61) ==
T++
(1 (1+213) + 72(1 - (L, + P Plar
3r
L 1gg
+ +24(1- - -7(+1 P2,. 9.1 da
+ 72221 - ----1 (C + f7,1) yai
1
A(ai, == a1 (L, + 2E 61)) ag
B(a Be, 56) == {, r
5z + 4Mfor 2M E
Be, d
4
1 + 72(1 -
+ +72(1 - \1+1) 2 86
g.10f Vac
m 22, 9, At.
C(at, 66) = L r
31 + +4M3at 2I, M302 + +2 f(a,, (t,
(109)
2
288
by
(p- 9.2 + 10,100
Va
D(as) = 2 (2a,- L a
2) 50
Bi) == 2r
Br ha, + 144(1 - ) ((g2222 + +,,11)
Lpp
ya,
37
+ 144(1 - 11+1) (C, + f7,1)
Qoxs
4T 8c Ja, + 7202 (1 m )²
87
[(ar, 66) =
9,1
Daxt
Moreover, we have
2r
3
M(a,, =
B: + r + 48(1 - -3441)322
Ny + fg
To:
82
+ +14((1 71+1) + tl,,) 33
+ 144(1 \1t1)
(110)
Var
Nan
4 r +
16v² T.
(3) =
Lig Bt L 125
Note that, we have
8y2
M(a,,30,0)) = I,ng8 3r L1n,1250
y
r +
(1 + 1 - 72(1 - 11+1) 22222 + tG, Stor
1 + 72 \141 (C, + f7.)) Vai"
+ +14(1- - 7/11) 226 9.1 vai
which together with 8, = C304 and 8, cgai in Eq. (16), we have
Eat, 31) = 112
r at
+
8u2
(1 (1+213)
at 6,
+ 24(1 - )241) ai g.1 xb
LHd 3e
Ln
+ 72 - nh+ (2
+
12 at
f11
+ 72(1
de+ )e+1) (2 C222202 + (4,1)
at
Ω
T
4442
176
M²
(1+ 21 (1+21 M o/
L22
cg
+ 24
g.1 +
at
+
(2
9.
2220" + G.,
02
1 + 전 )a
1
ai
(111)
4
39

---

11M]
22M Fing.s cs
where the first inequality follows from r
Cp and =
in (106); the last inequality
-1 880
13M2 |3520
follows from cg
2,g
CB
V
m3
(1+ + 2Iz), in (107) and 2 4804
9.1 and
Q, A 2 (440 22.
472 in (106).
Moreover, have
Mar,,, 56) = =0 - L,
2F( de)a
at
2 04 - Lya
2
0h
(112)
4
where the last inequality follows from 0, S 11/4g in (107) since o, - 1/(c+ in (16). Bounding (108a). From (109), we have
Lip T d1 + 111fa-22000 -f 223 + 3e, 60)
B(a 5,)
+ 72(1 \et1) 2 9. Va
1
7271 - 7 )2 2² 9.2 Nei
02
1
Ly r 5e + 4Mfa, 2M T., +
M²
o7
04 + 72
+
9.1
az
9 Lye + 2 M3 + 726
(
1
+
1
)
S
2 Mfan.
(113)
where the first inequality follows from B. cgan, d, cga, in (16), and Eq. (111); the second inequality is by Y 22M3
and V s2 288r
og (106); the last inequality follows from (106).
Tspes"
Mr
Moreover, using Eq. (109) together with Br cza and 6, = cza, in Eq. (16), we have
Clar, B2,
H. B +M4MMor 2L, M30 + E(a, &r)
288
Vo,, 9.1
(126
6,2
+ (7,10
9 < Type Tezar + *rM3ar
288
2
+
v
12 1p
9.1
9.2
+ G22caaa
M2
Ott:
(114)
11M
where the first inequality follows from (111); the last inequality follows from r
and
Luyes
V Z 576 @
M7 9.1 (p2rg, + 2c3 in (106).
Thus, from (113) and (1 (1),, we get
(108a) S O (VT).
(115)
Bounding (108b). From (109), we also have
D(a,) = 4a, - 2L - 50, S 0.
40

---

11Mj
From Eq. (109), 8t = Cg04, and r
Ta we obtain
21'
3r
F(at, 3t) - 1.p0
Br - -har + 144(1 - >e+11 "0.2)) + +.,1)
Voc
+ 144(1 - 1/+11) ) 2
+ +1,,2) Par
2 at
hag + 141(1g 22222 + +1,1a1
1
1
Pg
M Olt haxe
24
M?
L
22,00
where the second inequality follows from Ω, 4 2 144(6 + (721)= 25 Mr2
in (106); and the last
M;
cquality is by L. From 6, cja, in (16), we obtain
48
87 Qlx
I(a), 5,) =
8. jot + +
9. (1 - -71+1)
Lyo
4Y
cBat - -oat + 72 c2a0
T.p
9.1 Ω
89M?
Pa
Mf
Okts
Pv
where the second inequality follows from Y
22M2
and f 2
12 Mj
cg. the last equality follows
T,
from J 90 M² L3
Thus, we get
(108b) S O.
(116)
Bounding (108c).
From 3g = ccga in (16) and Eq. (110), we have
2
83.
L(an Bb)=
rB + 48(1 22+1)
H4 + l
8.1 Dat
87
33
+ 144(1 - -e+1) (cg,20² 2
+ 2,,1) Va
144(1 TT++1 (6,202 + +7,2)
2Tegat
2 0t + +Tega? + 4822 g.
+ 144(6 + +e,,)) 1 +
s 1630s
1
c3 +
Mg + lg.1
1
21 egcae
3
< Mg + lg.1
Tezaf + 4(11g + 1g
Tezar
4(1gg + lg.1)
> 19263 (My (Mot(g.1) cg. and Ω v > 576(2 2222
where the second inequality is by + (g,1) (e)
g.1
co in (106); the last inequality follows from a₁ S 1/c0(H, + (g,1 in (107).
41

---

From Bt cga,, 6, = cg00 in (16) and Eq. (110), we obtain
16r²
16v2 Y.
(3),, = Lug Bt r+ +
r
+ E 12ggan
pe C30,
Thus, we get
T
(108c) = Σ 3,
Σ
(3,,, 8.) sup xeX
liyi- - (x)=-(()--xxx)) xx)]2
112,T
00
(117)
orr
Bounding (108d).
From M7+1
c,
7(1 =
c,ai. A4+1 = =caa in Eq. (16), we obtain
(108d)
02 2
T
1++1
2
4
2
Syy
p
x 2+
4
Swy
p
5
2
at
V
a4
52
b
t=1
1=1
2
0
0
0
99
+
9xy
+
0
(118)
b
Bounding (108e). We also have
Gy,r + 12p
12p²
1264
126
(108e) = Φar
Nor Gxy.I + Var Gyy,T +
Dy.r +
Dx,r
var
Dar
0 L (Gy, Gxy. + Gyy. Dy. Dx.T))
(119)
aT
From Eq. (16), we have b = b = 1. Moreover, by (10), 0² dg + Jon + to7, + to gxy (15), we also have
+ +07, From
Gr Gy,r + Gxy.T + Gyy.T, Dr = Dy,T + Dx.T.
Then, by inequalities (112), (115), (116), (117), (118), (119), we have
T
0t
E
Pxx
(xp:
+ A
2
H2.
0²
T
Gr
DT
<
0
Vr
+
+
3
(120)
orr
b
OT
orr
[=1
From the definition of A in (105), we have
T
T
T
Blee212
B 11?
E
-A
+ T
[E|01] - E
+
at-1
a1
1=1
B|
BlleX+111 112
Elle/ I|2
E| E 1|2
a1-1
a1
Ω
at-1
at
1=1
02
o2
+ t²
02
07
<TOY + ror
+
+
9yy
Suy
(121)
Van
Using (121), we get
Σ
a4
Px
(x1; Vxx
2
H²t
o²
T
GT +
DT A
0
Vi
+
0g
+
OT
b
ot
t=1
0² T
HaT
GT
Dr
d2
0
VT
+
80
+ 8Y
+
a
+
+
b
RT
QT
or
0g
t=l
42

---

Since a, = = we get
1 1+1
Σ
2 log(T' 1),
c+l
which, combined with the fact that a2 decreases with respect and by multiplying both sides by 2/0r, results in Thus, we have
BL-Regr
E 1xx,o (xi; Vx
0
1
(Vr +ly1 - -( - logg 0²
CT
1 QT
(H2, + Gr + Dr)).
+
This completes the proof.
D Proof of Regret Bounds for Zeroth Order SOGD (ZO-SOGD)
Proof Roadmap. We provide Lemma D.7, which quantifies the enror between the approximated direction of the momentum-basee gradient estimator, di and the true direction, (x.. at each iteration. Lemma D.9 assesses the convergence of the iterative solutions {y:) specifically the gap E 1 yr [x, while accounting for the error introduced Lemma D.7. To establish Lemma D.13, which quantifies the error between the approximated direction of the momentum-based gradient estimator, d', and the true direction, (x,,, yz) VýSt. (X,, Yt) V.. need present
Lemma D.11. This lemma quantifies the error between dý and V (x,,
2p. (
P.)2) V Yr Pv Vt)). Then, Lemma D.15 captures the error of the system solution of Problem (18), i.c., gap E [ v. (x,))]] based these errors. To establish Lemma D.19, which quantifies the eтror between the approximated direction of the momentum- based hypergradient estimator, dØ and the true direction, Vx (x,,,x y: + (xtyy,) Vt. is necessary to introduce
Lemma D.17. This lemma quantifies the error between dž and fxfr,, yr) + _ ( ve) p (X,, - v.).. Then, Lemma D.20 bounds the projection mapping based on these errors. By combining these lemmas and setting parameters, achieve the desired result.
2nm (Vx9t, (Xt: Yt-
D.I Auxiliary Lemmas for Proof of Theorem 3.2
Lemma D.1. [4, Lemma A.I.] Suppose Assumption B4. holds. Then, for any x, V E X, we have:
V + v,y v Vgi(x, (x S fg. ||v||
Lemma D.2. Suppose that Assumptions and 2.3 hold for all x, E X, and t E [T], and that t and dy are defined in (22). Then, we have
dx
dd (x. s M² [|y (x) + 1/1 (V(xv))
(122a)
|| day I M2 [ly - (x)) + |V -7(())1²
(122b)
(x)) - ff,,p('', 1x' (x)))) s Ly ||x - x'11,
(122c)
l1y (x) - -x(('') s Ly ||x x'1,
(122d)
[x][()) - -x7(x') S La ||x x'I
(122e)
Here, (x), St. and 57()) are defined (20), (18), and (19), respectively. Moreover, the constants MG. Mc and (by, , Lo Ls) are defined as in (42), (43), and (44), respectively.
Proof. We first show Eq. (122a).
43

---

Using Assumptions 2.2 and Bl., we have Vygi, (x. (x()) = Mg. and
[x) = |1 (x, 87(())) V Vyft.p (x,
(123)
Mg
Observe that have
|| {x - (x
(xfx
v Sy (x.y) - vx(x) (x.
- V px y) (x)
V 9c (x. yx y) - (x)]l
(x)()) V2 p
(x,
Cx.1 222500 11y 8](x)) la.11/ (x)]
S Mf (lly - (x)(x) ||v (x(x))
(124)
where My is defined as in (42); the third inequality is by Assumption 2.3 and the last inequality is by Eq. (123).
We now show Eq. (122b).
Since d Vy (x, 81 (x)) + Vygi (x, (x)) (x) 0, we have || pl = ||d ال
1/v. Viv. y) + Vyst.p(x.))
-r (x, (x)) + (x II (v: Vyt.p
- - 81 (x)]
S ||
+ (x (v
(x.)) Vyfi,p 87 ( (x))]..
Then, from Assumption 2.3 and Eq. (123), we have
||dY S f,,2lyy - 87 ||| (x)]1 + fo.1ll - (x)il + erally - (7(x)
< (nn22r <fmnalo + t/2 1 (x)) + -
Mg
S My (lly - (x(()) + (x)il),,
where M, is defined as in (43).
The proofs of Eqs. (122c)- (122)) follow from [67, Lemma 17] by setting (Ly, Lv, Ly) as in (44).
D.2 Perturbation Bounds for OBO Objectives and Their Smoothing Variants
The following two lemmas are inspired by [24].
Lemma D.3. Given p = (pa. Pr) as positive smoothing parameters, let px, y) and ft,p(x, y) be the functions defined by (18).
(a) Suppose Assumption B3. holds. Then, have
lgr,p(x,y) - (x, < lg,1 + p2)
(125)
2
(b) Suppose Assumption B2. holds. Then, we have
(x,,((x)) v) fx( (, + pf)
(126)
44

---

Proof. Let B1 and B2 be the unit ball in R and R respectively, Let V(d1) and V(d2) be volume of the unit ball in R2 and RR,, respectively. Then, we have
(x.,) - yx(x,y)]
1
J / (x
p&S.y P68, + p.r) - gr(x, y)) dsdr
(dd))
Bi B2
/ / (xx(x P&8,Y + p.r) - (x, (V (x, (p28, p.r))) dsdr
(d2))
B, BB
Thus, get
(x,,p(x,)) y))
19:(x + Pa5,y p,r) - (x(,))) (V,x(x,)), (058, dsdr
B,
B2
F9.1
(
dsdr
B1
B2
2
9g
|s||2ds
||r||2dr
2
2
19.122
d1
lg
d2
2
d1
+
2
d2
+2
l
(22 + p?)
where the last equality follows since v
d víaj JSEB || atp"
The proof of part (b) follows using similar arguments.
Lemma D.4. Given p (Pa. Pr) as positive smoothing parameters, let (x, y) and fr,p y) be the functions defined by (18).
(a) Suppose Assumption B3. holds. Then, we have
[V.r,((x.y) - Vie(x,))] 1 Lellpedh + prd2)
(127)
2
(b) Suppose Assumption B2. holds. Then, we have
[V (x,,((x s lpalpad + prd2)
(128)
2
Proof. Let S(d,) be the surface area of the unit sphere in Rd,, Moreover, let UB, be the unit sphere.
|| (x,,,,(xx,,
(x)r(x,
d1
gi(x + Pss. y)sds
- -xxe((x
5(d1)
Ps Un,
di
gi(x + pss,y)sds / Ps
di y)sds
S(di)
Ps Jud
(V Vx y), ps )
d1
JuB
Ps
d1
gi((x + pps,,y) - (x, - ||s||| ds
S(di)ps
JUB
di
E ( ||s| ds
S(d1)Ps
Juen
Pad16g.1
(129)
2
45

---

where the second equality follows from Jua, ss ds S(di I. d,
Similarly, let S(d2) be the surface area of the unit sphere in RR Moreover, let Un, be the unit sphere.
yt (x.y) (x)((x
1
d2
/ gxxx p.r)rdr))
Vy00(x,y)
S(d2)
Pr Juz
1
d2
/ (xxx, + per)rat
/
de
y) y/rdr
S((2)
Pr Uuz
Jug Pr
d2
(x, y), P
Juz Pr
d2
1 19c(xe, + Pcr) - 9x(x,y) x),
- S(d2)Pr
Jung
$ d2
l9N1PE
Jees ||=|| dr
S(d2)Pr
prdz6g1
(130)
2
where the second equality follows from Jun, rr dr 8ida) de
I.
Thus, we get
Vgc.p(x.y) V yl
< V (x9t,p(x,)) - (xgi + | (y.t,((x,)) (x)
Padi1g11 + prizlg.11
2
2
Finally, by similar argument as in Part (a), obtain
VV (x. - Vxfi (x, s Padilg,1
(131)
2
and
(x.)) Vyfe (x, x)ll prdzes1
(132)
which implies
IV (x,y) (x.x)) s (padi + prd2)
Lemma D.5. Suppose Assumption B3. holds. Let v 99 y: Bi) and Vxgi (x, y: B,) be defined as
in (24a) and (24b), respectively. Then, for any (x, y) Rdh x Idda and Pr. Ps 2 0, we have
362 d2r
E || (x,;
< ld 9. Ily 5112
(133a)
(r,8,)
2
3 9.
E (s.B.)
(x, y: B.) (x.
< 3d4 62 12,11x x||2
(133b)
2
for all & E Rd and & E Rd..
Proof. The proof is similar to that of Lemma 5 in [42].
46

---

Lemma D.6. Suppose Assumptions 2.2 and B3. hold. Let (Ps. pr) be positive smoothing parameters. Let yi (x) and y? (x) be defined (1) and (19), respectively. Then, we have
- x((x)) lg.1 1/ +
(134)
Since, by Assumption 2.2, gr y) is Proof. From (I), have (x) E arg min ge gx(x,
1gg-Strongly convex with respect to y, follows from Lemma B.2 that
(x)]1 (ge (x, de (x, (x)))
Pg
By setting y (x), we have
(x) - (x)) v
(ge (x, (x)) - Se (x,,,,,
(135)
Mg
Similarly, from (19), we have
[a P&8. y + G.):
(x) E arg min yERd2
(x,((x,))=
E
(s.rit))
where p (ps. Pr). By Assumption 2.2, Pi (x, is M4y strongly convex with respect to y. Hence, according to Lemma B.2, we obtain
2 (ge.p (x,y) -x, (x))))
ly {x(x) I Ugg
By setting (x),, we have
2
[ly](x) y7 (x)]l
(x))
(136)
Mg
Summing up (135) and (136), get
1
[x) (x))1
S
(x. - 91 (x. (x))
My
1
+
(g. (x))
(x, 37 (x))).
which implies
1
(xy (x))
(x, yē (x,
9r yx
Fg
+
1gt (x, - (x)
14g
g (p + p2)
Pg
where the last inequality is by Eq. (125).
D.3 Bounds on the Zeroth-Order Inner Solution
Recall that Rdi and E IRda are vectors uniformly sampled from the unit balls B, and Bz, respectively. Let
Uh (s, E E U (r, E ) U3 = (s, E R =-= (r, E R
be generated from the uniform distributions over the unit spheres (UB, UB.). Here, (UB, UB.) denote the uniform distributions over the (d1, (di,d))-aa diimensoiol unit Euclidean balls (Bi, B2), respec- tively.
Then, similar (23), have
E
fy B.] = Vyfr,,(x,y)
Vxf( B.) = (xf
(.g.B.)
(Ug.B.)
E (Ug.B.)
V B.)
Vyg(,p(x.))
E
(x B.)
=Vx0)p(x,)) (137)
(Ug.B.)
47

---

Lemma D.7. Suppose that Assumptions B3, and DI. hold. Consider the sequence Ve)
generated by Algorithm 2, and define
c. V Vyst.p(X....)) -
(138)
Then, we have
E El 11? - (1 - ( 12(1 - 70111
V V - (x)((xx)
+ +9d26g.11 -4+1) /² + 24 (1 - 2 x xxel?
0 2
7 + 24dz -1 yl+1
y:ll² + b 1t+1.
(139)
Proof. From the definition of d in Algorithm 2, we have
a az = -- d + 1+1 (x11 BB+1)
+ (1 (1- 7+11 (y9 - (x) (i Bett))
Then, have
E y (X+11, - -'++
E Vy
X F(+1] àà (d )|
EE V X1+ F(t1) - -. + rl 7
- (1 7+11) (
- 9 Vr; Bi; ||?
=IE](1 7
d
+ + (V - (x -V---yyg (x,.,)
(1 (14))+1) (V
+y0t+1, (x, y.) (x.,))
(x + V 11
Bett)) 11?
From (137), we have
E v Vytti (X Beti) (ett 1x0t1)((111))))))
E
A Vygt+i (X B++1) (xx B4a)
119t11((x41,
(x),
then, we have
E| V (x
112
= (1 - 2 (x,, - d/11²
+ El/ V -
+ (1 - 7+41 Vy (x VyIt.p Vt) + Vx9t+1o(XxN) (x9.+1,(Xx.11)
(,0 ( B.+1) 112
(1 2 ) d
+ 2(1 - 2 (x V (x.
(x
+ (x. B111)l1
-
+ 27/4 El (x -
48

---

where the second inequality holds by Souchh--Scwwand inequality.
Then. from Eija E[a|] E|aa|| ||[[|]| and Assumption DI., we have
E (x+ a=+
BB y (x,, (x. 1
7 ) 7 V (x), (x N:)l2
62
+.(11 - 7 7- y.t (1:1
B.+1) - 12
(x 27 b
$ (1 7 3
+ 4(1 - (0(1- V Xz: yx. - 3x))
+ 12(1 .++1 d2 9.1 E2
[x4+ Vt+1) (i)l?
+ 3(1 - 7 4. d2 27 b
9r
where the second inequality follows from Young's inequality and Lemma D.5, From Eq. (130), we have
B|| (x.,)) - V y (xt,
< 3E V px y:) (x
+ 3E y91+1(xx,.,) y.) - (x)
+ 3E V (X,,
(x))
3pf 9.1
< 3E Vy9(+1 - (x),
2
Finally, we get
11411 - الا+ < (1-1144 Vy9,, "
d. 1|
+ 12(1 V, Vygo(x, 6 7 2
62
+ 12(1 d22 (X(4,, (x,,
3(11)++)))) d2p7 -
gy.
b
Lemma D.8. Suppose Assumptions 2.2 and B3. hold. Then, for the sequence ((x. ( by Algorithm 2, we have
generated
Illy+1 (1xx)1 S (1) (1- (1-28, 1ggg.1
E |llye - 57 (xxe)1
Mgg + Eg
(-11 +a)
2
88
E (x.
Mg + E
(1 (1+})888 ) [||{?0133)
where 0 constant, &e defined in (138), and (xx) is defined in (19).
Proof. From Lemma B.4, we have
E [llye1 (x)))] = E [1y: B.d.y (xx))
< (1 + a}L [|lx: V. (xx)))
+ (1+ 3 fiāæ V
(140)
49

---

Next, we will separately bound the first term on the RHS of the above inequality.
We have
Ilye -V
(xx))] -
LE Ily: sI(xx)) 3R II (x.)))
-23,E ( y.t (X,, No), {7(())]]
1 - 23, M
E [|l., 9
Mg 6
2,3
B3
E
(141)
1g + lnp1
where the inequality results from the strong convexity of gr.p by Assumption 2.2, which implies
Mgly,1 I1ye - 57((x)11 +
(x,, (7 (x,))
U1 + l, Vy.9t, y1)
Mg + lg.11
Substituting (141) into (140), gives the desired result.
For notational brevity in the analysis, we define
0% = lly, (x,))l 07 = llv (x,)
(142)
where (x) and v (x) are defined in (19) and (20), respectively.
Lemma D.9. Suppose Assumptions 2.2 and B3. hold. Let 0% be defined in (142). Then. for the sequence (x)), T generated by Algorithm 2 guarantees the following bound:
[BI0X+11 - -B(0"))
4L3 T
Tu Σ
BI0M1 + Lyg t=1
Σ
Ille 1221
3: +
E
El[x:
X
x++1 112 1
Lug
Br.
T
2Al
12
(p² + p²) +
sup 1 - -x(()))
LugKa Pig
Lig
xEX
Be
2
+
B
E
yg (x.. x
(143)
Mg
+ l
where by
fa1 is defined as in (44) and Lug Pg
Moba
My +b.1"
Proof. From Lemma B.4, we have for any c >
E |ly++1 - Vitz 1X
= ||lx++ - 87 (xx) + (xx,)) - (x++1(
< (1 + c) E [[lye+] - (xx))]]
+ 1 +
E [| (x - 5x
(144)
From Lemma D.8, we have for any a >> 0
Hgga.1
E ||lx+11 21
S (1 + a)
1-233 2,3
IE [|ly: - -x:()))
Mg +f
2B, - 83 )
- (1 +a)
E [||] y. (xV (x).))
Mg + l
1 1
Be [1c220113]
(145)
50

---

Substituting (145) into (144), we get
[ly+++1 81+1
(1-23, Mg
s (1+ a)
- (xx)))
My + l,.1
+ (-(1+0)(1+0))
2/3
B²
[V
Mg + bg1
+ (1+ + ) [1e]
+
1
E
- 577
(146)
32Lpg/ I-3rhpp
Deking I-25,knn
Choose
and
Then, the following equations and inequalities are satisfied.
3eL
(1+0) +1(0)(1 + a) 23,
2
(1+ a) - (1, =
:ellppo (1 + c) (1 (1- Be =1 BeLing
(147)
2
1+ < BeIpp
1
Br BeTupa"
where Lp,-
Molal Mo
Based on (146) and (147), we get
E fllyet1 (x )1 E [lly+ - [x,)]]
S BeInz
E |ll:: 9 (xx))1] + (-
2.3
-33 )
2
Mg + lg.1
2
2 E 1 -52 (xx))
+
8 [I|e
20
[1
(148)
BeL
B,Ln,,
Next, we upper-bound the last term of the above inequality.
E ||1y (x++1) - (x
2 (E ||9 (x(+)) Sit1 (x)) + (1) (x))))1
2 (L [||x X 2|2 + [x+)+((x)) (7(x))
(149)
where the second inequality is by Lemma D.2. Moreover, from Lemma D.6, get
E 8. (xx )
< 3E
||| (x:) - (x))1
+ 3E
|lv - (xx))1 + 3E |xx,()x)) - -x((x)11
6l (p² + p?)
< 3E |ly (x:) - xxx
(150)
14g
Combining (149) and (150) yields
E [11(+11(x+))) - (x.)
2 12 [||x - xx+1 [|3] + 3E [1y (x²) - yz y2 (x 66, 1 (0 +
)
(151)
Hgg
Substituting (151) into (148) and summing over E [T], give the desired result.
D.4 Bounds on the Zeroth-Order System Solution
Lemma D.10. Suppose Assumptions B2. and B3. hold. Let
= fi BB+1) + Vz (Zc+1) Be+1) (eftti(z,Bee))) B.41) 4394+1 12
51

---

where yyft and Vigi are defined in (25a) and (26a), respectively. Then, for the sequence ((x,, Yt, ve)) generated by Algorithm 2, we have
96 9.1 2p
96
0 S (12f
d2
Xx+1 x,,12 (12 +
9.1
Id2Blly++ y.
2p
362
+ d2 22
v
v.l12
+ +3(7,11
dgp.
2 g.
4p
Proof. From Lemma D.5, have
1 ( B.+1) - ftfi+i 1ll1
3 le
I 3, ///l///4111 - 21 +
2 f.1 d22p²
6d222,1111411 - x1112 6dz 12 f.1 |y++ - yell + 22 db
3
(152)
Moreover, from (26a), we have
14 ( V3 (2r
11 / Ix + P V Be+1) &ylt+i - Dv Bi+1)11
4p²
3 p2 dspp
1 11 + pvv(+1)
(xc, Pvv.)]1
4p²
8p2
$
4 g.1 _..1|x(+11 - x1|13 + d2 g.1 1lyc+11 - yell2
d2
402
d2 1.,.lllv llve+111111111
vell -
22 Esp
(153)
8p
where the first inequality follows from Lemma D.5.
From I|a + b12 < 2 (||a|2 + [bb])), we get
0 < 2E 22 91 (z-11 B(41) V g B(+1)l1
+ 2B V y / 21+1; B++1) y (2:: 11+1)11
96
962
< (126
2p²
dd X1+1 x111 (120²
f,1
+
2p
)d,Elly<41 y.
362 9.1
+ 2 1 B141 v2 + (36)
4p Pd
where the second inequality follows from (152) and (153).
Lemma D.11. Suppose Assumptions B2., B3., DI., and D3. hold. Consider the sequence
Ye vo) generated by Algorithm 2, and define
t+1 = Vy.f422((x41.80-1) (144( dy where (154)
1
2pv 4 29941 (X41))141)) = ( Ty94Lp(XH1. + poV(+1)
-V (vVe.)).
(155)
52

---

Then, we have
Elle Mr
1 s
(1- (1=
36B (x,, (x,,
3
p + 18d2 P
+
18d2 + 6(3(),1 + n.1
4p
dd3
9.2 22
18
+
B V
Fx yr + Avi.) Vygi(xi + pv
18
B
V AvV.)
Vygi(XE. -vove))
90
96
+ +6(12
+
12 + +
/d2 - -vll?
2pº
2/
02
2
+ 27d269, 3.1 El V241 vel12
3
by )1+11
(156)
bp
Proof. According to the definition of dy in Algorithm 2, we have
a - -y =d de-1 A (ze+1i (4+1::4+1) + V (Zot:BB)
(1 --teta) (Vyletz (2441i B2+1) + (8
-y-fe B(+1) 9 (4.
Then we have
E V (1411 + Vy (2 - 1
E| (2441 + 7y 1 (2(41) à. - (a)+) 12
V 7 1 (2++)) - dz + X
-d++1 (yylemi (26+ By_ + 83 92 (2++1; ::++1:B++1))) f (Z(41; B.+1) - -(1 -(1-A (Vy Z1 11+1) + 8700+1
-Vyfetizz Vy 1 (z; B, B, )) 1|
E]I(1 - ) (V 7990 (z:) -dp')
+ Aet1 (44(VVy.1122,224111 + 710++1
Vy.f411(241;; 73 B.41)
+ - ) Vyfttt. (2 + 73 ( - vyft,((z)) (Z
+ 1 - Vyle+1,(2z) - &(9441(2))
(24441 B.41) 43 99 (2.41; B. + (zfe41 Be41) + 4 (zi 112.
Since
E (2f44(Ze411::.pp 4
(2444)(22411) + V 4394 (2e+1),
E
Vyft (2 B,41)
(24 B.41)
Vyfr+ (z:: B.41) 73 (zy: Bett)
() + (2 Syf(.. - (39(+1
53

---

then, we have
E V ( ( di 1|
= -1- VI + (1(((2)) d
+ + Vy (4+1) (y (2441(241::441)
+ (1 1 fy 4 vyf(p(zz) - (z))
+V (2)) + 8 (z.) (y (2c)+1(2))
(z B V3 1 B(+1) yyfe+1 Bet1) + ( BL)) 112
I (1 - \
B V. (z) + 7 (2)) - d212
+ 3 1 E Vy fy (1+1 + 4 ( (z(-1) Vyfip(zz) (7z9(z))
Vyf++1p(zi
y (z1) - Vy vyfi+1,h (zi) - Ffgc+1
(
43 7 B(+1) + Sy (Zt; BB+1) 22ge+1(25 B1+1))12
+ 31 (
Fy (2, B1-11
33
(2++1) - 3 ( B1+1)]1
(157)
where the second inequality holds by Sauchy-Schward inequality.
Note that, for the last term on the right-hand side (157), from (26a) and (155), we have
(2+1::
< 21
(200)1((411.441 Av+++1) Vy9++ + Be2)))
2pv
+ 2pv
2|1
B -
6²
6p2
where the last inequality follows from Assumption DI.. Then, from Ella- E|a]|| E||a||2 ||[[|]] and Assumptions DI. and D3., we have
V.
&5 - d 1
$ (1 - (
+ (z))(z)) - 2Ø
- + 3 + V3 139(+1 (z,) Vyfe,((z)) (2)(11))
+ +61 - A.+1 ) 3 BB + 739t11 B,41)
02
f
[yfe+1(Z; B. 4 (2 B 32241
my
+
bp2 b
Then, from Young's inequality and Lemma D.10, we obtain
ft+1,,++1(( + V2 1 ay 1|2 $ (1 - E V (z, + (z9((z)) |
+ +1((1 A.. E V /
(z))l
+ 12(1 - 12(1-A(41)8 FE
- - )1
9/2 0.1
962 Jdzllyet -
+ +6112
ddz
X1+1 x+|12 2 6(120
2p²
2p
322 + 27 4.1 || - v2 6(303 +
0
g.1
)dZp + +322
+
)
(158)
1p²
hp2
54

---

For the third term on the right-han hand side of (158), based on (155), we have
y 9 (x) V e (Xe:
< (xt
Xt: yt +rv.) - (x Dovv)l
(159a)
2p
1
V - V894110(x6... -
puve)ll?
(159b)
2
For (159a), we get
+ Yt + yx < 3 V Vyg++1, N1 +vV)) V99c+1(X,, + pvv))
(x
+ 3/ V.St++1 Yx. + Av) - Vysr(X,, yr + v.)l (oVi))
+ vx PvV.) yc pvVil
32 8.1 puv.ll
S 3 Vygi yr + v.
where the last inequality follows from Eq. (130). Similary, for (159b), we have
-
3pf
< Ve - PvVe) -
-
2
Substituting the above inequalities in (159), we have
gh (x.. - (x,,
3
V Yx Yo
(x P
2p²
3/ 3.1
+
Vygr - P.v.) Vys++1(x,, - x
(160)
2p
2pp
For the second term on the right-hand side of (158), we have
(x (x,, y+
< 3 V fyft1, (x,, yc) (xf yi)l
+ 3 V I y:) Vx yc)ll
+ 3 fi yt) (x,, y:)l
3pfdBe7
$ 3 V v.) - I v.)
(161)
2
where the last inequality follows from Eq. (132). From (160), (161) and (158), we get
f( + (20041(2(+1) - dy 1|2
< (1 -
+ (2))(21))) - d2y
+ 36
V Vyfe+1 ))1 + 18p.
18
+
(y + pvve) - Vy9t+1 + p
18
V Vy9k (x,, vvV:) - 18p2d3
9.1
962
962
+ +6(22 +
)dg X141 - x111 + 6(120 +
)d
dd2ll++1 - y2ll
2pp
2p
322 9. )dbp + 3X2
32
+ 27dg 3.1
||111111 v.l12 6(36
[r)
40
hpg
55

---

Lemma D.12. Suppose Assumption B4. holds. Let
e Vi (Xe, vc) y (xe. Vo.
(162a)
e = V (x) V 9t (x1, Ve.
(162b)
where
93 Vr) = (V (x. vvV)) Ve pv
1
2pv
gt (xe, Vo)
(VxSt.((X.. PvV.) VxIt,p(X,,)1 -
2pv
Then, for (Xt, Vo) presented to Algorithm 2, we have
(a)
c [1]]"]
s Slypppp
(163a)
(b)
E I|lee11"
e L22PEp4.
(163b)
Proof. For part (a): From Lemma D.I, We have
E
H
E
63 9gth (Xc, yr) Vygt (x). Vo
$ 2pv
St Xt, + p.v:) - VxIt.p(x..1)) Vygr.p (x)
1
+ 2pv
E
Vygt, yc) Vx Vigi (x),
|Ivll
(164)
where the last inequality follows from (8). For part (b): From Lemma D.I, We have
E e
2 xy
(xr. Vr) - 2y (x),
=
S 2pv
E
[|| |
V
(x,, povi) Vx V2 Vzylt (x), v.
1
+
E
VXIt,
Vxgi,pXx,. -PoVi) - VxySr,p (x), vrll
2pv
$ E
[|]]|]]]
S L,2ppp"
(165)
where the last inequality follows from (8).
Lemma D.13. Suppose Assumption B4. holds. Then, for the directions dy and d provided to Algorithm 2, and
(a) for d defined in (22b), we have
di 11 < 2B [|3
E
d
28 2022000 =: B.,
(166a)
where e. (xfi Vzga (xe, vr. ay is defined in (154).
56

---

(b) and for di defined in (22c), we have
E
d
di
2 ||eb |2]
26 22ppp
(166b)
where
of= (x., + Xx dj.
(166c)
with V (x:: yc) defined in (172).
Proof. For part (a): Let
1
Vi (x,,
(x
(x
(167)
2pv
According to the definition of di in (22b), we have
E
dy
d.p
= d (yJe,(x(,)1) Vyst. (xe, yc) ve)
S 2E
j - (x,r.p(x, - V3 (xe,
(168a)
|| (x) Vzgt.p (x,, vc) v 11?
+ 21R
(168b)
Next, we separately bound (168a) and (168b) the RHS of the above inequality. Bounding (168a). We have
2E
ay
Vyfii
ge (x (x
[|]
2E
|10./111 12]]
(169)
Bounding (168b). From Lemmas D.1 and D.12, we have
(168b) E ||e"" !1?
< 36 22p
(170)
Combining (169) and (170) yields
E
a
d |"] 21E [12
+ 26 20222020
(171)
For part (b): Let
2 ky (Xr, vt) (V
(x: PvV.) -x
(172)
2pv
According to the definition of di in (22c), we have
a Vxlte(Xx,,1)) - Vxy (xx. v v12)
E
ax
d
= RF
2B
(ay Vxfr,p(Xe - (Xt, yc)
(173a)
|2 (xr, y+) V2 Pt (x.
+ 2E
(173b)
Next, we separately bound (173a) and (173b) on the RHS of the above inequality. Bounding (173a). We have
2E
(xfi,
2y (x (xx,
= 2E
| 11
(174)
Bounding (173b). From Lemmas D.I and D.12, we have
(173b) E
||e| ||]
< 26 22ppp
(175)
Combining (174)-(175) yields
27
dx 1.
S 2F
||
g 22
2F2
57

---

Lemma D.14. Suppose Assumptions 2.2, B1., B3. and B4. hold. Set the step size óe and the parameter p in (8), as
1 1ggg.1
f.
2
Vt (T), and p
(176)
M4 - f9.1"
Pg
Then, for the sequence {(xi, Yr: Vo) T= generated by Algorithm 2 and vi (xx) in (20), we have
d) (1- 81 Mg6
E
1l (x S (1+
E[ +
(1 à 82 Bi.
My 2g,1
for some > O, where θy and B, are defined in Eq. (142) and Lemma D.13, respectively.
Proof. By setting the radius p f..0 Ps
in (8), we have
E [[lve+1 (x,)11
EE
11 Z.
Vr - -bpd7] 1lz, [x7())))
lIve o, (x)))
(1 () E [[[v=
5.V.P. 8J (xx), vo) (xx))111
+ 11 +
6, E ||
VP,, (x1), vo)]1
(177)
where (x,, (x,), vo)
Vigte (xr, y7 (x,)) v. Vy 8 (x:)) the first inequality follows from non-expansiveness property of a projection operator.
We next bound the /,, and Ke terms in (177), respectively.
Bounding 4e- We have
J E [llve (x)) VV vo), (x,)))
+ EE [IVV (XL, S (xx) ve)1
25: Mg + gg
E - [[
26. Mg Mggg,1
87
(xx) v.)l
1gg + fg.1
where the inequality holds since
VP, is the gradient of the strongly convex quadratic program Vigr,p (x)) v + v (x (x)).
Thus, we have
E BVVP (I (x:), v.), V2 (x:))
MoLg.1 E [||v: (x:)
2 My + lg.1
E (Xx v.)
Mg lz
Since $ (2 Pg
Mylyn then we have Nottand
I 5 - 28, Mggg
( Mggg.1 8z
E [llve - (xxx) +
E [[ v.)
My + lg.2
fg.1 Mg lg.1
Gggg.1
<
8, Mg 2g
E [l|ve - (x)))
(178)
where the second inequality holds since from (20), we have
E [IIV (x))) v.]
E. [ (xi, 87 v. (xx
= E. 11 (x., (xxe)) (v: vx:))(
- eg E [llve - 4. (x,))
58

---

where the second inequality follows from Assumption B3.. Bounding K, Let
Ve (x, vc)
2pv (x - -x0t,((x,3:-AvV - pvv:)).
From Lemma D.13, we have
K, E ||dy (x Ve, vi]lP] B.
(179)
Putting (178), and (179) together with Eq. (177) yields the desired result.
E [Ive+1 (11141177(x.))) v7xx)11 s (1 + d) (1- Mggg.1
E [lvv- - v((x))1] + (1 (1+
=/ 8, Br.
8: My + Eg
Lemma D.15. Suppose Assumptions 2.2 and 2.3 hold. Let 07 be defined in (142). Set the parameter p in (8) as p
fre, Then, for any positive choice of step sizes satisfying
Pg
Mg
8, S
2
9.1
14
+ Egp1
the sequence {(xx, Yo, ve)
generated by Algorithm 2 guarantees the following bound:
Iag BTOY
110%+1]-B100) B(07)
Σ
Typ By 6z
16v²
T
1
+
(2L y
+ 1) Σ
IE ||xe+1 xel1
5,
t=1
+
T
966 122
(p' + p.) +
48v2
sup 1 - -x())) xeX
1
Lig uig
Lng
5,
1=1
(180)
where Br, u and (Iugy Iyy) are defined in Lemmas D.13, C.7 and D.9, respectively.
Proof. From Lemma B.4, have, for any > 0
E
Veei Vi+1 (x++1))
E || ||ve+1 (x.) + (x.))) - V (x++1)))
(1 6) [| (xx))11
+ (1+ ? ||00+1(((+1) (7)
(181)
From Lemma D.14, we have, for any à
E [Iver (xx)))] < (1 (1+6)
11 (1 8, Mg
0% + (1 7.
1
o4 Be.
(182)
1g Eg.1
Substituting (182) into (181), we get
E vee - ( (1+ =
1g6g.1 04
1-
Mg Eg.
(1+
1
+1++))
82
+(1
1
E
Vizu (x++1) (xx))1
(183)
8
59

---

Choose é= 6otingg 14 1- dihng
and á 6. 12 1-biling
Then, the following equations and inequalities are satisfied.
(1+ 6) (1 d) (1 - 6)L
(1+)) (1+ à - 8eL1p
(184)
1
1 5
1 S
à
de Lup
Pofel where Lpg
Mo
Thus, have
5e
JeT.gg
4 8.Br
E 111
02 +
Lnp
+
E
(xx++1) -1, (x,)))
(185)
Lug
dc
We now bound the last term on the right-hand side of (185). By Lemma C.7, we have:
1 41 (x++) - (x))2
2 (18(+1(xe+)) - (xx)11 + ||xc+1 - -xx(())xx|())
(21197+1 (x++1) - 81+1
11
+2 | (xx) - (xx(x)) + ||x++1 - -x1l²)
2² (213 [|x++1 -
-x,1= + x
++115+++((x)) (x,)) 11x+1-xx11) (186)
where the last inequality follows from Lemma D.2. From (150), have
[xx++1(x)) (xx))
31 (xt) yi+1
+ +31ly/ (x,) - yxxx)) 31lyy - (x,))1
< 3 yi+ (xx) - (xx)11 + gl (22 + p2)
(187)
Hg
Plugging (187) into (186), we get
V (x++1) - (
< 4
(2Lg + 1) ||x--1 x=l1
2
3 31 (xi) - (x,))1 blg,1 (p2 p2)
4
(188)
Then, substituting (188) into (185), rearranging the resulting inequality and summing over t we obtain the desired result.
[T]
D.5 Bounds on the Zeroth-Order Estimation Error of Outer Objective
Lemma D.16. Suppose Assumptions B2. and B3. hold. Let
= | B,+1) + (z
B.+1) - & (zu (2 BB1111
60

---

where Vxfe+1 and 2y are defined in (25b) and (26b), respectively. Then, for the sequence ((x,, Yt, ve)le= generated by Algorithm 2, have
962
96
w S (1207,1 +
)dl ||xx++ - x111 + (1269,1
)d dilly++1 - -rlll
2/²
2p
9
36
d1 9.1 || - voll + (367,1 +
)dppa
2
4p2
Proof. From Lemma D.5, we have
|/ (14+1: B(+1)
Vx (ze: B(+1)l1
3
3d1 9,1 |z+1 - z:l1²
2 f.1 e
< 6dg //,11111111 - xxl12 + 6dl ( blll+y++11111 - - 3
+ 2.
(189)
Moreover, from (26a), we have
Wy B(t1) 3 1 11+
4 1 VxIt+11 (X + Pv Be+1) V Xx91+1(xx:)X) - Pv Pv B1+1)l1
3 12
die (x11(xx+1. (vV (xc, Ye- Pvvi)]]
8p2 9.1
4p² 9.1 ||xx+| xxl12
d1 P2
d1 l2 g.1
1 yell
102
di G. ||v/+1
vell -vell= 8p?
22 of
(190)
where the first inequality follows from Lemma D.5.
From ||a b112 < 2 2 + [[bl(), we get
8 < 2| 22 xy 0y 1 B.+1) V x 1112
V f fe+ (2411; B(+1) Vxfe+1 (Zg Be+1)ll
962
962
< (1267,, +
)dl ||x++] - x1 2 + (1267.1 +
)dh ||y++1 - yylll
2p²
2p
- d1 62
9
|| voll2 + (36) f.1
362 g.1 )ah,p3
2 9.1
Ap²
where the second inequality follows from (189) and (190).
Lemma D.17. Suppose Assumptions B2., B3., D2., and D4. hold. Consider the sequence
((xt, Yt, vz)) generated by Algorithm 2. For et defined in (1662), we have
Ellet11 2 s (1 1++1) le, 1 + 36E (x).)))))) - vxf((x)))))
362
12 13 111.te
18 + 6(3,, +
+
4p
n.1 Pp
18
E| V (x.
Vx v2)1 +
2
18
+
E (x,+ - P.V.)
VxLi -
2
962
962
+6(128)
+
9-1 )di
2 661222
1.1
)d EE E - yel
2p²
2/
22
02
+ 22 12 El V(+1 - v2
(191)
9.
hp?
61

---

Proof. According to the definition of dē in Algorithm 2, we have
di+1 - dd = - + ne+1 ( + Iy (4++
+1 m++1) (vx ( + V sy 9t (Z+11;
(2; 42 xy (4:
Then, have
( + V Sy
1
E| Vx/1+1, + V2 Xy (2++1)
d;- - (d d
E/ Vx + 7 xy 91 (2++1)
dz + n
-144 (1 B xy 9 (Z BB+1))
(1 (++) (2+ B
+ 22 9 (2 BB41)
82 Sty (2; By- 1) 1|
- - (V + (c d.²)
=
+ + [Vx[ + V2 x ( (2+111 - 62 xy (2++1; Bi_))
+ (1 - 11-1)+1 Vx + 5% 2x - (xlt,p(z)) - (21)
(V) + (2 - (xf(+1 - (2
(xfL ( + Vxfe+1 B(+1) V2 (x: 112
Since
E
V (x + + ( Vxfe=1 + 42 Ey.e+1(Zec+1
E
V xy B.+1) (xfit1(z;::14 -2y Betz)
Vxfer1, (1+1) + 2 91+1 x V Vxf+21p(z)) 72 V2 (2y00+1(21)
then, we have
E V Vxfe+l + 22 dx 1|2
- V
72 ( (2x) d;112
+ |V + $2 x (2++1)
- 52 (
+ (1-7h+1
Vxf(+1,
42 1
Vxlt,p (2+)
+ +V
xy S (2:) Vxf(+1 52 (2
- (xftHi
xy 91 B1+1) + Vxft+1 Be+1) + F2 x2y90+1 (Z;; By-)) I|?
< (1 M1+1 2 V 62 (2 (2,) 171
+ 3(1 - M+ B / (Z(41) + 52 0 1 (z(+1) Vxfi,(zz) - 52 (2y0((z))
+ Vxfe+1p(z)) + 2 X S1+ (z.) V
42y (zt)
- (
B
- (
42 91+1
B1+1) + &xfe+1 (z:: Be+1) ) V2 90 (z;; B,
+ 13
(z B 2
+ 37 11 (2)11
4/2 1
Br )]
(192)
62

---

where the second inequality holds by Cauchy-Schwarzz Schwarz inequality. Note that for the last term on the right-hand side of (192), using (172) and (26b), we have
1 xy 9 (2++1)
V 1 B++1
$ 21
(VxItL,p(xxx11 + v++1+ V V + PvVe+1 B(1))11
2pv
211 2pv
(7 -. - Vx9+111(Xe1. - PvVe+1))]
-
0
where the last inequality follows from Assumption D2.. Then, from Elaa - [|a]]l== [
B||a|| ||] and Assumption D4., we have
E V
+ V2 1 d
< (1 - 7/+++) 2 V + 2 () - -d,12
+ 6(1 1 1) V (2x) + V 9t (z.) (x)(,p(2)) - V2 (x)))(2))11
+ 6(1 - 7++1) 1E V f 1 B(+1) + V2 1
02
Vxfi+1 B1+1) +
2
xy I1+1 (z) B 2| 37/
gx
).
(193)
bp
Then, from Young's inequality and Lemma 1.16, have
V - 22 ( d 1| $ 7/-1) x (t + V 2 (2t) d7 1|
+ - 7/++1 - E V 1 (2)) - Vxlt,p 21 1|2
+ 12(1 - 7 ) | V xy.
0t (2+) 2 (2:) )
9
962
+ +61127
dd X141 x111² 6(122
+
dd lly++1 - yell
2p
2p
382 9.1
02
02
+ 27d, & Gllllv+1 - v. 6(36))
f.1 +
+ 3
2x
+
In
(194)
4p²
bpp
b
For the third term the right-hand side of (193), we have
2 x 1
g 11 V (x.e+1,((x
- Vx.t
(195a)
2p
1
+
(195b)
2x
For (195a), we get
(x (vV:) Jx
< 3 V Xt. Yt +vv,, Vx v=)1
3/ VxI++1 (x.. +
+ v.):) - Vxgi(XI, yr + +PV:
3/1 Xx + AvV, Vx pvv:))
< 3 Xxg, yt + p.v)) VxI++1 y: + 2 +
where the last inequality follows from Eq. (130). Similary, for (195b), we have
||V xxt, -
3p
< PoV,) - +
2
63

---

Substituting these inequalities in (195), we have
V
xy (x v1)
3
VxDr Y+ (. - tx
2p
Yt PvV.) - 3p2d9
(196)
2p
2p
For the second term the right-hand side of (193), we have
V (x V (xfe,p(x( yill
3 V /x. (x
+ 3 Vxfe+1 (x), Ne).
+ /x
(x
< 3 Vxfi(xx, y:) I v.)1 3/2
(197)
2
where the last inequality follows from Eq. (132). From (196), (197) and (194), we get
B|| V + F2 xy (Z:+1) - 1 1/2
< (1 -1- 7/ 11 St, + 82 2y 12112
+ /.6///2./. Vt) - Vxle+1 yt)l 18pp
18
E Vx + Avv) (.v)
(x,, / v.)1
P
18
18p2
vv))
Vx9++1X, y: 2v
9.1
p
962 ø.1
962
+ +6122
|d
X141 x,11 + 6(126)
)d
EdyElly:41 - y2112
2p²
2p
362
02
82
+ 27d1 1,
Bllve+11 - vv 2 6638, + 9.1
jd9p3 2
+ 31
9x
+
Jx
40²
hp2
b
D.6 Bounds the Zeroth-Order Objective Function and its Projected Gradients
Lemma D.18. Suppose Assumptions 2.2, B2., B3., and 2.4 hold. Then, for the sequence of functions (fr 1T defined in Eq. (18), we have
Σ (((x)x (xe+1 1=1
(1+ Eail
2M + VT + &5,1
T (0z ( +z))
bg
Here, VT is defined in (11); and M is defined in Assumption 2.4.
64

---

Proof. Note that, we have
(((xi)) - (x
((xx)
(198)
T
(f - (1. (1
(199)
T
+
Σ (1 (xxx)))))11(xxx1188((00)))))) 1=1
(200)
From (126), we have
(198) - T Lrall2 + P?)
(201)
2
and
(200) - T 25.1003 02)
(202)
Moreover, from Lemma D.6, have
(199)
(((x)) - yxx))
(I((),,)(x)))) ((
t=1
f.1 Σ [xx1(x)) vx(xx))1++++++ l,1 Σ (x(+)) -x((x)))
(( -
laalph + p2)
< 2T
+
- (xx (203)
Hg
m=1
For the last term of the above inequality, we have
(xx)) - - (1ls::/((o)))---ssss---..lr.
Σ -00
t=2
2M + VT,
which implies that
(199) 2T Eg + p.)
2M + VT.
(204)
Bg
From (201), (202), and (204), get the desired result.
65

---

Lemma D.19. Suppose that Assumptions 2.2 and 2.3 hold. Let ft.p be defined as in (18). Then, for dø generated by Algorithm for all t [T), we have
E d (xx,
- 4E [|
+ 46 22g.2ppp
+ 2M BBO0 E(τ!1)
= A
(205)
where et is defined in Lemma D.13, and 0% oy are as defined in (142). Additionally, M, given in Lemma D.2.
Proof. From |aa + b1l2 < (Ilal2 - [[6|1?) we get
a v (x,, (ixi))
|āz dii [7]
$ 2E
(206a)
+ 2E
||dd,p - fx 87 (xx)) (x]]
(206b)
where d. is defined in (22c). From Lemma D.13, we have
(206a) - 4E ||e/ 12]
462 22
(207)
Moreover, from Eq. (122a), we get
(206b) S 2M3 (BTθ)) + E(OM)
(208)
Substituting (207) and (208) into (206), we conclude the desired result.
Lemma D.20. Suppose Assumptions 2.2, 2.3, and 2.4 hold. Let the sequence of functions { |T=1 be defined in (18), and let Px,., be given in Definition B.1. Then, for any positive choice of step sizes satisfying at I 1/4L,, for all E [T], Algorithm guarantees the following bound:
Σ 1=1
(a. - L
|ixx, (xii (xx,
12M + 6VT + Σ (6ar, 3Lyaa) A.
Σ
66 6l 2
+
3 3 (ar L (02 + p2)
(209)
Mg
Pg
where VT and A, are respectively defined in Eq. (11) and Lemma D.19.
Proof. Due to the smoothhhesss of the function f. by Eq. (39c) in Lemma C.1, ft,p is also Ly- smooth. Hence,
11 - (x. (xx))
Isf x1)
(V (xx, (x))) x4+1
|x x1 ??
2
-aa (f Px,
(xx: di
I T
||x (x):âz))(
(210)
For the first term the R.H.S of Eq. (210), we have that
66

---

(x,,, 82 Pxicce (xrid;)
(dr, Px.0: (x:dd]]
V (X,, 8r (x+)) - -d,, Pxçcc (xx:d()
$
Pxx,a
Xp: d.:
/1 27
+
E
|ay (xx,(xx
1 R ||x (x
||]
2
A
2
+
(211)
2
where the first inequality follows from Lemma B.7; the last inequality follows from Lemma D.19. Plugging the bound (211) into (210), have that
1x (xt
(L an) |x..a (xci dx) 12] + a,Ae
2
which can rearranged into
(a+ - L ||xx00 (xx:d)))
$ 2E (xx (xx)) - (x (x++1)) + axA.
(212)
In addition, we have
| Pxx (x:; (x
|| (x::d;) - Px (x:s px,p( (x (xx)))
S 3E
+ 3E
|xx (xii Ve.. Sx (xx - Px (xei (x
Pax,a ss::d))1?
+ 3E
| - (x
< 3E
+ 3E
f 87 (xx)) - v xx
Px (x:: d 11].
+ 3E
where the second inequaliy follows from non-expansiveness of the projection operator. Then, from Lemma 1.19 and Assumption B2., we have
E || (x;; (x,, (xx)
(x,
||xxa (xx:az))1 11²)
34, + 3 E xx
+ 3E
< 3A, + , eg. (pz + p2)
Pxxc (xx:d;)) )(1
+ 3E
(213)
19
where the last inequality is by Lemma D.6.
67

---

Combining (212) and (213) and summing over t = to T, we have
r
(ar - Lya
E |Ipx (xi Vx
6
Σ
(x.
-=1
(ps Pr) Σ
(at L)az) +3 Σ
(2a: L)aî) At
Mg
1+2 (6
< 12M + -VVT + 61
T (p= +
Uy
365,18,11
T
T
(02 + (r)
Σ
(or - I.gaūt
+ >
(20x - I.jaat Ac.
Ng
t=1
where the second inequality is due Lemma D.18.
Lemma D.21. Let the sequence Ye. ve) be generated by Algorithm 2.
(a) Then, have
11y-11 y 2. V
where e is defined in (138).
(b) Suppose Assumptions 2.2, B2. and B3. hold. Then, we have
X - x111² S 4a Pxx (xx Vxx
48 1 + +i) + 2A,0,
+
(214)
Pg
where A₃ is defined in (205).
(c) Suppose Assumptions B1., B2, and B3. hold. Then, we have
1 12 s 20 1| 3d269,18 88
82 oz.
+ (128g + 662 10? + 602 a.l Pva
where ef and 0% are defined in (154) and (142), respectively.
Proof. For part (a): From Algorithm have
llye=1 - yell 33 ||a 122
< 2,8 || - ( v.)l (,
2,8% 1 2,3 (x.
(215)
For part (b):
68

---

From the update rule in Algorithm 2, we obtain
|xx x(+1|1 x a² Px,aa (x4: de: 1
3 20² (IPxx (xe: (xe, (x,))))
+ |xxo (xr:dī) - Px (xi: V (x 1*)
87 s 2a (IPx. (xi: (x)))
+ | - Vi 97
s 20 (IPxx,0 (xt: (xx, + A.).
(216)
where the first inequality is by (a+b)² < 2a 262; the second inequality follows from non- expansiveness of the projection operator; and the last inequality follows from Lemma D.19.
+
The first term in the above inequality can be bounded as
Pxx (x:; V (x,, y (xx))))
IP (x:: (x. - Px,a. (xii (xx,((x.)
1Px,o, (xei V (x., Xx.,
< 2 V St,p 87 V xx
2 PXx, (Xxi Vx.,
< 20 (x+) - y7 (x+))1 + Px (xi: V
< y. lg. + p2) + 2 P (xy: fi y(x
(217)
Hg
where the last inequality follows from Lemma D.6. Based (217) and (216), we get
|x xx++1 s 2a 21 (xi xxx, 28 2
pt) A.).
For part (c): From the nonexpansiveness of projection, we have
||Ve+1 vz = |||z, [v2 6.dr] 112, [v.]
< 12
S 2071ldx
- (z -yf(p((z))
Vy + (z)((2))1
+ 258 || VtJt,
(x. +vv)) (x - - ?
2p,
< 15 +
66?
36?
30
(x. +
(218)
2pv=
2pv
where the second equality follows from (154). From Assumption B3., Lemma B.3 and (8), have
V (x y v=) < e fully: Ily + Pvv. - (x,))
s 28 n. | 12 + 26, lly: - (x(
< 2 g. 1220 + 26 1 (x
(219)
69

---

Similarly, we get (x - S 26, 2. + 26 2.111 (x,)1.
(220)
Moreover, from Eq. (132) and Assumption Bl., we have
[Vyy(,,(xx,, vT)l - Vx Vyf((x, +
del..iet + 211 (x)x
2
d2f T.PE
2
+
207,1
3.0'
(221)
Substituting (219), (220) and (221), into (218), we get
||ve+1 vell S [| Ao || + 1.
66
+ (1207.0 + 662 10g00)00 00? + 9 oflly - (xxx11
Pv²
D.7 Proof of Theorem 3.2
Proof. Since (1 7++13² < 7 and 7+11 = C, in (31), from (139), we have
El 21122111 112 - 1|3 v -le
+ 12(1 -
- v1)I
+ 9d26..11 (1 - -+ /²/ + 24d2 (1 - -)++1) E||xx++ - -x,12
(2.12
+ 2dd2 - (1-1111-))) ) Y2+1 - yr11? + 2 02
1tT1
(222)
b
Since (1 12 < 1 7 and mo+1 = Cr,0r in (31), from (191), we have
Bllef+1l1 2|2 - Ellet 113 - -c, + 36E V Vxfe+1 Vo) (x)(
362
22 Pa
+
18d4f,1 + 6(367, +
4p²
9.1
)d
22 + +18c22
9.1 2t
36
B xx yc + vv))) Vx V=
+
2
982
9
+ +6(12
f.1
+
20
9.1
)d
111x++1 - x111 + 2 6(12(, +
2p
9.1
Bly - 2
02
+ 27c2 17 V1+1 v. + 33
+
1x
Mi+11
(223)
bp?
Since (1 - >x+11) <1 1 - A and det1 = cxa, in (31), from (156), we have
M 2| -0--EE Elle," 112 S Eee 112 36E ( vy)((x))))) E| EleeM1ll
36 20
+ 18633, + 6(367,1
d
13 + 186222
9.1 p2
36 1
+
E Vy y, + vv) - V (x y: +
P
9
9
+ +6(1277 +
)d2R X++1 - +
Ed2 - y.ll
2p²
2p2
82
02
+ 22 9.1
Bl| v. + 3
+ b/ ) JM
(224)
hp
b
70

---

Combining the outcomes.
Let
B1AY ++11
E(AM1)
r
(0(0~=]-=1007) 1(101)
+
1
[ c 11? 111
$ t=1
(BlleH41l1 -1
Σ
[Blee (Bllef+1 11 Elett19)
V
Here, we have
11M4
52M
T
Ln,C0 CB
I cs
240 dzl2
12d2 g.1 L3 2
Φ max
L,
M2
(225)
d2 111
Ipp
144dz f.1 [11 + lg,1)s3 3662 f, d2, M4 G3
2
V max
720
27
f2 d21 TI.
I,f
T.pT
M
dil7,1
Lio 22 dics, n.
144dg17114 (Mg + lg.1)e8 366 7,11 12 cB L,T
Ω = max
720
27
Lj
TL,
M
with
c9 2 V1760 Mg
Lug
UM,
C8 2 333200 + +2L3))
Ling Pgg
48L2 d2
62 max
4h,, (2 + 1g
+1,
MZD
(226)
324 04
54L2
216
d2
d
Gv max
1080e2
9.11 M
M2
My
12
9.1 c3:
la
cp + Eg11
+
2
Cy
12
pbg
10T
Cn 26Ω,
C>
Cg
Lp
71

---

By adding (223). (222), (224), (143), and (180), along with (209) and considering the fact that at decreases with respect to f, and by applying Lemma D.21, we obtain:
T
Σ
A(as, de Pv)
IIPx,ac (x1; yZ
+A
< 12M + +VV +
Σ
B(a,, Be, Se Pv 11O
+
Clar, Se, Sc, pv) 1()
(227a)
48 16
T
T I(ar, 3e, 8cs Pv) Ellcy 1
+
E(Sr, 6c, pw) (p3 + +22)+ +
(227b)
Mg
1=1
1=1
88? 9222"*
'T
T
T
Σ
S.pp +
46g 9,22
1
(6a;- - a + 2a ElBr, Pv)) Px
(227c)
Lpp
t=1
12 r
48v² r 1i δr
+
+
H2,
M|
(227d)
Lig
3T
+
Q(8r Pv) Blle,
G + Σ ((e (x
(227c)
T
+
Z
(3d]lf.1 + (1207,0 + 66 2gg1p² ))?)
(227f)
t=1
36
36
12 +
18
18 Gx,T
Dy,
+
D T +
Gy.r
G.. +
(227g)
V
Ω
2
22
0
0
T+1
02
62
T
2
+ +2)
1++1
3
By
1+1 + 3(
9x
+
1
(227h)
b
bp
V
hp2
b
Ω
GiL. 2
dzpp
T
+
R(px)TTp: + TT + 12T
+
+
Σ
D(a,, Be, 8,) (p + p.). (227))
9.1
Here,
4L3 r
+ 16v2
T
dw:P) =
(212 + 1)
1upo 3r
I,n 19
2g.1
+ 6(12f f,1 + 962 d2 d1
d2
+ 24d2
)(
+
2p²
A(as, 8r, == 0+ L 2 - 4E(3,, dr, pv)
M1, Pv) = Lin To. + 2M² (6ar 3L +
4
Cla,,3,, pv,))) == L + 26p2
82
13
2
9,1 2
+ 2M/ (6az. - -3L,y + (,),,
dg
dj
Z = 2762 1.1
+
(228)
v
s
72

---

Moreover,
M(6)) == Ae+1 v
+ Z262 + 8T dc.
Lpz
D(at, 01) = 66 + 2 fa ) +
3 fl1.1 (at - (I
Mg
Hg
24 9.1 r
966 9. 11² r
+
+
4u My
Be
L Mg 8t"
P2
+ 2762 n,1
d2
F(px)= =- 24d2
+ (720%
+
1.1
Py
23,
S(Br, = Mg + 9g
+ 88 + 2F (px)))
(229)
Q(3,, = Lyp
2
r
r++1
+ 2F(
&
(2 18d2
36 0.1 d2
R(pv)= = 9dl
9.1
2
f.l
6(3l 1,1 +
2
V
4p2
T
32
of
((px): == lfd7
111
+ 6(3
n.1
Ω
f11
4pp ?
Liars Br, 8c, Pv) == 16+1
+ 4 (6az 3L ja? +
Ω
We then provide bounds for the terms in (227x). Note that, we have
O(, = 4L2 r
16v2
r
+
(2L + 1)
Lng 3r
5n
+ 24d2 9.1
6(12f
962 2p²
d2
f:1
V
Ω
which together with 3, = -caar. 81 = csa, in (31), we have
41 l'a
16v2
Top
+
(21 + 1)
Tite Br
I,,,1
de
2g
276 g.1 a
d2
di
24d2 ot
+ (7262
110 +
22
4442
Mf
a1
832v²
(1 + 21,
M2
a
12
I
1
1
c/
6 d2Le.1 g.!
18
2762
d2
+
f1 a++
+
9.1
a1)
L
Lj
Cv
0t
<
(230)
8"
11M2
r = 52M?
where the first inequality is by r
in (225), 12 = crin and 0r S 1/4L, in (31);
Lpge3 03¹
Luy cs
L3M3
the second inequality follows from cB 2 1 and + 240 doe Ly
1760
C8 2 33280
(1 212)) in (226);
12 3
v 720
720
doe?
Lg Ω 720
die7 b,
and cv 2 1080e2
9.1 ( + # in (225).
Moreover, we have
A(a Br, px) = 04 Lya - -E 8, )
Lya 2 a₁
2 0
2
> at
(231)
4
73

---

where the last inequality is by a - 1 in (226). Bounding (227a). From 5₁ = cso, in (31), we have
To, + 2M3 (6ar- - -L, +2u [ dr, pv))
Bla Br, 8r, pv) -
Tò,
Lus Tcsas 12M3a, -
1-M ,M + M]
04
Tupo Tes Tes +
25
2211 M3 at
2
2 Mznn.
(232)
where the first inequality follows from (230); the last inequality is by Y 52M2 From (228), we obtain
Ing in (225).
d2
di
Z 2762
9.1
v
+
Thus, from 3r = C304, 6c = c804, and 2 = Cuak in (31), we have
rB: Clar. Sc, = Lnn T8r + 162
d2
d1
82
2
y
9. P
+ 2M² (6or - 31 2
+ 2n
F. 8t, Pv))
< Li Tega; + 162(
d2
dp
b
c
at + Mfar
9
v
iy
2
11
d2
d
o
9 2
2 Mfaar + 162(
01
at + Mar
T
1
S Mfar.
(233)
2
11M3
where the first inequality follows from (230); the second equality follows from r the last inequality is by Cv
Iuge0 in (225);
324 M
(
9.
d2
+ a )ej.
Thus, from (232) and (233), we get
(227a) S (Vr).
(234)
Bounding (227b). From (230), we also obtain
4
Σ
Fl3,, po) x2)
1y
t=1
48 f 1
ai (p% + p:)
Ny
t=1
o
Σ
a + p?)
(235)
From (229) and M1t1 c, in (31), we have
L(a,, Sr, Pv) = Th+1
+ 4 (6a, - 3L + E(,,
Ω
< G
ar + 25
Ω
< -a,,
74

---

where the last inequality is by ciyy 2 2612 and (230). Thus, we get
T
Maa, Be, Pv Ellet11 O.
(236)
From (236) and (235), we have
(227b) S 0
Σ Ea + pt)
(237)
Bounding (227c).
From 6; = cja₁ in (31) and Eq. (230), we have
8C 8 T
depy 46
222200
(6a, 3L E(Br, 2
lips
8P 0 T
T
T
25
cscepy + 46
at
aspp.
4
1=1
Thus, from 2 = Cv (31), we have
(227c)
Σ
0f
(238)
Bounding (227d). From (228), we have
d2 + #
Z 27
(239)
From (229), de41 = exas and 6, = c,00, in (31), we have
(6;) = det1
8T
+ =26? +
V
Lin
Cx0t + 276
9.1
d2 dl
2c
+
Ly
8Y
cgat
S 29
27
d2 +
di
cgat +
p2
20gar
Lpg
4L,
9.1
Ω
r
< Lig cgat:
where the first inequality is by CA 2
10T cs v and as S 1/4by; the last inequality follows from
Ipp
M 27 Lyz f2 Th, g.1 d2cs and Ω 2 27 Lpn e d1cs.
Th,
Since 3 Cæa2 and o, = Ca0s in (31), we get
12 r
48 Tr
T
(227d) =
H2r + Σ M(5 E c 2
Lpg
BT
Lng
dr
H2r
<
(240)
Bounding (227e). From (229), we have
1 F(pv) 24dz
2762
d2
d
9.1
(7262
9.1
(241)
+
22
V
Ω
75

---

From (229), 741 = C,a6 3: = cga, in (31), we have
Q(3c,Pu)
7+41
2
-- (F(,))
+
22M
2762
d2
d1
ar +
2Ad2 9.1
+ (726 +
9.1
+
20
14
+
C
!
4M3 O4 +
24d2 9.1 0f. + (728 f,1 + 9.1
12
2702 14
d2
dp
201
12g
Cv
V/
?
4M, ai +
6d2 g.1
276 276 10
d2
d1
at +
22
1,1
)
+
203
Ls +
Ly
y
M
Ci
(242)
Pg
where the first equality is by r
Ep and P Cv the first inequality follows from
11M7
Cy 2 26M57 the second inequality is by at I 1/4by; the last incquality follows from
Po
SAL2,
12d26 L2 o and Z My and 2 d1 d, o3 My
1224, o3
Gv 2 My 12
22 f2
de + 1)).. +
M)
From (229), 3: = cgac, 2e = cva, in (31) and (241), we have
23,
S(Br.pv)
+ +3 + (pv))
Bg + -
20garT
2Ad2 2.1 + (7267, + 2 9.1 )
2762
d2
d1
+ +ezaTt++
+
20
Mg + 1lp11
Cra
V
c
+
24d2
9.l ai + (726)
/ + g. a4
2702
d
20
Mg + fg.1
Gv
n
cgarT
+
6d2 9.1
0t +
18
82
a
27 0t
g.
d
20
M4 + lg.11
L, +b
L,
Cv
c300,
(243)
4(1gg + (g,1)
where the first inequality follows from a₁ S 1/ca(1y + ly,1; the second inequality is by S 1/4Ly; the last inequality is by cv 2
216 22 (dz a ces(Hg + ly,1 and & >
(
(1, (n,
and
T
LeegT
144d2f7, (m. taalog and Ω 144d, e, t2 byT
1,T
Thus, we get
T (227e) = Σ 1E)le01))
T Σ S(e. PB [x s 0. (244)
Bounding (227f)... From (228), we have
dg d1
2 = 2722 2
s
76

---

Thus, from 6, = cja,, in (31), we have
T
(2271) =
Z
(3d2
f.1
0i + (126, + 666 )09)
1=1
T
d2
di
Σ
2762
+
(3d3 + (1267.0 + 66 cjai
9.1
s
1=1
T
= =0
Σ
(d1 + d2) + oz)
(245)
Bounding (227g). From & = cra in (31), we have
36
36
12
36
36
(227g)
Dy.r +
Dx,r +
Gys +
Gv.r +
Gx,7
v
upp
s2pt
1 =Gv,I + Gx.r))
0
DD.T + Dx,I Gy.r+ +
(246)
at
Bounding (227h). From 7(41 = C, M|+1 = C,a A441 = c2a, and p Cya, in (31), we have
(227h) = 2
T
1++1
02
9v
3
0
by
T+1
X2
3
0x
0
22
T
7+
+
bp
b
hp
Ω
1=1
1=1
1=1
2
T
0
02
4y
3
02
4y
0²
T+1
2 2
+
3
02
9x
1x)
T
0
+
b
bp2
b
V
bp
b
Ω
1=1
1=1
t=1
0
0
By
62
By
07 Jy
22
1x
Σ
(247)
bog
boi
Bounding (2271). From 3r- = c30 8, = cgas in (31), we have
fal
36 (aa- - Ly(a) + 24 T
966g, T
D(ar: 3r, 0,) = flf,1 (1 + 2
+
+
Mg
Fg
Lipa ug Br
1ng 313 5r
f g.1
3 361,1 g.1 (a: Lyaz)= + 24l r
966 g. 122 T
=6 +2
+
+
Lig My CBefe
Luguu csa
o
at
+
a1
and
T Σ D(a,, 61) (e + +x)) 0 -=²==0
T
(ai + 1 (et + 02)
Σ
(248)
at
[=1
Moreover, we have
1 R(pw) = 9dg
+
18
f.1
+ 6(36,
+
32
n.
&
= 0
(1
1
)dg
$
V
42
v
Pr
k((p)) 18d f11
2
6(36,
3/2 4p
df
0
(1
1
)dt
Ω
which, implies that
Tie
+ 18d2.2 Tp
) + ((P))T + 18
n.1 2pp2
9.1 Tip
=o (1
1 yTuu
+ (5
T
CdEppt + di
(249)
22
2
77

---

From (248), (249) and p CyCs in (31), we get
T
(227i) S o
Σ
on
1 + (1 0T
yT + +
(250)
04
Combining the outcomes (22 Combining inequalities (234), (237), (238), (240), (244), (245), (246), (247), and (250) leads to
T
QT
Px,a, (xi;
+A
2
1=1
T
T
H₂f
0
VT
Σ
(1 + p
+
(di ddd+f
QT
t=1
t=1
t=1
+0
Dy.r + Dx,T + Gy,T
+
(Gv, + Gx.T))
0T
0 oi
8² o a1
0 by
02 04
02 ai
+0
Σ
+
1x
b
T
+
Σ
(a
+
(0e + --)) + (1
TTulpp + d&p
04
aT
From the definition of A in (105), we have
r
- r
(B[0)) 11)
T
+ Y
[B[Oy] - B[0 .I) +
[B||e]1' El|e4+111 11²)
+
t=1
+
1
(E|lc 1 E 113)
1
EBlee 1|
Elle/ 11²)
Ω t=1
1=1
62
02
+
G2
0
<
Toy rØY
fly
Byy
+
Bay
(251)
+
V
Ω
From (28), we have 0² = 82_ + 02
+
+
+
62
02
Dxy
fx'
Thus, using (251), (31), and rearranging the terms, we get
T
Σ
E
||Px, (x:; yx
1=1
T
2
H2,r
0
VT +
Σ 1=1
arlo' + + + Σ
at
2
+
Σ
(di +dd + at)
OT
oT
t=1
t=l
2 0
1 _(G,T + Gx.T)
Dy.T + Dx.T
Gy.T
aT
aT
2
gy
a
a
32 at
Sy
82
oT
b
b
Σ
T
(at +
1
1
(ez + +2) + (1+
1
yT + Gip))
at.
QT
2
0 000 + 0 + 6²)
< 0 ((4 + dz) 3/44/ /3 (V1 + Dy.r + Dx + Gy.r + A1 + +
+(d1 + dz) 3/23/22//3 (Har + GV, + Gx.T)
(252)
78

---

where second inequality holds because we have
log 1)
Σ
(d1 +
(2+))
(d1 + d2) 9//4 +t)
(d1 + d2)
T
T
T1/3
Σ
2
Σ
(d) + /2) 1)2/3 S
(d1 + d2) (c+ 1)2/3
(d) + d2)
1=1
1=1
Σ
T
1
372/3
0
(d1 + d2) 33/4( + t) $
(d1 + 32) + +t/l33
2(d1 3/44
1=1
1=
1=1
Σ
(di
(c) +t1/83 -
(d + d2) 32)3/114133
04
Then, note that, we have
E
[Px (x: Vfxxx (xx)))) [
2
E
||xxxa (xy: (x,
T
Σ
E [Pxxa (x: (x(x - Px,,, (x4: Vxt, (xx))))
From non-expansiveness of the projection operator and Lemma D.4, we have
Px (x,; y? Px,a. (x,; xx
fe yi (xx))
xxxx)(x
(padi + prd2)
4 (R + ded))e
This implies
T
E Px (xi: VXX
2 (=1
T( pFd
<
Σ
E |Pxx. (xe Xx
+
Applying the upper bound in (252) yields
E
Px (x:; XZ
1=1
O
(d1 + dz) 3/4///33
(Vr Dy.r Dx,TT Gy.r Ai + 0²)
+(d1 + dz) 2/2 (H2T + GV.T + +xxT))
T(gdd + p2.
+
79

---

Thus, from p =
1
and P
1
in (31), we get
det
r
Σ
E
Px (xri VX
1=1
s 0 (d] + d2) d2)3//111/2 (Vr + Dy.r + Dx,T + Gy.r + A +
+(d + d2)3 (H2 + Gv. + Gx.)).
This completes the proof.
E Hyperparameter Tuning Results
As detailed in Section 4, we carefully tuned all hyperparameters to ensure stable and fair comparisons. Our analysis indicates that while ZO-SOGD exhibits sensitivity hyperparameter choices, it remains robust within reasonable ranges. Below, we provide extensive tuning results for ZO-SOGD.
The hyperparameter sensitivity analysis for the adversarial attack scenario reveals critical insights about the algorithm's attack effectiveness across different parameter configurations. For the inner and outer stepsizes, observe that the algorithm achieves optimal attack performance with specific combinations that balance perturbation strength and imperceptibility.
Table 2: Hyperparameter tuning results for inner (3) and outer (a) stepsizes in adversarial attack scenario. Values represent test accuracy (mean + std) over 5 runs. Lower values indicate better attack performance.
aa
= 0.001
= 0.005
= 0.01
= 0.1
0.001
0.68 + 0.05
0.59 + 0.07
0.47
0.06
0.53 +|2 0.08
G 0.005
0.54 0.06
0.41 0.05
0.35 0.04
0.42 + 0.05
8 = 0.01
0.48 + 0.04
0.34 + 0.05
0.57 + 0.07
0.39 + 0.06
3 0.1
0.26 + 0.03
0.43 + 0.06
0.33 + 0.04 0.45 = 0.07
The stepsize analysis reveals that larger inner stepsizes combined with smaller outer stepsizes tend to produce more effective attacks. Specifically, the configuration with = 0.1 and a 0.001 achieves the lowest test accuracy of 0.26 + 0.03, indicating the most successful adversarial perturbations. This pattern suggests that aggressive updates to the perturbation parameters (5) while maintaining conservative byperparameter updates (a) creates an effective balance for generating strong yet imperceptible adversarial examples.
Table 3: Performance comparison across different smoothing parameters (pr ps) in adversarial attack scenario.
Po Ar Ps
0.001
0.005
0.01
0.05
Pv 0.001
0.61 0.06
0.52 0.05
0.48 0.04
0.57 0.06
P: = 0.005
0.47 0.05
0.39 0.04
0.35 0.04
0.45 + 0.05
Pe = 0.01
0.41 + 0.04
0.28 + 0.03
0.31 + 0.03
0.43 + 0.05
Pv 0.05
0.53 + 0.06
0.44 + 0.05
0.40 + 0.04
0.52 + 0.06
The smoothing parameter analysis provides additional insights into the algorithm's convergence behavior in the adversarial setting. The optimal configuration occurs with P. 0.01 and p, Pa = 0.005, achieving a test accuracy of 0.28 0.03. These moderate smoothing values appear to provide the right balance between exploration and exploitation in the adversarial perturbation space, allowing the algorithm to find effective attack directions without excessive oscillation or premature convergence.
80

---

Table 4: Performance comparison across different momentum parameters in adversarial attack scenario.
Yt A =
0.9
0.99
0.999
7t 0.9
0.35 + 0.04
0.29 + 0.03
0.38 + 0.05
>/ 0.99
0.31 0.03
0.24
0.02
0.33 + 0.04
7t 0.999
0.37 + 0.04
0.32 + 0.08
0.40 + 0.05
The momentum parameter investigation reveals that moderate momentum values consistently produce the most effective adversarial attacks. The optimal configuration with "/ 0.99 and X = 7); = 0.99 achieves the lowest test accuracy of 0.24 + 0.02, representing the successful attack performance. This configuration suggests that maintaining momentum across both inner and outer optimization loops helps the algorithm navigate the complex adversarial landscape effectively than either momentum or excessive momentum settings.
The comprehensive analysis demonstrates that ZO-SOGD maintains robust attack performance across a broad range of hyperparameter configurations. The algorithm consistently achieves test accuracies below 0.5 across most reasonable parameter combinations, indicating reliable adversarial attack capability. The standard deviations remain low throughout the parameter space, suggesting stable and reproducible attack performance across multiple experimental runs.
The optimal hyperparameter configuration for adversarial attacks consists of inner stepsize 0.1, outer stepsize 0.001, smoothing parameters P. = 0.01 and Pr Ps 0.005, and momentum parameters "t- = X = 7) = 0.99. This configuration enables ZO-SOGD to achieve superior attack performance while maintaining the imperceptibility constraints essential for practical adversarial examples.
81

---

NeurIPS Paper Checklist
A. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide detailed proof's and implementations of the algorithms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
B. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are provided in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
C. 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]
82

---

Justification:
Please refer to Theorems 2.6 and 3.2.
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 complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
D. 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: It is provided in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution 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) 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.
E. 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?
83

---

Answer: [Yes]
Justification:
The data is publicly available. For experimental results, please refer to Section
and the supplement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips. ec/
ceeiionooliiiooo liyy 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 open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ wewiii/ggidee/ooooo
seissssiiccyyyy for more details.
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.
F. Experimental setting/details
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?
Question:
Answer: [Yes]
Justification: For experimental results, please refer to Section and the supplement. 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.
G. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Section 4 and the supplement.
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).
84

---

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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
H. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: All experiments were conducted on the same system and are easily reproducible standard personal computer.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
I. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:/ http///eeuripp.eeeee htcp/plliii/thhccuiii.iioooo
Question:
Answer: [Yes]
Justification:
The authors reviewed the NeurlPS Code 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).
J. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
Theory Paper.
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.
85

---

The conference expects that many papers will be foundational research and not tied 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
K. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
Theory Paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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.
L. Lieenses 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: The authors cite the original paper that produced the code package dataset.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset 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 (c.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 package should be provided. For popular datasets, paperswi thcode. com com/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.
86

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
M. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA].
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
N. Crowdsoureing 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: Theory paper.
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 the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
O. Institutional review board (IRB) approvals or equivalent for research with human subjects
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?
Question:
Answer: [NA].
Justification:
Paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 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 the institution conducting the review.
P. Declaration of LLM usage
87

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]-
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ http://eeeuuuueeeeeee httpp/rrppsccooooeeeeeeeeeeeeeee wctp///ooneeencc//22////11/ for what should or should be described.
88


Reviews:
[{"review_id": "toxuDFzzLJ", "reviewer": "Reviewer_ETap", "summary": "The paper presents a unified first-order (SOGD) and zeroth-order (ZO-SOGD) framework for online bilevel optimization (OBO) that achieves sub-linear stochastic bilevel local regret without any window smoothing. Key ingredients are 1) momentum-type projected search direction that simultaneously updates leader, follower, and auxiliary variables in a single loop, 2) oracle-efficient hyper-gradient estimation that needs only one inner linear-system step per round, and 3) a fully function-value–only variant that estimates gradients, Hessians, and Jacobians via two-point finite differences.\n\nTheoretical contributions include tight $O(T^{1/3})$ (first-order) and $O((d_1+d_2)^{3/4}T^{1/3})$ (zeroth-order) regret bounds under standard non-convex/strongly-convex assumptions. Empirical studies on online adversarial attacks and parametric loss tuning under distribution shift confirm the framework’s practical gains over state-of-the-art OBO and single-level baselines.", "questions": "1) Could you make a GitHub or submit your codes and experiments for the sake of reproducibility of your result?\n\n2) Could you elaborate on concrete scenarios where the proposed bilevel local regret better captures performance than traditional window-smoothed metrics? Have you identified tasks where the two measures give conflicting evaluations?\n\n3) The theoretical analysis uses order-$T^{-1/3}$ step sizes. In the experiments I suppose you tune them heuristically, did you observe a clear regime where the theory-suggested schedule outperforms alternative decays (e.g., $T^{-1/2}$)?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) Removing the window-smoothed regret requirement is a clear conceptual advance.\n2) Proofs carefully track stochastic variance, path-length, and gradient-drift terms and tighten the noise dependence to $T^{-2/3}$ which is sharper than the $T^{-1/2}$ factor in SOBBO/SOBOW. \n3) Experiments show ZO-SOGD consistently outperforms strong black-box attack optimizers (ZO-O-Adam, SignSGD, etc.) in success rate and perturbation norm while maintaining reasonable run-time, and SOGD matches or exceeds OAGD / SOBOW on adaptive loss tuning with lower latency.\nWeaknesses: The code for the experiments is not provided in the supplementary material. It must be required for reproducibility.", "was_revised": true, "final_justification": "The author’s reply resolves my concerns; I’m keeping my current rating. However, the proofs read quite densely and could be clarified with revisions. Compared with other bilevel optimization papers I’ve read, I had more difficulty following these arguments.", "rebuttal": "We sincerely thank Reviewer ETap for the valuable and constructive feedback. We address each point below.\n\n**Question 1: Could you make a GitHub or submit your codes and experiments for the sake of reproducibility of your result?**\n\n**Response:** Thank you for raising this important point. We fully agree on the importance of reproducibility. To that end, we contacted the Area Chairs to inquire whether we could share an anonymous code link during the rebuttal phase and received the following guidance:\n\n> \"Because of known concerns on identity leakage, we are prohibited using any links in the rebuttal, including, but not limited to anonymous or non-anonymous URL links, or updating your submitted GitHub repository.\"\n\nAccordingly, while we are currently unable to share the code during the rebuttal phase, we will release the complete codebase upon acceptance to facilitate full reproducibility of our results.\n\n---\n\n**Question 2: Could you elaborate on concrete scenarios where the proposed bilevel local regret better captures performance than traditional window-smoothed metrics? Have you identified tasks where the two measures give conflicting evaluations?**\n\n**Response:**  We thank the reviewer for this insightful question. While the bilevel local regret values themselves may not always show dramatic differences between window-smoothed and non-smoothed approaches, the key distinction lies in the underlying algorithmic mechanisms and their real-world performance. Our contribution is not just the regret metric, but the first and zeroth order novel recursive momentum-type search directions (Eq. 6) that fundamentally differs from window-smoothed gradient methods used in prior work.\n\nTraditional OBO methods like OAGD, SOBOW, and SOBBO all rely on window-smoothed search directions of the form:\n\n$$\n\\nabla F_{t,w}(x,y) = \\frac{1}{w}\\sum_{i=0}^{w-1} \\nabla f_{t-i}(x,y),\n$$\n\nwhich inherently averages past gradients. This averaging introduces lag and can lead to conflicting gradient directions when objectives change rapidly. In contrast, our recursive momentum approach\n\n$$\nd^x_t = \\eta\\nabla f_t(x_t, y_t) + (1-\\eta)d^x_{t-1} + (1-\\eta)(\\nabla f_t(x_t, y_t) - \\nabla f_t(x_{t-1}, y_{t-1}))\n$$\n\nmaintains a single adaptive direction that immediately responds to changes while preserving useful historical information through the momentum term.\n\n*Experiment: Periodic Objective Oscillations:* Following your valuable suggestion, we evaluate a synthetic scenario where the leader's objective exhibits oscillations with frequency parameter $c$:\n$$\nf_t(x,y) = (1 + \\sin(ct)) \\cdot \\|x - y^*_t(x)\\|^2 + \\cos(2ct) \\cdot \\|x\\|^2\n$$\n$$\ng_t(x,y) = \\|y - (\\cos(x) + 0.5\\sin(ct))\\|^2\n$$\n\n**Table 1: Gradient-based Regret Under Different Change Frequencies**\n\n| Method             | Time (s) | Our Regret |  Smoothed Regret |\n|--------------------|----------|-------------------------------|-----------------------------------|\n| *For $c = 0.1$ (Slow changes)* |          |                               |                                   |\n| OAGD ($w = 20$)     | 45.2     | **498.0**                         | **485.3**                             |\n| SOBOW ($w = 10$)    | 68.4     | 542.6                         | 521.8                             |\n| SOGD ($w = 1$)      | **22.6** | 596.9                     | 596.9                         |\n| *For $c = 5$ (Rapid changes)* |          |                               |                                   |\n| OAGD ($w = 20$)     | 52.3     | 1842.7                        | **127.5**                          |\n| SOBOW ($w = 10$)    | 75.8     | 1205.3                        | 186.2                             |\n| SOGD ($w = 1$)      | **24.9** | **758.4**                     | 758.4                         |\n\n\nIn rapidly changing environments ($c = 5$), OBO   [[Tarzanagh et al., (2022)](https://proceedings.mlr.press/v238/ataee-tarzanagh24a/ataee-tarzanagh24a.pdf)]  with smoothing regret ($\\sum_{t=1}^T ||\\nabla F_{t,w}||$) shows extremely low window-smoothed regret (127.5) because opposing gradients cancel out when averaged, suggesting near-optimal performance. However, its local regret (1842.7) reveals it's actually performing poorly—the algorithm is stuck between conflicting directions.\n\nThis demonstrates why window-smoothed metrics can be fundamentally misleading: they evaluate performance against averaged gradients that may not represent any actual objective the algorithm needs to track. Our local regret correctly captures that SOGD (758.4) significantly outperforms window-based methods in dynamic environments.\n\n\n---\n\n**Question 3: The theoretical analysis uses $O(T^{-2/3})$ step sizes. In the experiments I suppose you tune them heuristically, did you observe a clear regime where the theory-suggested schedule outperforms alternative decays (e.g., $T^{-1/2}$)?**\n\n**Response:** We appreciate the reviewer's careful observation. From Theorem 2.6, we use $\\alpha_t = 1/((c_1 + t)^{1/3})$ and $\\beta_t = c_\\beta \\alpha_t$. For the zeroth-order case in Theorem 3.2, we have $\\alpha_t = 1/((d_1 + d_2)^{3/4}(c_1+ t)^{1/3})$, with similar scaling for the other parameters. These $O(t^{-1/3})$ schedules are derived to balance the bias-variance trade-off in our stochastic bilevel setting and to achieve the $O(T^{1/3})$ regret bound.\n\nWhile it is difficult to validate this theory in our real-world  highly nonconvex experiments--and we heuristically tuned the parameters--we can demonstrate its advantages in synthetic settings. To validate our theoretical step size schedule, we conducted experiments using the periodic objective oscillation scenario from our response to Question 2. \n\n**Table 2: Step Size Schedule Comparison on Periodic Objectives**\n\n| Step Size Schedule                 | Our Regret ($c = 0.1$) | Our Regret ($c = 5$) |\n|-----------------------------------|---------------------|------------------|\n| $\\alpha_t = 0.001$ (Fixed)         | 396.6               | 892.4            |\n| $\\alpha_t \\propto t^{-1/2}$       | **325.5**               | 850.6            |\n| $\\alpha_t \\propto t^{-1/3}$ (Theory) | 596.9         | **758.4**        |\n\nThe faster $O(t^{-1/2})$ decay proves too aggressive for our bilevel setting, especially in rapidly changing environments. This schedule reduces the step size too quickly, preventing the algorithm from adapting to sudden changes in the bilevel landscape. \n\nThe advantage of our theoretical schedule becomes particularly pronounced in environments with rapid changes. When the oscillation frequency is high ($c = 5$), the performance gap widens dramatically: the $O(t^{-1/3})$ schedule achieves a regret of 758.4, while the $O(t^{-1/2})$ schedule yields 850.6. Conversely, in smoother settings with $c = 0.1$, the performance difference narrows (596.9 vs. 325.6), as rapid adaptation is less critical. \n\nWe emphasize that our approach significantly reduces computation time and memory usage, as we do not use window smoothing. Please refer to **Table 1**."}, {"review_id": "bJ5oXUY5XT", "reviewer": "Reviewer_LBrC", "summary": "This paper studies the online bilevel optimization problem with stochastic and zero-order feedback. It proposes a new performance measure for OBO that avoids the need for window-smoothed objectives, as used in prior work. The paper then presents algorithms for both the stochastic and zero-order feedback settings, providing theoretical guarantees under the proposed performance metric. Experiments on black-box attacks and loss tunning are conducted to demonstrate the effectiveness of the proposed methods.", "questions": "**Questions:**\n\n1. Could you provide additional justification for the proposed performance measure?\n2. Could you offer a more detailed discussion on the tightness of the proposed regret bounds?\n3. In the experiments, what is the benefit of applying an algorithm designed for time-varying objectives instead of treating the data as stochastic samples from a fixed distribution?", "limitations": "NA", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n* The proposed performance measure eliminates the need for smoothing used in previous works, making it more suitable for scenarios where the objective function changes over time.\n* Experiments are conducted to empirically validate the effectiveness of the proposed algorithms.\n\n\n**Weaknesses:**\n\n* **Clarity of the performance measure:**\nThe notation for $f_t$ and $g_t$ is somewhat confusing to me, as it appears these notations are used to denote both expected and individual functions in (1), leading to ambiguity in understanding the performance measure. If $f_t$ represents the expected function, it is unclear to me over what randomness the expectation in equation (2a) is taken. On the other hand, if $f_t$ denotes the individual realization, it seems that BL-Regret cannot reach zero even with optimal predictions at each iteration. Additionally, the BL-Regret depends on $\\alpha_t$, which is a parameter of the algorithm itself. It is not clear what is an appropriate choice of $\\alpha_t$ for evaluating different methods, or how to fairly compare regret across methods using different $\\alpha_t$ schedules.\n\n* **Theorem 2.6 and Theorem 3.2:**\nThe regret bounds presented appear superlinear in the worst case, as $\\Delta_T$ can be as large as $\\mathcal{O}(T)$. In such scenarios, the guarantees become worse than the trivial $\\mathcal{O}(T)$ regret that one could achieve simply by choosing arbitrary predictions within a compact set $X$.\n\n* **Claims about convergence rates:**\nIn line 161, the authors claim the proposed method surpasses the $\\mathcal{O}(T^{-1/2}\\sigma^2)$ rate for online stochastic optimization (OSO). However, this argument is unclear because the bound still depends on $\\Delta_T$, which in the worst case can grow as $\\mathcal{O}(T)$, resulting in a convergence rate worse than $\\mathcal{O}(1)$. The same concern applies to the claim made at line 212.\n\n* **Experiments:**\nAlthough the paper focuses on OBO with time-varying $f_t$ and $g_t$, the two experimental cases studied appear essentially to be offline learning problems, where it is unclear why modeling time-varying objectives is necessary. Even if the validation datasets $\\mathcal{D}_t^{val}$ and training datasets $\\mathcal{D}_t^{tr}$ vary, in the offline setting it would be more natural to assume they are drawn from the same fixed distribution rather than a time-varying distribution.", "was_revised": true, "final_justification": "One of my concerns about the paper lies in the theoretical guarantee, specifically the $O(T\\^{1/3}\\Delta\\_T + T\\^{2/3}\\Psi\\_T)$ dynamic regret bound (Theorem 2.6). This bound implies that the dynamic regret is sublinear only when $\\Delta\\_T = o(T^{2/3})$ and $\\Psi_T = o(T\\^{1/3})$. In the worst case, the bound becomes superlinear at a rate of $O(T^{5/3})$. By contrast, the algorithms in Table 1 achieve at worst $O(T)$ dynamic regret bound (though the performance measure is slightly different). Since no lower bound is provided, it is unclear whether this gap is due to the inherent hardness of the problem or the suboptimality of the proposed algorithm. \n\nThat said, I acknowledge that the paper introduces an interesting approach by avoiding window smoothing, and my concerns regarding the experimental results have been adequately addressed. Therefore, I am willing to raise my score to 4. \n\nIn the revision, I encourage the authors to provide a more comprehensive discussion of their results. For example, in Remark 2.7, it would be helpful to clearly specify the conditions under which the regret is sublinear, identify the scenarios in which the proposed bound is tighter than existing approaches, and discuss its limitations in the worst-case setting.", "rebuttal": "We thank Reviewer LBrC for the detailed feedback. \n\n**Q1: Additional justification for proposed performance measure?**\n**Weakness 1- Clarity of the performance measure: - The notation for $f_t$ and $g_t$ ... iteration.**\n\n**Response:**  Thank you for your comment. We use $f_t(x,y;\\xi_t)$ and $g_t(x,y;\\zeta_t)$ to denote individual stochastic realizations, while the expected functions are defined as: $f_t(x,y) := E_{\\xi_t  \\sim D_f} \\quad [f_t(x,y;\\xi_t)]$ and $g_t(x,y) := E_{\\zeta_t \\sim D_g}\\quad [g_t(x,y;\\zeta_t)]$,as introduced in Equation (1).\n\nThe key insight is that $x_t$ represents the output of a stochastic bilevel optimization algorithm at iteration $t$ (detailed in Section 2). As such, $x_t$ is a random variable that depends on all stochastic information observed by the algorithm up to time $t-1$, including the random samples used in the estimation of (implicit) gradients and Hessians in earlier iterations.\n\nOur bilevel regret is defined in Equation (2a) as $BL-Reg_T := \\sum_{t=1}^T E [||P_{X,\\alpha_t}(x_t; \\nabla f_t(x_t, y^*_t(x_t)))||^2]$, where the gradient of the expected function $f_t$ is evaluated at the random point $x_t$. Although $f_t$ is an expected function (not a random sample), its gradient becomes a random quantity due to its dependence on $x_t$, which is itself random.\n\nThe outer expectation $E[\\cdot]$ in our regret is over all randomness in the algorithm up to time $t$, including sampled gradients and Hessians (see Algorithms 1 and 2). Regret thus measures the expected stationarity gap, with bounds given in Theorems 2.6 and 3.2.\n\n---\n\n**Q1: Additional justification for proposed performance measure?**\n**Weakness 1- Clarity of the performance ... BL-Regret depends on $\\alpha_t$, ...  schedules.**\n\n**Response:** Thank you for your comment. This dependency is standard in the analysis of online algorithms involving projected gradient descent. We refer the reviewer to Definitions 2.2 and 2.5 in the seminal work of [[Hazan, 2017](https://proceedings.mlr.press/v70/hazan17a/hazan17a.pdf)], where the regret for projected gradient descent is defined as:\n$$\nRegret_T = \\sum_{t=1}^T ||\\frac{1}{\\eta_t}(x_t-x_{t+1})||^2,\n$$\nwith updates\n$$\nx_{t+1} = \\Pi_{\\mathcal{K}}[x_t - \\eta_t \\nabla F_{t,w}(x_t)],\n$$\nwhere \n$$ F_{t,w}(x_t)=\\frac{1}{w}\\sum_{i=0}^{w-1}f_{t-i}(x_t).$$\n\nTheir Proposition 2.3 shows projected gradient is a continuous mapping, so Brouwer’s fixed point theorem guarantees at least one fixed point where projected gradient (and thus average regret) vanishes. Definition 2.5 also shows single-level regret depends on stepsize, as does our bilevel regret on $\\alpha_t$. Our analysis extends these results to the bilevel case.\nIt is important to contextualize our regret relative to prior OBO work. Previous OBO methods in Table 1 (e.g. OAGD and SOBOW) address the unconstrained case ($\\mathcal{X} = \\mathbb{R}^{d_1}$), where the projection operator becomes the identity. Thus, our bilevel regret definition (Eq. 2b) simplifies to\n$$\nBL-Reg_T = \\sum^T_{t=1} E [||\\nabla f_t(x_t, y^*_t(x_t))||^2],\n$$\nwhich is independent of $\\alpha_t$ and matches the regret definitions used by OAGD and SOBOW. Our work extends OBO to the **constrained** setting and establishes an improved $O(T^{1/3})$ bound. The stepsize $\\alpha_t = 1/(c+t)^{1/3}$ in Theorem 2.6 (Eq. 15) ensures convergence and is standard in non-convex online optimization.\n\nFor fair experimental comparison (Section 4):  \n(1) In unconstrained settings, all methods use plain gradient descent, so regret is independent of $\\alpha_t$;  \n(2) In constrained settings, all use the same projection and tune $\\alpha \\in {0.0001, 0.0005, 0.001, 0.005, 0.01}$.\n\n---\n\n**Q2: Detailed discussion on tightness of regret bounds?**\n**Weakness 2- Theorem 2.6 and Theorem 3.2: The regret bounds presented appear superlinear  ...  a compact set $X$.**\n\n**Response:**  Thank you for your comment.   It is widely recognized that it is impossible to achieve dynamic regret in general. For example,  [[Zhang et al. (2018)](https://proceedings.neurips.cc/paper/2018/file/10a5ab2db37feedfdeaab192ead4ac0e-Paper.pdf)], on Page 3, Section 2.2 states: *\"While **it is impossible to achieve a sublinear dynamic regret in general**, we can bound the dynamic regret in terms of certain regularity of the comparator sequence or the function sequence.\"*\n\nThe condition $\\Delta_T = o(T)$ is standard in OBO literature [[Tarzanagh et al., (2022)](https://proceedings.mlr.press/v238/ataee-tarzanagh24a/ataee-tarzanagh24a.pdf)] and online  single-level optimization [[Besbes et al., (2015)](https://arxiv.org/pdf/1307.5449)].\n\n\nEven with $\\Delta_T = O(T)$, our bound scales as $O(T^{4/3})$ compared to window-smoothed methods requiring $w = \\sqrt{T}$, which give $O(T^{3/2})$ regret; albeit neither regret is usable as they are not sublinear.\n\nWhen $V_T = c T$ for some $c > 0$, the number of objective functions $f_t$ differing from previous ones can scale linearly with $T$, making good performance impossible—information from $f_1$ to $f_{t-1}$ is uninformative for $f_t$. $\\Delta_T$ consists of $E_1$ and $V_T$. We assume $\\|y_1 - y_1^*\\| \\leq D$ for $E_1$, and provide examples where $V_T = o(T)$ in many online settings.\n\n**Example 1:**  \nConsider $f_t(x) = \\|A_t x - b_t\\|^2$, where  \n$A_t = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 + 1/t \\end{bmatrix}$, $x = b_t = (1,1)$.  \nThen,\n$$\nV_T := \\sum_{t=2}^T \\max_x |f_t(x) - f_{t-1}(x)| = \\sum_{t=2}^T |(1/t)^2 - (1/(t-1))^2| .\n$$\nBy $a^2 - b^2 = (a-b)(a+b)$,\n$$\nV_T = \\sum_{t=2}^T |(1/t - 1/(t-1))(1/t + 1/(t-1))| = \\sum_{t=2}^T |2/(t(t-1)^2)| .\n$$\nThen,\n$V_T \\leq \\sum_{t=2}^T 2/t^3 \\approx \\int_{2}^T 2/t^3 dt = 1/4 - 1/T^2.$  \nAs $T \\to \\infty$, $V_T$ approaches a constant, i.e., grows slower than $T$.\n\nMoreover, if $A_t = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 + 1/\\log t \\end{bmatrix}$, then\n$$\nV_T = \\sum_{t=3}^T |(1/\\log t)^2 - (1/\\log (t-1))^2| = \\sum_{t=3}^T |1/\\log t - 1/\\log (t-1)| (1/\\log t + 1/\\log (t-1)) .\n$$\nSince $1/\\log t - 1/\\log (t-1) \\approx -1/(t (\\log t)^2)$, we have $V_T = \\sum_{t=3}^T 1/(t (\\log t)^3) = O(\\log T)$.\n\n\n**Example 2:** \nLet $x \\in [-1,1]$, $y \\in \\mathbb{R}$, and define\n$$\nf_t(x, y) = \\frac{1}{2} (x + 2 a_t^{(1)})^2 + \\frac{1}{2} (y - a_t^{(2)})^2,\n$$\n$$\ng_t(x, y) = \\frac{1}{2} y^2 - (x - a_t^{(2)}) y,\n$$\nwhere $a_t^{(1)} = 1/t$ and $a_t^{(2)} = 1/\\sqrt{t}$.  \nThen $y_t^{\\star}(x) = x - a_t^{(2)}$ and by bounding term by term one finds\n$$\nV_T = O(1).\n$$\n\nIn summary, when the variations decay faster than $1/t$, we obtain $V_T = o(T)$. If the decay is like $1/\\sqrt{t}$, then $V_T = O(\\sqrt{T})$.\n\n---\n\n**Weakness 3- Claims about convergence rates:.... same concern applies to the claim made at line 212.**\n\n**Response:** We appreciate the reviewer’s comment. \n\nAs discussed in response to **Weakness 2** and Remark 2.7, and as shown in Theorems 3.1 and 4.2 of  [[Hallak et al., 2021](https://openreview.net/forum?id=XkXb99Eeg6G)], dynamic regret bounds in single-level online optimization include a regularity term (e.g., $V_T$ or $C_T$) that quantifies the temporal variation of the cost functions. The rate $\\mathcal{O}(T^{-1/2} \\sigma^2)$  is meaningful only when this regularity term is sublinear; please also see [[Aydore et al., 2019](https://openreview.net/forum?id=HJxWTNrg8B)] and [[Zhang et al., 2020](https://openreview.net/forum?id=Z_8hoytvdi)]\n\nSpecifically, our method's regularity term $\\Delta_T$ is analogous to those terms in prior work, but the key difference is that our dependence on $T$ and $\\sigma$ yields strictly better dependence than that of previous methods when $\\Delta_T$ grows slowly. For example, in Theorems 3.1 and 4.2 of [[Hallak et al., 2021](https://openreview.net/forum?id=XkXb99Eeg6G)], the stochastic component appears as $O(T \\sigma^2/w^2)$ alongside regularity terms. Hence, their bound also depends on a regularity term, and it is commonly assumed that this term is sublinear in order to achieve a sublinear regret.\n\n\nSimilarly, in the bilevel setting ( please refer to Table 1), all existing methods incorporate regularity terms such as $V_T$, $H_{p,T}$, or $\\Delta_T$ in the regret bounds. These methods (e.g., OAGD, SOBOW, SOBBO) yield regret bounds like $T/w + V_T + H_{2,T}$ or \n$(T/w) \\sigma^2 + V_T + H_{2,T}$, with $w = o(T)$; please see [[Ataee Tarzanagh et al., 2024](https://openreview.net/forum?id=dzmWT2UWMD)] and [[Lin et al., 2024](https://openreview.net/forum?id=Xx1_bVkiuZ)]. In contrast, our approach features a $\\sigma^2$ term that is multiplied by a factor strictly better in $T$ than previous methods, which often incur a  $\\mathcal{O}(T^{-1/2})$  due to window averaging; please refer to Table 1.\n\n---\n\n**Q3: Benefit of time-varying ... from fixed distribution?**\n**Weakness 4- Experiments: Although the paper .. .a time-varying distribution.**\n\n**Response:** We respectfully disagree with the characterization of our experiments as \"essentially offline learning problems.\" Both experimental settings are genuinely online with time-varying objectives. For example, in the adversarial attack setting (Section 4), the optimal attack strategy changes abruptly between stages (see Eq. (28)), reflecting dynamic defenses in real-world scenarios. These are not i.i.d. samples, but represent structural shifts requiring online adaptation of hyperparameters $x^*_s$. This setting is well-established in the online learning literature, where distribution shifts are a central motivation for online algorithms [[Hall and Willett, 2015]](https://arxiv.org/pdf/1307.5944).\n\nOur method is also well-suited for online meta-learning (OML), where agents must quickly adapt to sequential tasks; please see Section 4.3 in [[Ataee Tarzanagh et al., 2024](https://openreview.net/forum?id=dzmWT2UWMD)] for discussion on OBO for OML. For additional applications, including traffic flow prediction and wireless network control, please refer to Appendix A in [[Lin et al., 2024](https://openreview.net/forum?id=Xx1_bVkiuZ)]."}, {"review_id": "iFhWSbcEBD", "reviewer": "Reviewer_yzQD", "summary": "This paper studies online bilevel optimization using both first-order and zeroth-order oracles. It achieves stochastic sublinear regret without relying on window smoothing, leveraging novel search directions. In the zeroth-order setting, hypergradient estimation is performed using only function values. The effectiveness of the proposed algorithm is demonstrated through numerical experiments.", "questions": "1) What is the purpose of Lemma 2.1? It appears to be a direct application of the exponential moving average (EMA) and may not require a separate lemma.  \n\n2) In theorem 2.6, what can be said about the optimality of the regret bound with respect to the time horizon $T$? Which specific factor is responsible for the improvement over OSO? \n\n3) Is the dimensional dependence in the zeroth order setting optimal ? In theorem 3.2, Line 200, the dimensional dependence seems to be $O(d_1+d_2)^{3/2}$ but in Remark 3.3, this is reported as $O(d_1+d_2)$. Which statement is correct?", "limitations": "The discussion of limitation is rather superficial. For example, there are many more natural questions that are left open after reading this paper. Are the regret bounds optimal? If not, what are the lower bounds for regret in each problem setting?", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: \n\n- Unlike prior approaches, the proposed algorithms do not rely on window smoothing, thereby avoiding the significant computational overhead associated with evaluating multiple past gradients at each iteration. This makes the method more scalable and better suited for real-time or large-scale applications. \n\n- In previous works, hypergradient estimation typically requires multiple iterations of the inner objective. In contrast, this paper achieves hypergradient estimation using a single subproblem iteration. \n\n- In the zeroth-order setting, the algorithm efficiently approximates computationally intensive second-order terms (Hessian and Jacobian) using only a function value oracle. \n\nWeaknesses :  \n\n- Although a variance reduction-based approach is used in Equation 6a, the paper lacks a clear discussion of the motivation behind this choice and its specific contributions to the overall method. A more explicit explanation of how variance reduction influences the results would strengthen the presentation.  \n\n- The paper would benefit from a clearer articulation of its limitations and potential directions for future work.", "was_revised": true, "final_justification": "My initial score was positive. The authors addressed my concerns and I raised the score.", "rebuttal": "We thank Reviewer yzQD for the detailed questions. We address each point below:\n\n**Weakness 1: Although a variance reduction-based approach is used in Equation 6a, the paper lacks a clear discussion of the motivation behind this choice and its specific contributions to the overall method. A more explicit explanation of how variance reduction influences the results would strengthen the presentation.**\n\n**Question 1: What is the purpose of Lemma 2.1? It appears to be a direct application of the exponential moving average (EMA) and may not require a separate lemma.**\n\n**Response:** We appreciate this constructive comment. Lemma 2.1 plays a pivotal role in enabling online learning without relying on window smoothing. As discussed below Lemma 2.1 (Lines 104--107), for specific choices of $w$ and $W$, the time-smoothed gradient forms a momentum-type search direction. Our key insight is that, instead of using time-smoothed gradients directly as a search direction (as in previous online bilevel optimization (OBO) methods such as OAGD, SOBOW, and SOBBO), we can design momentum-type updates to achieve local regret bounds without smoothing.\n\nHowever, our initial theoretical analysis revealed that achieving regret bounds via momentum updates—without gradient smoothing—would require assuming bounded inner-level gradients, a restrictive condition under our strong convexity assumption (Assumption 2.2). To address this, we introduce Equation (6a), which replaces time-averaged gradients with a variance reduction momentum-based update that avoids such assumptions. Specifically, the first two terms ($\\eta \\nabla f_t(x_t, y_t; B_t) + (1-\\eta) d_{t-1}^x$) implement a momentum update and eliminate time smoothing, while the remaining term $(1-\\eta)(\\nabla f_t(x_t, y_t; B_t) - \\nabla f_t(x_{t-1}, y_{t-1}; B_t))$ controls noise amplification in the nested bilevel structure and avoids additional assumptions on bounded gradients.\n\nFurthermore, we show that under a suitable choice of $\\eta$, this variance reduction mechanism in Equation (6a) enables us to achieve $O(T^{1/3})$ regret rates without window smoothing. This represents a significant improvement over the typical $\\mathcal{O}(T^{1/2})$ regret rates obtained by standard online single-level and bilevel methods. We will expand this discussion in Section 2 to better motivate the specific form used.\n\n---\n\n**Question 2: In Theorem 2.6, what can be said about the optimality of the regret bound with respect to the time horizon $T$? Which specific factor is responsible for the improvement over OSO?**\n\n**Response:** Thank you for your comment. As we do not provide matching lower bounds, we do not claim these bounds are optimal. In fact, establishing lower bounds for bilevel regret remains an open problem in both first-order and zeroth-order settings. To our knowledge, all prior works—including those listed in Table 1 (e.g., OAGD, SOBOW, SOBBO)—focus exclusively on upper bounds. For further discussion, please see our response under Limitations.\n\nBelow, we discuss the regret bound with respect to the time horizon $T$ for both OBO and online single-level optimization (OSO).  \nAs discussed in Remark 2.7 and shown in Theorems 3.1 and 4.2 of OSO-type methods [[Hallak et al., 2021]](https://openreview.net/forum?id=XkXb99Eeg6G), in OSO, dynamic regret bounds include a regularity term (e.g., $V_T$, representing online time variations) that quantifies the temporal change in the cost functions. The average regret bound $\\mathcal{O}(T^{-1/2} \\sigma^2)$ is meaningful only when this regularity term is sublinear. Please see also [[Besbes et al., 2015]](https://pubsonline.informs.org/doi/abs/10.1287/opre.2015.1408?journalCode=opre), [[Hazan, 2017]](https://proceedings.mlr.press/v70/hazan17a/hazan17a.pdf), [[Aydore et al., 2019]](https://openreview.net/forum?id=HJxWTNrg8B), [[Zhang et al., 2020]](https://openreview.net/forum?id=Z_8hoytvdi), and [[Guan et al., 2024]](https://openreview.net/forum?id=iZgECfyHXF).\n\nOur method's regularity term $\\Delta_T$ is analogous to those in prior work, but the key difference is that our dependence on $T$ and $\\sigma$ yields strictly better scaling than previous methods when $\\Delta_T$ grows slowly. For example, in Theorems 3.1 and 4.2 of [[Hallak et al., 2021]](https://openreview.net/), the stochastic component appears as $T \\sigma^2 / w^2$ or $(T / w^2 )(\\delta^2 + \\tau \\sigma^2)$, along with regularity terms. Hence, their average regret bound scales as $\\mathcal{O}(T^{-1/2} \\sigma^2)$ under the assumption that the regularity term is sublinear. However, under similar assumptions, our average regret bound scales as $\\mathcal{O}(T^{-2/3} \\sigma^2)$, which shows significant improvement in dependence on $T$.\n\nSimilarly, in the OBO setting (see Table 1), all existing methods incorporate regularity terms such as $V_T$, $H_{p,T}$, or $\\Delta_T$ in their regret bounds. Specifically, all existing methods (e.g., OAGD, SOBOW, SOBBO) yield regret bounds like $T/w + V_T + H_{2,T}$ or $(T/w) \\sigma^2 + V_T + H_{2,T}$ with $w = o(T)$; please see [[Ataee Tarzanagh et al., 2024]](https://openreview.net/forum?id=dzmWT2UWMD), [[Lin et al., 2024]](https://openreview.net/forum?id=Xx1_bVkiuZ), and [[Bohne et al., 2024]](https://openreview.net/forum?id=VYU605FWmS).\n\nHowever, our average regret bound features a $\\sigma^2$ term that is multiplied by a factor strictly better in $T$ than previous methods, which often incur an $\\mathcal{O}(T^{-1/2})$ rate due to window averaging (please refer to Table 1).\n\nOverall, our method is able to achieve regret bounds that improve over both single-level and bilevel settings.\n\n---\n\n**Question 3: Is the dimensional dependence in the zeroth order setting optimal? In Theorem 3.2, Line 200, the dimensional dependence seems to be $\\mathcal{O}((d_1 + d_2)^{3/2})$, but in Remark 3.3, this is reported as $\\mathcal{O}(d_1 + d_2)$. Which statement is correct?**\n\n**Response:** Thank you for catching this important discrepancy. In Remark 3.3, we wrote $O(d_1 + d_2)$ to highlight the dependence on both the upper-level and lower-level dimensions. However, we simplified the expression and omitted the exponent for brevity. The correct dimensional dependence appears in Theorem 3.2, where the regret bound consists of two dominant terms: the first term scales as $O((d_1 + d_2)^{3/4})$, and the second as $O((d_1 + d_2)^{3/2})$.\n\nThis higher-order dependence is expected in the zeroth-order bilevel setting, where gradients, Jacobians, and Hessians must be estimated using only function evaluations. \n\nWe will revise Remark 3.3 to clarify that although $O(d_1 + d_2)$ reflects the qualitative dimensional dependence, the exact bound includes powers stated in Theorem 3.2.\n\n---\n\n**Weakness 2: Paper lacks clear articulation of limitations and future work**\n\n**Limitations: The discussion of limitations is rather superficial. For example, there are many more natural questions that are left open after reading this paper. Are the regret bounds optimal? If not, what are the lower bounds for regret in each problem setting?**\n\n**Response:** Thank you for raising this important point. We agree that the current discussion of limitations can be expanded. While our work establishes the first sublinear regret guarantees for stochastic OBO without window smoothing, we do not claim these bounds are optimal. Indeed, deriving lower bounds for bilevel regret remains an open and challenging problem, in both first-order and zeroth-order settings. To date, all existing works have focused exclusively on upper bounds (please refer to Table 1).\n\nWe will revise the limitations section to explicitly state that the optimality of our regret bounds is not known, and that lower-bound analysis is an important direction for future work.\n\nBeyond this, another limitation is that the work focuses on nonconvex online bilevel learning, which is more challenging than the convex case. Extending our results to cover convex and strongly convex bilevel problems, particularly in the zeroth-order setting, would be a valuable direction for future research. While first-order convex and strongly convex guarantees exist for some prior OBO methods [[Tarzanagh et al., 2022]](https://proceedings.mlr.press/v238/ataee-tarzanagh24a/ataee-tarzanagh24a.pdf), no such guarantees currently exist for zeroth-order bilevel optimization. This represents an open and important area for further investigation.\n\nWe will add a discussion of these potential improvements and outline lower bound questions for future work."}, {"review_id": "91rDmrPWpm", "reviewer": "Reviewer_R7y3", "summary": "This article presents two online bilevel optimization algorithms SOGD and ZO-SOGD. Among them, SOGD achieves the sota local regret bound without using window-smoothed functions. ZO-SOGO provides a fully-zero-order approach and achieves the hypergradient estimation only with function values. The authors present the theoretical analysis of the regret as well as the convergence analysis. Both two algorithms perform well in a series of numerical experiments.", "questions": "1. Whether the authors can present the comparison of different algorithms under **wall-clocked time**?\n2. Whether the author lack a detailed comparsion for the computation complexity of different algorithms?\n3. How does the step size affect the algorithm performance practically? Please provide some experimental results.\n4. Can the authors provide a brief proof sketch? It may help readers understand the proof.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. Both algorithms are sing-loop.\n2. SOGO achieves the sota regret bound without extra computation of the window-smoothed function. ZO-SOGO provides a fully-zero-order approach for online BO, which is especially useful in the training of large models.\n3. The authors present a detailed proof of the regret bound, which have been quickly checked by the reviewer and no errors have been found.\n4. The experiment result successfully validate the theoretical finds.\n\nWeakness:\n1. The authors fail to present the comparison of different algorithms under **wall-clocked time** in the experiment, which may illustrate the practical value of the proposed algorithms. Also, additional experiment should be taken to validate how step size affects the convergence.\n2. The author lack a detailed comparsion for the computation complexity of different algorithms.", "was_revised": true, "final_justification": "This submission is a theoretically valuable paper for discussion with rich theoretical results and enough experiments. Moreover, all the concerns have solved during rebuttal and discussion period. Thus, the reviewer recommends to the acceptance.", "rebuttal": "We thank Reviewer R7y3 for the constructive comments. We address each point below.\n\n**Question 1: Can authors present wall-clock time comparison?**\n**Weakness 1: Missing wall-clock time comparison and step size analysis**\n\n**Response:**  Thank you for your review and suggestions. We would like to clarify that the runtime plots presented in both Figures 2 and 3 already show wall-clock time measurements in seconds. Please refer to the left subplot in Figures 2 and 3, where we report time elapsed. \n\nSpecifically,  \n\n- In Figure~2 (left panel), we present the actual **wall-clock time of our ZO-SOGD** method compared to the baseline methods in the online adversarial attack experiment. The recorded times range from approximately $0.5 \\times 10^2$ to $2.0 \\times 10^2$ seconds at $T=200$ steps.\n\n- In Figure 3 (left panel), we present **wall-clock time comparisons for our SOGD** method against OAGD and SOBOW in the parametric loss tuning task. The results show a clear efficiency gain, with SOGD completing under 25 seconds at $T = 400$, compared to SOBOW, which takes roughly 220 seconds due to its reliance on conjugate gradient (CG) iterations.\n\nAll wall-clock times were measured using the same hardware platform across all algorithms to ensure fair and consistent comparisons. \n \nIn the revised version, we will make this point more explicit by stating \"wall-clock time\" clearly in the figure captions and experimental section to avoid any ambiguity.  \n\n\n\n**Question 2: Detailed computational complexity comparison?**\n**Weakness 2: Lack of detailed computational complexity comparison**\n\n**Response:**  Thank you for your valuable comments.  We will provide the total computational cost estimates for each method.\n\n**Total complexity:**\n- **SOGD**: $O((d_1 + d_2)\\cdot \\epsilon^{-3})$  \n- **ZO-SOGD**: $O((d_1 + d_2)^{7/4} \\cdot \\epsilon^{-3})$  \n- **SOBOW/SOBBO**: $O(((d_1 + d_2) + \\kappa_g \\log(\\kappa_g)  d_2)\\cdot \\epsilon^{-3})$ due to conjugate gradient (CG) steps\n\nAs an example, for SOGD, the regret bound  \n$$BL\\text{-}Reg_T \\leq O(T^{1/3}(\\sigma^2 + \\Delta_T) + T^{2/3} \\Psi_T),$$  \nimplies that  \n$$BL\\text{-}Reg_T / T \\leq O(T^{-2/3}(\\sigma^2 + \\Delta_T) + T^{-1/3} \\Psi_T).$$  \nLet $O(T^{-1/3}) = \\epsilon$. Then $T = O(\\epsilon^{-3})$, which is sufficient to ensure that the average regret $BL\\text{-}Reg_T / T \\leq \\epsilon$, leading to a total cost of $O(\\epsilon^{-3})$.\n\nFor SOGD, we have $O(d_1 + d_2)$ gradient computations, $O(d_2)$ Hessian-vector products, and $O(d_2)$ Jacobian-vector products. Since the algorithm operates over $T$ iterations, the total number of operations is $T(d_1 + d_2)$. Note that to achieve $\\epsilon$-stationarity, we need $T = O(\\epsilon^{-3})$ iterations. Thus, the computational complexity is $O((d_1 + d_2)\\cdot \\epsilon^{-3})$.\n\nWe note that the total cost for other baselines (SOBOW/SOBBO) is derived using their window size $w = o(T)$ and the factor $\\kappa_g \\log(\\kappa_g)$ for conjugate gradient (CG) steps. The OAGD baseline incurs higher cost due to exact system solves at each iteration.\n\nWe will include the above discussion in the main paper in the revised version.\n\n\n**Question 3: How does step size affect algorithm performance practically?**\n\n**Response:**  Thank you for your valuable feedback.\n\nWe apologize that these details were not prominently featured in the main paper. We would like to clarify that a comprehensive hyperparameter sensitivity study—including step sizes, momentum parameters, and other key settings—has been included in **Appendix E** of our submission within the **Supplementary Material: zip** file. This appendix provides detailed ablation studies showing how different parameter choices affect algorithm performance across various problem settings, along with practical guidelines for parameter selection. If the reviewer requires any specific clarification regarding these studies, we are happy to provide further details.\n\nIn summary, we conducted extensive tuning for ZO-SOGD in the adversarial attack scenario. This includes inner/outer step sizes ($\\beta$, $\\alpha$), smoothing parameters ($\\rho_v$, $\\rho_r = \\rho_s$), and momentum terms ($\\gamma_t$, $\\lambda_t = \\eta_t$). While ZO-SOGD is somewhat sensitive to these choices, it consistently performs well across a wide range.\n\n- Best performance was achieved with $\\beta = 0.1$, $\\alpha = 0.001$;  \n- Smoothing parameters $\\rho_v = 0.01$, $\\rho_r = \\rho_s = 0.005$ yielded stable behavior;  \n- Momentum $\\gamma_t = \\lambda_t = \\eta_t = 0.99$ led to the strongest attacks (accuracy $0.24 \\pm 0.02$).\n\nWe will make **Appendix E** more visible in the main text for clarity. Please let us know if further details are needed.\n\n\n**Question 4: Can authors provide a brief proof sketch?**\n\n**Response:**  We thank the reviewer for the constructive comment.\n\nDetailed proof sketches are provided in **Appendix C (lines 516–529)** for our first-order method (SOGD) and in **Appendix D (lines 797–811)** for the zeroth-order method (ZO-SOGD). For convenience, we summarize the key ideas below using simplified explanations and light math.\n\n**SOGD Proof Sketch:**  \n\nThe analysis starts with Lemma C.2, which bounds the error between the momentum-based estimate $d^y_t$ and the true inner gradient $\\nabla_y  g_t(x_t, y_t)$. Using this, Lemma C.4 shows convergence of $y_t$ toward the best-response solution $y_t^\\star(x_t)$, i.e., minimizing $ g_t(x_t, \\cdot)$. Lemma C.5 controls the error in $d^v_t$ versus the ideal second-order term involving $\\nabla_y f_t$ and $\\nabla^2_y g_t$. Lemma C.8 then bounds the error $||v_{t+1} - v^\\star_t(x_t)||^2$. Lemma C.9 focuses on the hypergradient estimator $d^x_t$ and its closeness to the true gradient $\\nabla_x f_t(z_t) + \\nabla^2_{xy} g_t(z_t) v_t$. Finally, Lemma C.11 establishes a projection bound that aggregates the above errors to complete the regret analysis.\n\n**ZO-SOGD Proof Sketch:**  \n\nFor the zeroth-order case, Lemma D.9 quantifies the error between the zeroth-order estimate $d^y_t$ and the smoothed gradient $\\nabla_y g_{t,\\rho}(x_t, y_t)$. Lemma D.11 shows that the iterates $y_t$ converge to a smoothed best response $\\hat{y}^*_t(x_t)$. The auxiliary vector estimates are handled in Lemma D.15, bounding the difference from the smoothed version of $\\nabla_y f_t + \\nabla^2_y g_t \\cdot v_t$, while Lemma D.17 ensures the convergence of $v_t$ to $\\hat{v}^\\star_t(x_t)$. Lemmas D.19–D.22 complete the proof by addressing hypergradient approximation and projection error bounds.\n\nWe will include this summary in the main paper in the revised version, if space permits."}]

Author rebuttal:

Meta-review: This paper proposes a new online bilevel optimization method. It introduces a novel search direction that  does not rely on deterministic window-smoothed regret minimization as existing approaches. It then shows that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear stochastic bilevel regret without window smoothing. 

All reviewers agree that eliminating the dependence on window smoothing is a significant contribution to online bilevel optimization. In addition, the experiments confirm the effectiveness of the proposed method.  A minor concern after the rebuttal phase is that the paper lacks a more comprehensive discussion of its regret bound, particularly with regard to its limitations in worst-case scenarios. It is highly recommended that this issue be addressed in the camera-ready version. Overall, this paper makes important contributions to online bilevel optimization and is recommended for acceptance.
Decision: Accept (poster)