Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization
Authors: Khanh-Hung Giang-Tran
Soroosh Shafiee
Nam Ho-Nguyen
Venue: NeurIPS 2025 poster ()
Keywords: bilevel optimization
stochastic optimization
projection-free
conditional gradient
Primary area: optimization

Abstract: We propose efficient methods for solving stochastic simple bilevel optimization problems with convex inner levels, where the goal is to minimize an outer stochastic objective function subject to the solution set of an inner stochastic optimization problem. 
    Existing methods often rely on costly projection or linear optimization oracles over complex sets, limiting their scalability. 
    To overcome this, we propose an iteratively regularized conditional gradient approach that leverages linear optimization oracles exclusively over the base feasible set. Our proposed methods employ a vanishing regularization sequence that progressively emphasizes the inner problem while biasing towards desirable minimal outer objective solutions. In the one-sample stochastic setting and under standard convexity assumptions, we establish non-asymptotic convergence rates of $O(t^{-1/4})$ for both the outer and inner objectives. In the finite-sum setting with a mini-batch scheme, the corresponding rates become $O(t^{-1/2})$. When the outer objective is nonconvex, we prove non-asymptotic convergence rates of $O(t^{-1/7})$ for both the outer and inner objectives in the one-sample stochastic setting, and $O(t^{-1/4})$ in the finite-sum setting. Experimental results on over-parametrized regression and dictionary learning tasks demonstrate the practical advantages of our approach over existing methods, confirming our theoretical findings.

Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization
Khanh-Hung Giang-Tran Cornell University tg4520cornel1.cer edu
Soroosh Shafiee
Nam Ho-Nguyen The University of Sydney nam nam.ho-nguyemae noyyenuyensyydee edu au
Cornell University
shaf weafeeecoeee...om edu
Abstract
We propose efficient methods for solving stochastic simple bilevel optimization problems with convex inner levels, where the goal is minimize outer stochas- tic objective function subject to the solution set of an inner stochastic optimization problem. Existing methods often rely costly projection oracles over complex sets, limiting their scalability. To overcome this, we propose iteratively regularized conditional gradient approach that leverages linear opti- mization oracles exclusively over the base feasible set. Our proposed methods em- ploy vanishing regularization sequence that progressively emphasizes the inner problem while biasing towards desirable minimal outer objective solutions. In the one-sample stochastic setting and under standard convexity assumptions, we es- tablish non-asymptotic convergence rates of ((1-1/4) for both the outer and inner objectives. In the finite-sum setting with a mini-batch scheme, the corresponding rates become Ö(t-1/3) When the outer objective is nonconvex, we prove non- asymptotic convergence rates of Ó(t-l/7) for both the outer and inner objectives in the one-sample stochastic setting, and ((t-1/1) in the finite-sum setting. Ex- perimental results on over-parametrized regression and dictionary learning tasks demonstrate the practical advantages of our approach over existing methods, con- firming our theoretical findings.
linear optimization
Introduction
We consider stochastic simple bilevel optimization problees,,,,,oo,s,ss,,,, where the goal is to minimize an outer stochastic objective function subject to the solution set of an inner stochastic convex optimization problem. Formally, the problem defined as
Fopt = min (F(x) == Eff (z. 0)] x E Nopth, where Xopt == arg min (G(z) = :- (2 #ER'
=EX
(1)
Here X C. Rd is a compact convex set, and both F and G are smooth with G is additionally
convex, making the optimization problem (1) possibly nonconvex problem with convex domain. This framework has broad applicability, including hyper-parameter optimization [16, 17,39) 39]. meta- learning [17, 42], reinforcement learning [32] and game theory [50]. particular, problem (1) arises in learning applications where G is the prediction error of a model z on data, and F is auxiliary validation data set). The dependence on data is through the expectation operators and the random variables 0, S. The bilevel formulation provides tuning-free alternative to the usual regularization approach where we optimize a F(xx) + G(x) for a carefully tuned parameter
objective (e.g., regularization,
Despite its wide applications in machine learning there three primary challenges in solving (1). First, we do not have an explicit representation of the optimal set Xopt in general, preventing us
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

from using some common operations in optimization such as projection onto or linear optimization over Xopt. An alternative is reformulate (1) using its value function formulation
min =EX
F(z) s.t. G(x) Gapt
min G(z)- =EX
However, this leads to our second challenge. Problem (2) is inherently ill-conditioned: by defini- tion of Gopt. there exists no x X such that G(z)) Gope, hence (2) does not satisfy Slater's s condition. As a result, the Lagrangian dual of (2) may not be solvable, complicating the use of standard primal-dual methods. In addition, we do not know Gopt a priori,
alternative is to approximate it with G' < Gope Eg. and consider the constraint G(xx) < G instead. However, this approach does not solve the actual bilevel problem (I), and may still introduce numerical instability. The third challenge comes from the stochastic nature of the objectives. Since F and G are defined as expectations, their exact computation may be intractable when dealing with large-scale datasets. In single-level optimization, this is typically addressed through sampling- based methods that op- crate on mini-batches drawn from the distributions of 0 and & instead of the actual distributions themselves. However, such stochastic approximations introduce noise into the optimization process, necessitating new techniques to control the noise and ensure convergence.
1.1 Related works
Simple bilevel optimization problems with nonconvex outer objectives This setting has been studied by Jiang et al. [29] in the deterministic case and by Cao et al. [4] in the stochastic case. These works propose conditional gradient methods that require performing linear optimization over inter- sections of the base domain X with a halfspace. In contrast, our approach removes this requirement by relying solely on linear optimization over X. We note that we do not address the more general case with both nonconvex inner and outer objectives considered in [5, 21, 24]. In the remainder of this section, will focus simple bilevel problems with convex inner and outer objectives.
Iterative regularization methods. Simple bilevel optimization extends Tikhonov regulariza- tion [52] beyond f2 penalties by considering a blended objective a F(z))+((x)) where
modu- lates the trade-off between inner and outer objectives. As o - 0, the problem converges to a bilevel form that prioritizes the inner objective. Friedlander and Tseng [18] established fundamental condi- tions ensuring solution existence for a > 0, forming the basis for iterative regularization, where is gradually reduced. This idea was first implemented by Cabot [3] in the unconstrained case X = Rd using a positive decreasing sequence os, and later extended to general convex constraints by Dutta and Pandit [14]. While these methods use proximal steps, which can be computationally expensive, Solodov [49] proposed a more efficient gradient-based alternative. Helou and Simões [23] further generalized the framework to non- smothh settings via an e-subgradient method. These works show asymptotic convergence but lack convergence rates. Amini and Yousefian [1] analyzed an iterative regularized projected gradient method and established a convergence rate of (1)--1/2))) for the inner objective, assuming non-smooth I' and G, compact X, and strong convexity of f. Kaushik and Yousefian [30] later removed the strong convexity assumption and proved rates of O(t"²) and
((t-(1/2-0) b)) for the inner and outer objectives. respectively, for any b E (0, 1/2). Malitsky [35] studied an accelerated variant based on Tseng's method [53]. achieving an o(t rate for the in- ner problem. More recently. Merchav et al. [37] proposed an accelerated proximal scheme with a Olog(t + 1)/t) rate under smoothness assumption and (t-2) and (11/2277) for inner and outer objectives, respectively, under a Hölderian error bound condition with modulus E (1, Our work also follows an iterative regularization approach, but avoids expensive projections or proximal operations by leveraging linear optimization oracles.
Projection-free methods. Several important applications have domains where projection- operations are inefficient, yet linear optimization over X is easier. To address the limitations of projection-base methods, recent work has focused on projection-free bilevel optimization via linear optimization oracles. Jiang et al. [29] approximated Xopt by replacing the constraint G(x) < Gopt with a linear approximation, which removed the need for Slater's condition, and applying the con- ditional gradient method, refining the approximation at each step. They established O(t-1) conver- gence rates for both objectives under smoothness and compactness assumptions in case f is convex. Under non-convex setting, they claimed the convergence rates of ((t-1/2) to the stationary point of the problem. However, their method requires a pre-specified tolerance parameter <g. and only
2

---

guarantees (fg/2)-inne 22iieeeaaiibil Doron and Shtern [12] proposed an alternative approach based on sublevel sets of the outer function F. Their method performs conditional gradient updates over sets of the form X x {a: : F(x) S a), with a surrogate G, that is updated iteratively. They achieved rates of )(( for the inner and ((121/2) for the outer objective under composite structure G and an error bound on F. While linear optimization over X may be efficient, this is not always true for sets like X n H. where H is a halfspace, or { {F(z) S a) unless has special structure. To address this, Giang-Tran Tran et al. [20] introduced conditional gradient-based iterative regularization scheme that only requires linear optimization over X, albeit with slower rates: (t+=²) and ((t-(1-P) for the inner and outer problems, respectively, for any p E (0, 1). We extend this framework to the stochastic setting, maintaining the same oracle-based reliance on linear optimization over X.
Stochastic methods. Stochastic bilevel optimization remains less explored. Jalilzadeh et al. [27]
developed an iterative regularization-base based stochastic extragradient algorithm, requiring (11cc)
and O(1 (e") stochastic gradient queries to achieve 6-optimality for both objectives. Cao et al. [4]
extended the projection-free framework of Jiang et al. [29] the stochastic setting. Their methods
achieve O((-") convergence rate when the noise distributions have finite support, and Ö(t-1/2)
convergence rates under sub-Gaussian noise. However, their method requires linear optimization over intersections of X with a halfspace. In contrast, our work relaxes this requirement by relying solely on linear optimization over the base set X.
Other methods and bilevel problem classes. Several alternative approaches exist for simple bilevel optimization, including sequential averaging schemes [36, 44, 46], sublevel set-based meth- ods [2, 6, 21, 58], accelerated algorithms [6, 7, 45, 54] and primal-dual strategies [47]. These methods are less related to our framework and do not address the stochastic setting. More general bilevel problems have seen considerable attention. particularly in Stackelberg game formulations where the upper and lower levels model leader-follower dynamics [8, 10, 19, 28, 31, 33, 34, 56]. Recent extensions include contextual bilevel optimization with exogenous variables [25, 51, 55] and problems with functional constraints the lower level [30, 40]. Our focus in this paper, however, restricted to the stochastic simple bilevel problems.
1.2 Contributions
We present two iterative regularization methods for solving problem (1) in both stochastic and finite- sum settings. The key idea is introduce a decreasing regularization sequence {a:)22 1, and at each iteration 6, perform a gradient-basse based update on the composite objective o, + G. As o, decreases, the algorithm gradually shifts focus from to G, thereby steering x; toward points in Xope- At the same time the o term encourages xe towards point in Xopt that minimizes F. In the stochastic formulation (1), computing exact gradients of the upper and lower objectives is computationally the
expensive. To address this, we employ sample-based gradient estimators. Specifically, STOchastic Recursive Momentum (STORM) estimator [9] in the one-sample stochastic setting, and the Stochastic Path Pate-Inte Differential EstimatoR (SPIDER) [15, 38] in the finite-sum setting.
The key contributions of this paper are summarized below.
One-sample stochastic setting: We develop a projection-free method for stochastic simple bilevel optimization that under convexity of F on the base set X achieves nigh-probability con- vergence rates of O / //lg(d? dt² /8)) for the outer-level problem and O(t-//A/oo((d/) for the inner-level problem, with probability at least 1 8. Without convexity of F, the method enjoys the non-asymptotic convergence rates of O( (og(d(2/8) for both the outer- and inner- level objectives. Compared to the state-of-the-an approach by Cao et al. [4, Algorithm 1], which achieves the O(t-1/2 / /log(td/5) rate under convex settings and O(t (togg///log(td (log(td/8)) under nonconvex settings for both the outer and inner problems, our method offers several key advan- tages. First, it eliminates the need for optimization over intersections of the base domain with a halfspace, requiring only linear optimization over the original constraint set. Second, it removes the dependency on their pre-specified tolerance parameter ég. and the associated computationally expensive initialization procedure to find an -optimal starting point. Third, our algorithm en- joys anytime guarantees. Overall, the proposed algorithm is simple, single-loop procedure that is significantly easier to implement than that of [4].
3

---

Finite-sum setting: For problems with n component functions, we establish convergence rates of O(t-1/2 /8)) (outer) and O(t-1/2 (oo-1//21ol(11 (1))) (inner) with probability 1 - 8. Without convexity of F, the method enjoys the non-asymptotic convergence rates of O(L log(dl /8)) for both the outer- and inner-level objectives. Although Cao et al. [4. Algorithm 2] achieves improved O /log(t/) rates under convex settings and O /log(//)) rates un- der nonconvex settings for both objectives, it again relies on more computationally demanding halfspace-inee intersecionn oracles, requires an additional initialization step, depends on a fixed step- size, and does offer anytime guarantees.
Numerical validation: We demonstrate the practical efficiency of our methods on over- parametrized regression and dictionary learning tasks, showing significant speedups over existing projection- based and projection-fre free approaches. The experiments validate both the convergence rates and computational advantages of our framework.
The supplementary material is organized in the appendices as follows. Appendix A establishes the preparatory lemmas used throughout our analysis. Appendices and C contain the detailed proofs for the results presented in Section 2 and Section 3, respectively. Appendix D provides additional material, including analyses of the convergence rate coefficients well details of the numerical implementations in Section 4.
2 Algorithm and convergence results for the one-sample stochastic setting
In this section, we introduce the Iteratively Regularized Stochastic Conditional Gradient (IR-SCG) method, summarized in Algorithm 1. This approach conditional gradient method that leverages the STORM estimator to progressively reduce noise variance via momentum-base updates, assuming sub-Gaue Gaousasssin noise. While the use of the STORM estimator in projection-free methods was first explored in [60], our IR-SCG algorithm offers several key advantages. Notably, unlike the method of Cao al. [4], IR-SCG is an anytime algorithm that does not require careful initialization, preset step sizes, or knowledge of the total number of iterations T in advance.
Algorithm 1: Iteratively Regularized Stochastic Conditional Gradient (IR-SCG) Algorithm.
Data: Parameters {01)22 S [0, 1].(or)e20 S RR++. Result: sequences (12, h221- Initialize 2g E X;
for t = 0, do if then
Compute
VF. V,) VG. = Vag(I:,
else Compute
VF. (1 V -1-
VG. = (1 - ar) VG 0000
Compute
1t arg min x
(oVV.'+ + VC,) o
Je+1 x, + av - xxt)
S + 2)(1 + 1)
Σ
(i (1+t)-(i-1--0
*E|t+1
2++1 1= (t+ + 1)0:+10141 + Eie (i+ 1)i(0111-11
(1)))((i11 - -0,)24
S

---

To establish convergence rates for Algorithm 1, we impose the following standard assumptions on the simple bilevel problem (1). the following, all norms refer the Euclidean norm.
Assumption 1. The following hold.
(a) C TR. is convex and compact with diameter D oo, iee, |x~ D for any z, E X.
(b) Functions F, G are convex over X and continuously differentiable on an open neighbor- hood of X.
(c) For any f(-,8) is Ly-smooth on an open neighborhood of X, ie., continuously differentiable and its derivative is -ipischhtt:::
[V, V 0)1 L 2/1
for any x, y E X.
(d) For any &, {) is T-g-Smooth on open neighborhood of X. (e) For any E X, the stochastic gradients noise is sub Gabusiassnnn, i.e., there exists some f Gg > such that
E exp (1
2 [ s exp((1)
E exp (1V VG(=)))//o)) s exp((1).
First, we present the result for the case that F convex.
Theorem 1. Let {zet121 be the iterates generated by Algorithm I with az 2/(t 2) for any t 2 O, and regularization parameters o; := +)++1) 1 for some chosen Ç > 00, E (0, 1/2). Under Assumption for any t 2 1, with probability at least 5, it (jointly) holds that
x0( F(z)) - Fopt s O (1-13/2-P)
Vlog (dt2 (dt2/5)
G(a) - Gopt S ( (d/3))
Moreover, with probability 1, have
lim F(xt) Fopt: 1-000
lim G(xx)) = Gopt-
Theorem 1 provides the formal convergence guarantees for the IR-SCG algorithm in the convex setting. set p 1/4, Algorithm achieves an e-level optimality gap for both the outer and inner problems with a sample complexity of (11/e)).
We extend analysis to the general case where F is not necessarily convex. In this setting, we require a different measure for stationarity. We define our stationarity measure using the Frank-Wolfe gap, which for convex function F(x) if and only if is optimal. This provides natural generalization for the non-convex case. Accordingly, for all E X, we define the functions
F(z) = max
(F(x))(x (x- ((x) == G(x) - Gopt.
To avoid clutter, we present the result using the optimally tuned parameters of Algorithm 1.
Theorem 2. Let {xe denote the iterates generated by Algorithm I with stepsizes Oz,- (t+1)-4
and regularization parameters at c(1+1)-- for any 122 0, with p= and w 6 4. If Assumptioon
holds with the exception that may be noncorvex, then with probability at least 8, for every t 2 0, it (jointly) holds that
Et of
so log((t2)))) (dt) G(xx) s 0 0(t log (dt? (d({/8)
Ei Ti
Moreover, with probubility 1, we have
lim inf F(x,) 0, 1-+00
lim g(xx) 1000
5

---

3 Algorithm and convergence results for the finite-sum setting
In this section, address the case where the expectations in (1) finite sums over components. We introduce the Iteratively Regularized Finite-Sum Conditional Gradient (IR-FSCG) method, sum- marized in Algorithm where [n] == ..,..., n2.. This approach conditional gradient method that leverages the SPIDER estimator, achieving variance reduction through periodic gradient recom- putations with mini-batches of size q. While the SPIDER estimator has been previously integrated into projection- -free methods [22, 48. 57, 59], here we show how it can be effectively adapted to our regularized setting. The primary advantage that, unlike the method of Cao al. [4], IR-FSCG preserves the desirable anytime properties of our approach while achieving faster convergence rate that capitalizes on the finite-sum structure. Additionally, it does not require careful initialization, preset step sizes, or knowledge of the total number of iterations T in advance.
To establish its convergence, we again rely on Assumption noting that condition Assumption I(e) holds automatically in this finite-sum setting. First, we present the result when F is convex.
Theorem 3. Suppose F and G in (1) are expectations over uniform distributions on [n]] Let hrs be the iterates generated by Algorithm 2 with = log(g)/4 for 0 S t < 0g = 2/(t + 2) for any 2 q, and at == (mmax(t, q) + 1)- for some chosen > 0, p E (0,1) and = 9. Under Assumption 1, with probability at least 1 5, for any 2 it holds that
Vlgg F(z)) Fopt O gc(t,g) (- Vlog (12/8)) G(z) Gopt SO ( Voo
log (1/8)
where c(t, 4) = max (1, q log(s)/t)- Moreover, with probability 1, we have
lim F(x) = Fopt.
lim G(xz) = Gopt. 100
5000
Algorithm 2: Iteratively Regularized Finite-Sum Conditional Gradient (IR-FSCG) Algorithm.
Data: Parameters (oz (22g S [0, 1], foe)20 S R4 S, E [n]. Result: sequences (Iz, 21211 Initialize zo E X; for ( 0, 2, do if = mod then Compute
VF, : VF(x)) VG. VG(x.).
else
Draw S new i..d. samples S = (01, ..... 0s). S₂ ..... Es}; , Compute
VF, VF + fis (xt) vis, (21-1) VG, = VG., + Vgs, (Ix) Vgs, (II-1)-
Compute
(o.VF. + Vo.) 8
"t E arg min vEX
241 == v4 + 0r r:))
i q then Compute
S (t+ (t 1)0
Σ
(i 1)1(0,11-0) -
(t () + 1) F141 + Eie
(i 1)i(or-1 - -0,)2;
2++1 ==
S

---

Theorem 3 provides the formal convergence guarantees for the IR-FSCG algorithm in the convex setting. Moreover, when we set S q Lyn and p = 1/2. Algorithm achieves an e-level opti- mality gap for both the outer and inner problems with sample complexity of O(vn/<²), Besides, Algorithm 2 can be readily extended when the outer- and inner-level problems involve different numbers of component functions (ny # n,g) by introducing (S,; 9f) for the outer level and (Sgz 9g) for the inner level. Details are omitted for brevity.
We next extend our analysis to the more general case where F is not necessarily convex, using the auxiliary function (3) assess stationarity. To avoid clutter, we present the result using the optimally tuned parameters of Algorithm 2.
Theorem 4, Let {xa 1:20 denote the iterates generated by Algorithm 2 with stepsizes a = log(q + 1)/(9 + 1) for any I t S q, at 1/(t + 1)th for any t > q and S 9, and regularization parameters of = s(max(t, 9 + +1 + 1) with p= 2 and w 3. If Assumption holds with the exception that F may be nonconvex, then with probability at least 6, for every 2 9, it (jointly) holds that
BoFBiF(a so log (dt21)). g(x+) S 0 (t log (df
Ei Bi
where
cooly 1)00 logla + 11) (1 log(g +1)
9-1
0 0sisg 4
B1
q +
a+1
i> q.
Moreover, with probability we have
lim inf F(x,) = 0,
lim G(zz) 0. t1000
400
Numerical results
We showcase the performance of our proposed algorithms in an over-parametrized regression and dictionary learning problems. For performance comparison, we implement four algorithms: SBCGI [4, Algorithm 1]. SBCGF [4, Algorithm 2], aR- aR-IG [27], and the stochastic variant of the dynamic barrier gradient descent (SDBGD) [21]. All implementation details follow those in the corresponding papers and available in Appendix D. To ensure reproducibility, all source codes are made available at https: //gi git.ub...... com/ wtt.cooo////eeeeeeeeeee brucegiang OG-SttBilll.
4.1 Over-parameterized regression
We first consider simple bilevel optimization problem with convex outer-level objective function
min F(x)= = |Dvall ||Avar - beall s.t. x E arg min G(=) = Danl || - by 1 zER
(5)
where the goal is to minimize the validation loss by choosing among optimal solutions of the training loss constrained by the norrr ball. We use the same training and validation datasets, (Aus by) and (Aval, bea)), from the Wikipedia Math Essential dataset [43], as in [4]. This dataset consists of n 1068 samples and 730 features.
We evaluate the performance of different algorithms across 10 experiments with random initializa- tions and report their average performance within a 4-minute exccution limit. Figure shows the convergence behavior of different algorithms for the inner-level (left) and outer-level (right) opti- mality gaps in terms of execution time. Our proposed stochastic methods outperform existing ap- proaches. In particular, IRCFSCG achieves high-accuracy solutions for the outer-level objective while maintaining strong inner-level feasibility, surpassing mini-batch counterpart, SBCGF, Similarly, IR-SCG outperforms its single-sample counterpart, SBCGI. We also observe that both SBCGI and SBCGF exhibit degradation in their inner-level optimality gaps over time. This behavior aligns with the theoretical guarantees in [4], where the inner-level convergence can only be bounded by eg/2 without monotonic improvement guarantees. Furthermore, neither aR-IP-SeG nor SDBGD makes significant progress in optimizing the outer-level objective function.
7

---

GL Gaps
20-1
10'1
10-4
(secands)
Time (seconds)
IR-80G
IR-PSCC
SBCGI
SBCOP
aR-IP-Bel (shors) * aRt-IPSSeG
SI8GD (short)
SDBGD (lomg)
Figure 1:
The inner-level optimality gap (left) and the outer-level absolute optimality gap (right) over time for different algorithms on the wer-parametrized regression problem (5).
The table below also reports the average number of iterations and stochastic oracle calls over the 4-minute time limit for each algorithm. Our projection-free method completes more iterations within the fixed time budget, benefiting from a simpler linear minimization oracle compared to the projection-free free approach in [4]. We also observe that SDEGD and IR-SCG perform similar num- ber of iterations, as the -norm projection oracle has comparable computational cost to the linear minimization oracle.
Method
Average iterations
Average # of oracle calls
IR-SCG IR-FSCG
1182617.0
2365234.0 28240425.0
369952.5
SBCGI
6726.9
7428681.9
SBCGF
6713.4
7935076.2
aR-IP-SeG (short step)
807700.2
3230800.8
aR-IP ER-IP-SeG (long step)
799725.0
3199300.0
SDBGD (short step)
1250392.6
2500782.2
SDBGD (long step)
1243720.1
2487440.2
4.2 Dictionary learning
In the dictionary learning problem, the goal is to learn a compact representation of input data A {aI,.... (n.) C R. Formally, we aim to find a dictionary D = [d] dp] Rm such that each data point a; can be approximated by linear combination the basis vectors in D. This leads to the following optimization problem
min D.X
|
Dari
xE(m]
s.t.
D E mxx
X = [2] ...... .. R
11
Vj E [p]. | s 8, Vi [n].
where we refer X the coefficient matrix. In practice, data points usually arrive sequentially and the representation evolves gradually. Hence, the dictionary must be updated sequentially as well. Assume that we already have learned dictionary D E Rxxp and the corresponding coefficient matrix E R for some data set A. As a new dataset A' = {af...., d C Rd arrives, we intend to enrich our dictionary by learning Ó E Rmxq (g > and the coefficient matrix X Rox=' for the new dataset while maintaining good performance of on the old dataset A as
well as the learned coefficient matrix X.

---

10"
10
10
Gaps
10"
G()
10-4
10-
10-
10
Time (saconds)
(seconds)
IR-8CC
IR-PSCC
SBCGT
SECOP
aR-IP-8el (shor:) *
aR-1P-SeG
SDBGD [short)
SDBGD (lomp)
Figure 2: The inner-level optimality gap (left) and the outer-level objective function (right) over time for different algorithms on the dictionary learning problem (6).
This leads to the following simple bilevel problem with a nonconvex outer-level objective function
1
min F(D,X):= = DX
||a
D
2n'
rE(n']
s.t. DE mxg, X = [ ... -,, E Roxn',
|| S
E
(6)
DE arg min |=s
g(Z) = 2n
||;; - Z
KE(n)
where we denote ds as the prolonged vector R by appending zeros at the end. We consider problem (6) on synthetic dataset with similar setup [4, 29].
We evaluate the performance different algorithms across 10 experiments with random initializa- tions and report their average performance within a 1-minute exccution limit. Figure 2 shows the convergence behavior of different algorithms for the inner-level (left) and outer-level (right) prob- lems in terms of execution time. Our proposed stochastic methods outperform existing approaches. In particular, IR-FSCG achieves better solutions for the outer-level objective while maintaining strong inner-level feasibility, surpassing its mini-batch counterpart, SBCGI. Similarly, IR-SCG out- performs its single-sample counterpart, SBCGI. We again observe that both SBCGI and SBCGF exhibit degradation in their inner-level optimality gaps time.
The table below reports the average number of iterations and stochastic oracle calls over the 1-minute time limit for each algorithm. Our projection-free free method completes more iterations within the fixed time budget, benefiting from simpler linear minimization oracle compared to the projection free methods in [4]. We also observe that SDBGD performs fewer iterations than IR-SCG, it relies more costly projection oracle.
Method IR-SCG
Average of iterations
Average # of oracle calls
32736.1
65472.2
IR-FSCG
30532.6
1872851.0
SBCGI
466.3
7440.6
SBCGF aR-IP-Sed (short step)
361.84
6147916.0
6290.0
25160.0
aR-IP-SeG (long step)
6278.1
25112.4
SDBGD (short step)
11441.3
22882.6
SDEGD (long step)
12239.3
24478.6

---

References
[1] M. Amini and F. Yousefian. An iterative regularized incremental projected subgradient method for a class of bilevel optimization problems. In American Control Conference, pages 4069- 4074, 2019.
[2] A. Beck and S. Sabach. first order method for finding minimal norm-like solutions of convex optimization problems. Mathematical Programming. 147(1):25-44) 46, 2014.
[3] A. Cabot. Proximal point algorithm controlled by slowly vanishing term: Applications to hierarchical minimization. SIAM Journal on Optimization, 15(2):555-572, 2005.
[4] J. Cao, R. Jiang, N. Abolfazli, E. Yazdandoost Hamedani, and A. Mokhtari. Projection-fiee methods for stochastic simple bilevel optimization with convex lower-level problem. In Ad- vances in Neural Information Processing Systems, pages 6105-6131, 2023.
[5] J. Cao, R. Jiang, E. Y. Hamedani, and A. Mokhtari. On the complexity of finding stationary points in nonconvex simple bilevel optimization. arXiv:2507.23155, 2025.
[6] Cao, Jiang. E. Yazdandoost Hamedani, and A. Mokhtari. An accelerated gradient method for convex smooth simple bilevel optimization. In Advances in Neural Information Processing Systems, pages 45126-45154, 2024.
[7] P. Chen, X. Shi, R. Jiang, and J. Wang. Penalty-based methods for simple bilevel optimization under Hölderian error bounds. arXiv:2402.02155, 2024.
[8] Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Advances in Neural Information Processing Systems, pages 25294-25307, 2021.
[9] A. Cutkosky and Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems, pages 15236-15245, 2019.
[10] M. Dagréou, Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that en- ables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems, pages (6698-26711 10, 2022.
[11] S. Diamond and Boyd. CVXPY: A Python-embedder modeling language for convex opti- mization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[12] L. Doron and S. Shtern. Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems. Mathematical Programming, 201(1):521- 558, 2023.
[13] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the ball for learning in high dimensions. In International Conference on Machine Learning, pages 272-279, 2008
[14] Dutta and T. Pandit. Algorithms for simple bilevel programming. In A. Zemkohoo and S. Dempe, editors, Bilevel Optimization: Advances and Next Challenges, pages 253-291. Springer, 2020.
[15] C. Fang, C. J. Li, Z. Lin, and T. Zhang. SPIDER: Near-optimal non-convex optimization via stochastic
differential estimator. In Advances in Neural Information Processing Systems, pages 687-697, 2018
[16] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-basse hyperparameter optimization. In International Conference on Machine Learning, pages 1665- 1173, 2017.
[17] I.. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyper- parameter optimization and meta-learning. International Conference on Machine Learning, pages 1568-1577,201
[18] M. P. Friedlladerr and P. Tseng. Exact regularization of convex programs. SIAM Journal on Optimization, (8(4):1326-135) 2008.
[19] S. Ghadimi and M. Wang. Approximation methods for bilevel programming.
1rXiv:1802.002246 2018
[20] K.-H. Giang- Tran, N. Ho-Nguyen, and Lee. projection-fiee method for solving convex bilevel optimization problems. Mathematical Programming, 2024.
10

---

[21] C. Gong, X. Liu, and Q. Liu. Bi-objective trade-off with dynamic barrier gradient descent. In Advances in Neural Information Processing Systems, pages 19630-29642, 2021.
[22] H. Hassani, A. Karbasi, A. Mokhtari, and Z. Shen. Stochastic conditional gradient++::nonn) convex minimization and continuous submodular maximization. SIAM Journal on Optimiza- 2020.
fion, (0r)3)303333333344
[23] E. S. Helou and L. E. A. Simões. e-subgradient algorithms for bilevel convex optimization. Inverse Problems, 33(5):050020, 2017. ISSN 0266-5611.
[24] Y.-G. Hsieh, J. Thortoo,, Ndiaye, M. Klein, M. Cuturi, and Ablin. Careful with that scalpel: improving gradient surgery with an EMA. 17Xi::2402.02998,, 2024.
[25] Y. Hu, J. Wang. Y. Xie, A. Krause, and D. Kuhn. Contextual stochastic bilevel optimization.
In Advances in Neural Information Processing Systems, pages 78412-78434 2023.
[26] M. Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435, 2013.
[27] A. Jalilzadeh, F. Yousefian, and M. Ebrahimi. Stochastic approximation for estimating the price of stability in stochastic Nash games. ACM Transactions on Modeling and Computer Simulation, 34(2):1-24, 2024.
[28] K. Ji, J. Yang. and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892, 2021.
[29] R. Jiang, N. Abolfazli. A. Mokhtari, and E. Y. Hamedani. A conditional gradient- basen method for simple bilevel optimization with convex lower-level problem. In International Conference on Artificial Intelligence and Statistics, pages 10305-10323, 2023.
[30] H. D. Kaushik and F. Yousefian. A method with convergence rates for optimization prob- lems with variational inequality constraints. SIAM Journal on Optimization, 31:21117)-2219, 2021.
[31] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via couble-momentum In Advances in Neural Information Processing Systems, pages 30271-30283, 2021.
[32] V. Konda and J. Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Pro- cessing Systems, pages 1008-1014, 1999.
[33] Kwon, D. Kwon, S. Wright, and R. D. Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18113, 2023.
[34] 7. Lu and S. Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1337-199,, 2024.
[35] Y. Malitsky. The primal-dual hybrid gradient method reduces primal method for linearly constrained optimization problems. arXiv:1706 NKK::1776602602,, 2017.
[36] R. Merchav and S. Sabach. Convex bi-level optimization problems with nonsmooth outer objective function. SIAM Journal on Optimization, 33(4):31 ((44))3114-3122) 2023.
[37] R. Merchav, S. Sabach, and M. Teboulle. A fast algorithm for convex composite bi-level optimization. arXiv:2407.2122// 2024.
[38] L.. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621, 2017.
[39] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Con- ference on Machine Learning, pages 737-746, 2016.
[40] I. Petrulionyté, Mairal, and M. Arbel. Functional bilevel optimization for machine learning. In Advances in Neural Information Processing Systems, pages 14016-14065, 2024.
[41] I. Pinclis. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, 12(4):167-11766 1994.
[42] A. Raghu, M. Raghu, S. Bengio, and O. Vinyals. Rapid learning or feature reuse? Towards understanding the effectiveness MAMI.. In International Conference on Learning Repre- sentations, 2020.
11

---

[43] B. Rozemberezki, P. Scherer, Y. He, G. Panagopoulos, A. Riedel, M. Astefanoaei, O. Kiss, Beres, G. López, N. Collignon, and Sarkar. Pytorch geometric temporal: Spatiotempo- ral signal processing with neural machine learning models. In International Conference on Information and Knowledge Management, pages 4564-4573, 2021.
[44] S. Sabach and S. Shtern. A order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):400-660, 2017.
[45] S. Samadi, D. Burbano, and F. Yousefian. Achieving optimal complexity guarantees for a class of bilevel convex optimization problems. In American Control Conference, pages 2206-2211, 2024.
[46] Y. Shehu, P. T. Vuong, and A. Zemkoho. An inertial extrapolation method for convex simple bilevel optimization. Optimization Methods and Software, 36(1):1-19, 2021.
[47] L. Shen, N. Ho-Nguyen, and F. Klinç-Karzan An online convex optimization- frame- work for convex bilevel optimization. Mathematical Programming, 198(2):519-1152. 2023.
[48] Z. Shen, C. Fang, P. Zhao, J. Huang, and H. Qian. Complexities in projection-free stochastic non-convex minimization. In International Conference on Artificial Intelligence and Statistics, pages 2876, 2019.
[49] M. Solodov. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2)2227, 2007.
[50] H. Stackelberg. The Theory of Market Economy. Oxford University Press, 1952.
[51] V. Thoma, B. Pásztor, A. Krause, G. Ramponi, and Y. Hu. Contextual bilevel reinforcement learning for incentive alignment. In Advances in Neural Information Processing Systems, pages 127369-127435, 2024.
[52] A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. V. H. Winston & Sons, 1977. Translated from the Russian, Preface by translation editor Fritz John, Scripta Series in Mathematics.
[53] P. Tseng. On accelerated proximal gradient methods for convex concave optimization. Tech- nical report, Department of Mathematics, University of Washington, 2008
[54] J. Wang, Shi, and R. Jiag. Near-optimal convex simple bilevel optimization with bisection method. In International Conference on Artificial Intelligence and Statistics, pages 2008-2016 2024.
[55] J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. In Advances in Neural Information Processing Systems, pages 13670-13682, 2021.
[56] Y. Yang, P. Xiao, and K. Ji. Achieving O(c-1.5 complexity in Hessian/Jacobian-fres stochas- tic bilevel optimization. In Advances in Neural Information Processing Systems, pages 39491 39503, 2023.
[57] A. Yurtsever, S. Sra, and V. Cevher. Conditional gradient methods via stochastic path- integrated differential estimator. In International Conference on Machine Learning, pages 7282-7291, 2019.
[58] H. Zhang, L. Chen, J. Xu, and J. Zhang. Functionally constrained algorithm solves convex simple bilevel problem. In Advances in Neural Information Processing Systems, pages 57591- 57618. 2024.
[59] M. Zhang, L. Chen, A. Mokhtari, H. Hassani, and A. Karbasi. Quantized Frank-Wolfe: Faster optimization, lower communication, and projection free. In International Conference on Arti- ficial Intelligence and Statistics, pages 3696-3706, 2020.
[60] M. Zhang. Z. Shen, A. Mokhtari, H. Hassani, and A. Karbasi. One sample stochastic Frank- Wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4012-4023 2020.
12

---

A Preparatory Lemmas
Throughout all appendices, we employ the notation $x(x) := o.F(x)+((x) and
VG, to denote the gradient estimate at step t. We also denote Topt E Xopt as an optimal solution to (1). All norms refer to the Euclidean norm.
For any sequence (1e generated by either Algorithm or Algorithm we observe that by construction, 2o, D2 E X Hence, under convexity of X, F++1 E X as it is convex combination of x, and et, and is assumed to convex. By a simple induction argument, one can easily show that the sequence (2+)120 E X.
A.1 Convex outer-level
Lemma Let (11)120 denote the iterates generated by Algorithm I or Algorithm 2 with some given stepsizes far)120. If Assumptiin 1 holds, then for every 1 2 ki we have
D2 +20, (0.(2))
- (()_a))(((()))) (aai))-D((rra (Fope)))
2
Proof of Lemma
Recall that
F++1 24 onlVe 2t), where is E arg
(7.))
vEX
As both functions F and G are assumed be convex and smooth, is easy to show that convex and o,Ly + Lg smooth. By smoothness of o, and the assumption that diam(X) D, can show that
(.(4+1) S 21(2)) a Vol xz) + (oeks + Lg)a
110e x,11
S ( + a. (xx (v. - (x)+ (oetss (.gg D2
Note that for any W, X and any gradient estimator , we have
(xx) (r+ - xzt)
(V vΦ.) (vr 21) + VΦ, (e: zz)
(V,) VΦ.) T (vt - 2,) + V4, (w: Izt) (az) Vo.) T (mr- 21) + (VØ, (tt( ( (w, S 2D VΦ.- - (I.(1)) + (x+( (w: - xt),
xx) + (., (o)((())(((s))) (wi - -xa)
where the first inequality follows from the definition of us and the second inequality uses the Cauchy-Schwarz inequality, and the assumption that diam(X) D. Thus, by smoothness of Φ,,
for any wa E X and any gradient estimator V we have
(x((111) < (,(x:) V4, (w: (w) xx) +2 (Z)))l (o,L,+L,)DD' (7)
2
and set wi Topt. Thanks to the convexity of th, easily show that (2, - =x)) 5 (Foppt - (1z). Thus, we obtain
or (x(+1))) (x(op)
< (x,)) - (Zope) + at D (Zope)) - (x())) 2D| V v0,(2,))) + (o,L, + D2)
2
= (1 av)) (Iopt) (xx))) + 20x, v (+)()))) + (orLs + D2)D2
2
The proof concludes by using the definition of the stepsizes at.
13

---

Lemma 2. Let f21 denote the iterates generated by Algorithmm 1 or Algorithm 2 with stepsizes (ar120 given by at 2/ 2) for any t Z k. If Afssupptio holds, then each k. we have
t(t 1) (2) - (Fpp)) +
Σ (i+ 1)))))-----)))((( - -Fops)
s (k: + (0x(2)))) (Fopt)) + + - k) (8)
+ E V -
Proof of Lemma 2. By definition of tb, we have
Pe(xe+1)- (xp(Fpp)) = ot+1 I - GGre)) ((+)))((()((() Fopt)
(1+1((E+1) 11+1 (Tops) (or 0(+1) Fope).
To simplify the derivations, we introduce the shorthands h4 := (((x)) - D (((Copt) and
T = 2(L,0; + Lz)
4D
+
VΦ. - VDe(x))) - (o, 0++1) Fopt).
(t+
++2
Applying Lemma with stepsize a = 2/(1+2/ for all r 2 k gives the recursion h441 S +42 + for any t 2 k. This can be re-expressed as
(1+ 1)th, I(I 1)1,-1 ((1 + 1)91-1
for any & 22 ls + 1. Thus, for t 2 k + 1, it holds that
(t 1)the (Is + 1)kh2
Σ ((i 1)ih, (i 1))h4-1)
Σ (i+ 1)im-11- kE((]((]
(E(e](()
By definition of he and m/. and using the inequalities i/(i+ ( < 1 and 0;-1 S for i E [4] \ [M].
we arrive at
(t + (2.( (e((opt)) (k + 1)A (#x( 2 (2(p))))
S 2(0oLs + Lg) (t ExeriN
(F)(()))) Fopt)
EEENNN 4iD V (
which implies (8). This completes the proof.
Proposition 1. Let {2t denote the iterates generated by Algoritium I or Algorithm 2 with step- sizes (or J:zo given by 0it 2/(1 + 2) for any i " If Assumption holds, then for each k we have
(k: + 1)4: (TK) Fb (xopt))
2(0oLs + D2gg - k)
G(æz) Gopt
t(t + 1)
+(++1)
4iD Vo.11 VΦ, (
1(t+1)
at (at Eiep( + +1)1(1111100 t(t ((++1) 1)
+
Fopt
min F(x))
ZEX
and
(t+ (++1)to(F((x)) - Fope) +
Σ (++1)((0-110)))) - oF) - Fopt)
ve [E]]][[]]
< (Is + 1)k (#x(Ts) D (Zopt)) + 22 + L2) k) (10)
Σ
4iD M - V
14

---

Proof of Proposition 1. By definition of the function 4, the first term in (8) satisfies
1(t+11
=ttpp))))((((+)(((())))) - +t(+
(a()))- (aoe)-FF(rraaa F(ropt)). (11)
Since 2t E X, we have mingex F(x) - I F(xz) - Fopt for all t 2 0. Using this bound together with the identity in (11), we can further lower bound the left-hand side of inequality (8), and arrive at the bound (9). This completes the proof of the first claim.
For the second claim, since { he2 X is feasible in the lower-level problem, it follows directly that G(zz) 2 Gopt. Combining this inequality with (11) and (8), we obtain (10), which concludes the proof.
A.2 Nonconvex outer-level
When F is possibly nonconvex, we start by establishing a bound, akin to Lemma 2.
Lemma 3. Let {1e) denote the iterates generated by Algorithm I or Algorithm 2 with (os, rete20 given by at +t+ 1)- and at = <(t + 1) for z k, with < p S w. If Assumption I holds with the exception that F may be noncomvex, then for every t k, we have
(t + - (=x( s 2< sup =eX
(t oxF((E)) Eoi((a)
i=k
Σ
2D 2D
(o,Ls + Lg)
2( + 1)-0
Proof of Lemma 3. Using the definition of 0, = o. + G. for any 1 2 k; we have
FFF(1)41) G( S F(F))) + G(xz) + a vEX
min((.VF(())) + VG(x.)) xr)
+ +D V (+)))+ + (orLy + Dg)
2
where the inequality follows directly from (7) and by minimizing we E X. We emphasize that (7) does not involve any convexity assumptions on &, and relics solely on its smoothness. Furthermore, notice that for any E X.
min (FV)()) + VG(x)) (v S min oEX
(oVF(x)+ VG(z)) (v (v-
DEXope
I min eEp
(oVF(z) (u - x) + G(v)-G(a) - G(z)
= =o) - (zz). (z)).
where the last equality follows from the definition of F and g. Using the above bound, we may thus conclude that
oe F(F(()+)) + G(re+1) S a.F(xx) G(x,) an(oF + G(xx))
+ 2Da V.. v.,(x:))1 (o,L; + Lg) D2)
simple re-arrangement and using the definition of & then yields the bound a,(o,F(x,) + ((x))) < (F(z)) F(x ((x,) g(x141)
+ 2Da, V - v + (o.L, D2
(12)
2
Using the definition of ar and the fact that (t + 1)th < to - 1 for any & 2 0, we arrive at
(t + 1)) < ((x)) + (t + 1) (F F(x Fxt)
+ +2D v.,(2+)) + (o.L, + D²) 2(1 1)
15

---

Unwinding this recursion back to i = k, we obtain
(1 (1+1)=((2+1)+ S ha (xxx)
((i (((+)) F(+++1)))
E (x))
2D vØ; (x;(1) (0, + 1gg)
2( + 1)
Since S w, we have (i 1) 02 2 0. Therefore, we deduce that
Σ 11-1))o,(P(t) F(x++1))
((ax)((i+))00) - -(0 +orf(xx) - 1f
< sup [F())] =EX
Σ ((i+1)"0 - -oo + oz
+ (1 1) of sup [F(2)]
=EX
i=
< 2s sup ([=)]((++))))) o F(FR)
=ex
This completes the proof.
To establish asymptotic convergence of the proposed methods under nonconvex outer-level, we rely on an observation that function J is Lipschitz continuous on X. Lemma 4. If Assumption 1 holds, the function F as defined in (3) is L5 + max,ex [VF(=)]]- Lipschitz continuous over X.
Proof of Lemma 4. Given x, X, we observe that
Fly)
max eEXopt
{VF()) (y v)}
max ((VF(y) VF(x)) (y- vF() vF(x) (x-
"EXopt
max ((VF(y) VF(x)) -) VF(4) (y- vx()) T (x v))
DEXopt
max ([|VF()) - (F(z)|lly VF (x- VF ((x v)
max eEXapt
[Lyl|x
D D (F
D1 - 1
D max VF 1 F xEX
where the first and third inequality follows from Schwartz inequality, while the second inequality follows from the Ly-smoohhness of F.
By interchanging the role of and x, we deduce that
F(v) s (DDD) max IVF(2)]I) 11 x/}.
This concludes the proof.
B Proofs of Section 2
B.1 Proof of Theorem 1
We restate Theorem I with exact upper bounds sub-optimality gaps.
16

---

Theorem 1. Let {21 be the iterates generated by Algorithm 1 with = 2/(t 2) for any t 2 and regularization parameters {0r)120 given by o, := <(t + 1) for some chosen 0, p E (0, 1/2) Under Assumption 1, for any 1 2 1, with probability at least 1 - 6, we have
2(b + Lggls)D2 (t + 1)1
4c (A(L, Lg/s) + 3(0, 0g/s)) vlgg (8d12/8).
F(z)= Fapt S
(t 1)122-p
and
G(zz) Gapt
min(1,2(1 - p}} )
2p
(1=2p) FFgr - min F F(x)) 5 2
$ 14
+ Lg)
DEX
2
+4c (8 D2) D2 + 3 D)
V (1 2p)e + log (8d/6) (t+
where is some absolute constant. Moreover, with probability 1, we have
lim F(x)) Fopt.
lim G(xz) Gopt. E0000
The proof proceeds by applying Proposition with k In this case, the main random component in (9) and ( (10) is the term Eie(g
(f;-((1 We first derive a probabilistic upper bound for this term, then carefully set the parameters in Algorithm I to establish the convergence rate for both the lower- and upper-level problems.
We begin by bounding the gradient estimator used in Algorithm 1.
Lemma 5. Let {Iele20 denote the iterates generated by Algorithm with stepsize a = 22/(t + 2) for any t 2 O. If Assumption I holds, then for any t 1, given 8 (0, 1), with probability at least 1 - 8, for some absolute constant c, it (jointly) holds that
v /log(4d/0)
|VF, - VF(xx)) S (V +30,)
(1+ 1)122
(13)
/log(Ad/8)
VG, - VG(=))I S c + 30
(t + 1)
Proof of Lemma 5. The proof closely follows the argument in [4. Lemma 4.1]. In particular, the bounds in [4, Lemma B. I] still hold under the modified stepsize a 2/(t+ 2), instead of 1/(t+1) 1). The constant inside the logarithmic term changes from 6 to 4, as we now apply a union bound over two events rather than three. Additionally, the constants of the upper bounds is doubled due to use of the modified stepsize. We omit the details for brevity.
Proposition 2. Let (2e) denote the iterates generated by Algorithm I with oz = 2/ + 2) for any 2 If Assumption holds and the parameters (at are non-increasing and positive, then given 8 E (0, 1), with probability at least 1 ö, for some absolute constant e. and any t 2 1, we have
Σ sEId
|| Vo --0-4411100 (#--)
Sc(4(GoLL +1g) + 3( + og)) + 1)3/2 Vlog (8dt2 (8df2//)..
Proof of Proposition 2. Given i 2 1 and E (0, 1), by Lemma 5, with probability at least 1 5/i(i + 1), we have
i -
- S i(0,
- - +/ VG(x:-1)l)
i( VF FF VF + | VG(x,-1)I)
$ 02/2 (4(00L, + 0,)) Vilog (4di(i+1)/) +1/5)
17

---

Thus, using the union bound, with probability at least 1 1- 1/i(i+1) = =1- 1- for any i [t], we have
Σ v - [c({
-
Σ (V2 4.) - oo)) v log (8d12
S < + -g) 3(000, 0g)) (t 1)3/2 ViaaVlou log (8dt²
where the second inequality follows from bounding Eiero vi - (t + 1)3/2 via the Riemann sum approximation, and observing that 2/2 < 3.
To establish the desired convergence results for Algorithm I, we need to impose certain conditions on the regularization parameters {ar (20. stated below.
Condition 1. The regularization parameters fort12o are non-increasing, positive, and converge O. Condition 2. There exists I. TR such that
lim / ( [ (1- L. I-000
0++1
Condition 3. + 1)0 lo for any i and log(!) o(lot) oc.
The following parameters will appear in our analysis and convergence rates
(it (1+1))(0-11-0)))) + 2(00L, +Ly)
Fopt min min f(x) 1+ Papt-minFFe
C sup 121
(14a)
(t + 1)t02
(t + 1)0x
8c (4(ooLy + Lg) + 3(000, + og)
Cs == sup 121
Vlog (8d12/8)
(14b)
(1+ 1)1/20,
C = Co C.
(14c)
Ei + 1)i(0r11- oz)00
V == sup 121
(14d)
(++1)to
While it is not obvious priori, Lemma 17 in Appendix D.1 guarantees that these quantities remain finite for any parameter choice satisfying Conditions 1-3. In particular, Conditions 1-3 hold when a: = s(t + 1)-P for any p E (0, 1), which is what is used in Theorems and 3, and Lemma 8 provides explicit bounds this case. We now analyze the sequence {ar tezo Algorithm for the inner-level problem.
Lemma 6. Let (12 denote the iterates generated by Algorithm I with 04 = 2/(L 2) for any 2 O, and C& be defined as (14a). If Assumption and Conditions 1-3 hold, with probability at least - 5, it holds that
G(æz) Gopt S Caan.
(15)
for any t 2 O.
Proof of Lemma 6. Combining (9) from Proposition 1 with the probabilistic bound in Proposition 2, and after some straightforward calculations, with probability at least 1 8, we have
8e (A(OoL, L,) + 3( + o)) Vlog (8)
G(æ.) Gopt 5
11
+ 2(0oL + Lg)
Ponn-min
((O)
Eieng +1)((1--1--) (1+1) 1)
aet
(1+1)
=EX
By definition of Cs. the right-hand side is at most Csa, for any t 1. This completes the proof.
We next analyze the convergence of the sequence {2))22 in Algorithm for both outer- and inner- level problems.
18

---

Lemma 7. Let { h221 denote the iterates generated by Algorithm with ai = 2/(t 2) for any
t 2 O, and let Cs. V be defined as (14). If Assumption and Conditions 1-3 hold. then with probability at least - 6, it (jointly) holds that
F(z)) - Fopt 5 2(00L1 + Dg) +
4c ( + Lg) 3(000, + 0g)) Vlog (8dt2/0)
(1+1)0g
(++ 1)
G(z))= Gopt I C3(1++Vo
for any 1 2 1.
Proof of Lemma 7. Recall from Algorithm that we have defined
Se+1 = + 2) + 1)0++1 + Ejeltra + 1)((a,11- - -a;)
Se+1 (1 2)(1 + 1)0 Eiettty 1)i(0i-1--0)) o.),..)
Ze+1
thus 24 is simply convex combination of To. ......... Ty for every t 1. Therefore, F is convex, can apply Jensen's inequality to the left-hand side of the inequality (10) with h = 0, and after some tedious calculation, arrive at
F(2)) Fopt I 2(00bs DLg)
4iD|VA
VΦ, (z--1))
St
S
.E
Using the inequality S: 2 (++ t,o which holds thanks to Condition 1, and applying Proposition 2, with probability at least - 6, have
F(2)) Fopt S 2(00L, + D²) + 8c(4(00L, + Lg) 3(000, + to))) Vlog (8dt2/0)
(t+1)or 1)o,
(t + 1)
This completes the proof of the first claim.
For the second claim, we follow the same procedure. In particular, applying Jensen's inequality with respect the convex function G to the left-hand side of (15) and using the inequality S, (t (t-1)to,, with probability at least 8, we have
Co t(t + 1)
(t+ (++1))of+ + Σ 11)1))((--11-1
1)i(o,11 1)((0111-0))0) -o:)os
G(2)) Gopt
seld
The proof concludes by using the definition of V.
Lemma 7 establishes convergence result in terms of the regularization parameters (0.)20- The next lemma specifies an update rule these parameters and provides bounds on the quantities introduced in (14).
Lemma 8. Consider the sequence o, == <(t + 1) for t 2 and the quantities defined in (14).
(i) Ifp E (0, then torh22 satisfies Condition 1 and Condition 2 with L p. Furthermore,
C s (1 (1+2p)
Fopt
min zEX
F(x))
2(s + D.2
V
2p
min(1,2( -p}}
(it) If (0.1/2). then {az)ezo satisfies Condition 3, and we have
Os s 40 (s ( (1r+ [e) D2 +3 (1y - ())
2
log (8d/8).
(1 (p)e -
Proof of Lemma 8. As for assertion (i), it is trivial to see that the sequence for satisfies Condi- tions 1. validate Condition 2, observe that
lim / (at 10- -1)- = lim t +00 レ
((+++11)
P
(1+ -
-1)
= lim
lim
p.
0111
t t ++1
8-0 8
19

---

where the last equality holds as the derivative of y at 1 equals We next establish the bound for C. For t 1, it follows from the mean value theorem that there exists b, (t, + 1) such that
P (L+ 1) = -pb 10-1) - 1 =nb," (x+1) S pl (pt2))
Hence, we observe that
Eiety (i + 1)i(0:-1 - 04) S 2cp Eie(t) 1- S 2spt2=p,
where the first inequality is due to t + 1 < 2t and the second inequality holds because f- is an increasing function in t. This implies
Eien (i + 1)((os-1-00
2pt2-P 111 + 1)2-p S 2p.
(1+ + 1)lo:
Since min 1)o, c, obtain
Fopt - min F(x)) + 2(5L, + Lg) zEx
C c s1+
We next establish the bound for V. Using similar arguments, we observe that 1)i(o.-1 1))(ooi o.)o, s 25ppp Eie(o) 11-2p
Ei
If 1 - 2p 2 0, then (1-2p is an increasing function in and thus
Eien( + 1)i(a--1 - -0)0; S 2p(222(1=p)
Dividing both sides by 1(1 + 1) deduce that V < 2p. When 1 22p have
Ei 1)i(o,11 o,)o, S 2ps²
1 +
2 2p - 1)) 5² I-p
2-2p
where the first inequality is due to the Riemann sum approximation Eie 1 S 1+ s: 2dd Dividing both sides by t(t + 1)0² deduce that V S p/ p). thus the claim follows.
As for assertion (ii). it trivial to see that Condition 3 holds. We thus focus on bounding Cz. Using the fact that sup log(())(())))) ()/L 1/e, for any ( 2 1, we may conclude that
Sc (4(ooLs + D² + 3(000, + Dg) (1 + 1)1/20
v log (8dt2/5)
8c (1 (1(1,) L, L Lg D²+3 0f _g (1 D)
()++2))) V (t 1)1-)122p
1
2
log (t--2p)+ log (8d/5)
(1- 2p
< 80
4
( (
D2
o 0g D V (1 2p)e
2
+ -log (8d/8).
The claim then follows from the definition of Cs.
Proof of Theorem I. The first claim on the non-asymptotic convergence guarantee follows directly from Lemmas 7 and 8. As for the second claim on the asymptotic convergence, we prove a more general result: even if o, is not set as <(t + 1) the iterates of Algorithm 1 still converge almost surely, provided the regularization sequence satisfies the conditions in Lemma 6.
Lemma 6 implies that lim G(xx) Gopt with probability least 1 8. As 8 can be arbitrarily small, we may conclude that lim, G(x,) = Gopt. almost surely. This implies that any limit point of {2r in Xopt almost surely. Since F is convex, hence lower semi comiicontisuuus over X, and by definition of Fopt. we have lim inf F(x.) 2 Fopt almost surely.
Besides, by combining Propositions 1 and 2, we deduce that for any d (0, 1), with probability at least 1 - 5, we have, for all f 2 1,
4c (4(ooL, + L2) + 3(00o, + og))
Fxx)) Fopt <
Vlog (8dt2/5)
( 1)2/20,
20

---

2(00Ls + Lg)
+ Eiey 1)i(o,-1
oz) 1-11-)00---))(64 F(x:))
(t 1)
t(t + 1)ot
4o (4(00T.s + I2y) + 3(000, + +gg Vlog (8d12/8)
(t 1)+1)
2(0011 + Dz) Eisy( 1)1(01-1111111) - o4)
max oop F)
11+
1(1 + 1)
where the second inequality holds due to Condition 1. We claim that all terms on the right hand side converge to 0 as co. This is obvious except for the last term.
Recall that almost surely lim infe+oo F(xx) 2 Fopt- Therefore we have lim sup, ( Fappt F(x))) I 0 and hence lim4-+20 max{Fopt F(x)).0 0 almost surely. Applying the Stolz-Cesåro theorem and (33) leads to
Eiegg(1 + 1)((0;11 - 0i) max (oopt F(r.). O,
lim t0000
UL + 1)
almost surely. Then each term on the right hand side of the inequality converges co. follows that with probability at least --d 6,
lim sup(F(xt) - Fopt) s O. t+000
Thus, since this holds for any 5 (0, 1), it holds almost surely. In conclusion, we have shown that lim supt-poo (F(x,) - Fopt) S and lim inff->z((F(a))) Fops) 2 O, which implies that
lim F(xa) Fopt almost surely. This completes the proof.
L
B.2 Proof of Theorem 2
We restate Theorem 2 with explicit upper bounds on the stationary gaps and for a more general choice of p and w. Toward the end of the proof, show that the optimal parameters p 2/7 and w = 6/7.
Theorem 2. Let {zt]t20 denote the iterates generated by Algorithm with stepsizes or = 11+1)- -w and regularization parameters ot =(t + 1)-P for any t O. If Assumption I holds with the exception that F may be nonconvex, then with probability at least 6, for every 2 0, it (jointly) holds that
Ei + P)(TF(
Ei + +1-
< 4(11 - p) sup F(2) (t+ -1--1 2(1 ((1-)))(2ze)))) ((z) 1)m-1 + 2(1 201p)(cttt,,)00
+t 1)
<(1-w)
=EX
40(1 tdll-))v((akll
9u (50
+
(t + 1/7-w/2 / /log (4d(t + 2)22
<(1 2/2)
and
2t P (1-p-
+ =F(oo)) + (st. + T.g)) D2 21-2w
((x)) S sup [F(2) =EX
1
1- w
2cy 2012((2(5L) + Lg) D
3"
8) 1-3312 Vlgg (4d(t + g)2/0))))/0) (sa, + +
3"
1 w/2
where c is some absolute constant.
Proof of Theorem 2. Following the proof of [4, Lemma 4.1], for any that, with probability at least - -7); we have
easily show
V4. (..(z))) 2(0,,1 Lg)
3 -1 (o,0, (0,0)+ +00) (i (1+1)-u/² w/2
3
log
4d
m
21

---

Setting (++1)(+2)) applying union bound, and using the fact that o; 00 we have that
with probability at least - 5 Ei=o (++1)(++2) 2 1 -1-6 8, the following holds:
2D (x;(( + (0:L, + D2)
2(i + 1)
222c(2(sLs + 4,)
3"
0 + +gg)DD
4d(l + 2)2 +2)2
(sLg Lg)
3--1
log
D>²
(i+ 1)w/
6
2(i + 1)
2v 2/2c(2 Dg)D+ + 3
(sog og))D
4d(t + 2) log
(t + 1-=-1
1 w/2
8
(sbs + D²) w
(1 + 1)
Applying Lemma 3 with k- = 0, with probability at least - 8, we thus have
((1++))52 sup [(3)[(++))*++(((( Σ Fo:((tt(++1) + (skrthy) (2
=EX
1=0
(16)
( (++1) 1-w12
(so
log [d((11222) b
+
1-w/2
Note that the maximum in the definition of function F is with respect to Xopt not X. Therefore, F F(x:) can take both positive and negative values since x; E X. However, we can derive the follow- ing bound
(t+ 1)1-1
Σ FFF(())
S sup F(2) zEX
Σ o. S sup [F(z)]
seX 1 1
which further implies that
P + t w--P-
(sLs + L1) 11-2w
(xx)) S < sup FF()]
+ +cF(z))t
=ex
1 p
1-w w
2cv2(2((5L) +4y)0 + 3 (so, + [g))D 11 /1-30/2
[Ad(t + 2)2
7)2
log
(17)
1/w/2
5
We next focus on the upper-level problem. Since g(xe+1) 2 0. using (16), we have
+ (sLs + Ln)
Σ F(r,) s 2x sup
+ |F(z)](t + P <F(z))
1-w (t+ 1) 1-
zex
2ev 2(2(LLy + Lg) + Ls + +o0))D
[d(t + 2)2
(t + 1/1- log
1 1-w/2
Dividing both sides by Ei oi, and furthermore exploiting the bounds
(++2) (++2))PP-1 -
(t + 1)2-P
Σ oi 2
2
1-p
2(1 - p)
1=0
we arrive at Σ 0 F(x)
S 4(1 - p) sup [F())] 1)0-1 + 2(1 p) (Ix) 1)P-1
Σ/= os
=ex
2(1 p) Lij D2
(t (t+ 1)
<(1 w)
4c(1 4c(1-)) I,, D+ -t ( (s0
4d(t + 2)2
(t ((11))-w// 1)p-w/2 |log
w/1=
8
(18)
22

---

Both bounds involving G and F hold with probability 2 1 6. Hence, the first claim on the non- asymptotic convergence guarantee follows. Moreover, by optimizing over the parameters p and w, we aim to ensure that the right-hand sides of both bounds converge to O. To achieve this, we select p and w minimize the slowest rate with respect to to t:
1 w, -w, - 2w, 3w/2, 1,p 1,p w, - 7
min max (-p, p.w.eppS
which is realized by setting = 2/7, 6/7 as required. Substituting these values yields the bound presented in the main body of the paper.
As for the second claim on asymptotic convergence, we prove a more general result: If
max (-p, p w, w. 2w,, 3w/ w - 1,P 1. w.p p w/2] 0,
then it holds that
lim inf F(x:) = lim (zz)) = O. 1-+00
t-+00
Under this additional assumption and the fact that ( 0, deduce that lim4-+o (xx) from taking the limit on both sides of (17). From the continuity G, we deduce that any limit point of (2a) is in Xont- the continuity of F from Lemma 4 and the fact that F(x) for any x E Xopt. we deduce that lim inl F(x)) 2 0. Recall that
lim inf F(x;) = lim inf F(xx),
10000
100 k2t
and
Ei 2
oi o, infazs F(Tx)
Σi=o Oj
Ei=0 0,
Combining these observations and (18), have
Σ o; infa2: F(xx)
E/=0 oi
$ 4(1 p) sup |F(2)[(t + 1)- + 2(1 (( =EX
2(1 (5اا + D²)
(1 (1+1)) 11
s(1 w)
4e(1 4cl1-)) D
30 (co)+0,)) (1+1))-44) 1)/- log
[d(( + 2)²
<(1-w/2)
By the Stolz-Cesåro theorem (since E 10, Σ120 of = oo) and taking the limit on both sides of the above inequality, we obtain lim inf, F(x,) < 0. Since this holds with probability at least 1 for any 8 E (0, 1), should hold almost surely. Thus, we conclude the proof.
C Proofs of Section 3
C.1 Proof of Theorem 3
We restate Theorem 3 with exact upper bounds on sub-optimality gaps.
Theorem 3. Suppose the expectations defining F and G in (1) are from uniform distributions over finite sets of size [n). Let {2e be the iterates generated by Algorithm 2 with a = log(g)) for < 4. 04 = 2/(1 + 2) for any i 2 g, and a, := <(max (1, 1) for some chosen >> O, P E (0, and S q. Under Assumption 1, with probubility at least 6, for any 2 it holds that
F(z) Fop
max (F(xo) Fopus 0) (G(x)) Gopr)/s (L3 Lg
1/4 16 log [Gr2)
log(a)
(q +
23

---

2 + ( q) + (8v2t - 44) (Ly + La/s) D2 D2 /
10t2
+
(++ 1)t--P
G(2+)
-Gopt
x
(1 + 2p)
Papt
-min F F(x))
5 2(5Lg + Lg)
+
max F(x) 5(x0)) xEX
aEX
2
+ max m(x) g(xo)) + =EX
(Lys+ Lg) D²
+ +6
+ +log (16/8)
1 1-p
c(1 p)
1 e(l-p)
(1+
2p
+8V2(LJS + Lg) D2
+ log (16/0)
(t+
min [1, 1,,(11 11[11pp] p)}
Moreover, with probability 1, it holds that
lim F(x) Fopt.
lim G(xx) Gopt. 1000
The proof proceeds by applying Proposition with q. Unlike the proof of Theorem 1, here we have two main random components (9) and (10): (q 1)q (fg(Fg) oy (Zopt) and - We first derive probabilistic upper bounds for these terms, then carefully set the parameters in Algorithm 2 to establish the convergence rate for both lower- and upper-level problems. In the following we use the notation
EieMNa AiDIVV,,>
F(x)
Σ f(()), VE(M)
G(z)
Σ g((x).
T2
n
VE(N)
For simplicity, we assume that F' and G have the same size support, though our arguments are easily extended to the more general case. Also, given C [n]. we write
fs(x) = S
Σ f((x), IES
gs(x) = S
E)(a).
iES
We begin with a probabilistic bound on the gradient estimator used in Algorithm 2.
Lemma 9. Let (22 denote the iterates generated by Algorithum with a, = log(g)/ for any
0 < I < q and at 2/(1 2) for any 1. 2 q. Assumption 1 holds, then for any 0, given 5 E (0, 1), with probability at least 1 - ō, it (jointly) holds that
log(4)
VF, - VF(x))
< &&L,
Vlog (8/0),
V9S
(19)
log( q))
VG. VG(x))
< 8L
log (8/8),
VqS
provided that 0 S 1 < q, and
- (t-st) 5(1 + 1)(8 + 1)
vp. - vF(as) SB
log (8/8)
(20)
VG. - VG(Eo) D
(t-s,)
log (8/0),
5(1+ + 1)(st +
where 8t = gL///, provided that q.
Proof of Lemma 9. Ift st, we have VF, = VF(x,). Otherwise, let S, C. [n] be the index set of size S chosen at iteration and for i E S, define
1
4,4 = (Vf((x))) ( VF())) VVF(x,))))
24

---

From the update rule for 2t, we have ||, - ----1lll = aa-lllt--------1-1--0111 z1-1 S a for any t 2 1. As result,
2
|EE - 5 (lIV - vf((a--)) + [VF();)) - VF(
-
S Qt-1
for any t E {s+ +........ 9t + + and i E [S:]. For any t such that t o 8t, we have from the definition of FF, that
VF, VF(2)) - VF(2-1)) + Σ
Ct,
:E|S)
Thus, we deduce that
V.. VF.-v(().))
ΣΣ
Ex
+
+1 1 Eies, 6 is a martingale with bounded increments, we apply a concentration in- equality [41, Theorem 3.5] to get
Since Ex
A
P VF. FF(x)) 2n)= - 4exp
4 4
D2
0
9
If I $ q, we have
4L2
4L3 (log(1)
2
41. D2 log
(1) (1)
Σ
s
S
q
and thus
2
VF. - VF(ct)
22) S 4exp
1662, 1 (
If / g, we observe that
(s 1)2 S faf." (u + 1)2
du
4 sx) (t () 1
Σ
- =4
8
$=8+1
Then, have
x + 1)(s, + +1) 6413 8t)
vl. VF. VF(o>) 2)) < 4exp
Arguing similarly for VG,, we have
2 16L3 log (g)
P V 22)
s 4exp
if S1S and
P -C(x) 2n) < 4xxp
S² (o((t1)((s)) +1)
D4 st)
if / q. Given d (0, and 1 5 q, setting the right hand side 5/2 and solving for X,
have
log(g)
5
P VF. [FF 2 8L, D
Vlog (8/8)
VqS
2
and
|| &L
log(g) VqS
Vlog (8/6)
1
2
Applying union bound, we deduce that with probability least 1 8, (19) for > q, also deduce that (20) holds with probability at least 1 6.
holds. Arguing similarly
D
25

---

To establish convergence results for Algorithm 2, we replace Condition 3 with the following. Condition 4. oz da for 0 I 4. (t 1)0e+1 to for any 2 0, and log(t) o(tor) as 0c.
Note that dR is fixed during the initialization phase, and of in Condition is replaced by of in Condition 4. Unlike the proof of Theorem where we k 0, the proof of Theorem requires setting & q. We therefore begin by analyzing the sequence {ar generated by Algorithm over the first q iterations.
Lemma 10. Let frr denote the iterates generated by Algorithm 2 with a₁ = log(g)/q / any 0 st 9 and S 9. If Assumption 1 and Condition 4 hold, we have then given 6 E (0, 1), with probability at least 5 Eusics 1/ + 1) + for any 2 it holds that
(1 11- log(a) ) (Do (1-1o8(0) (F((o)))
(g((ig) (F(pp)t)
9
16tt
log(4)
+ (L + Lg)
2 + + log
8
Proof of Lemma 10. By Lemma 1, for any 0 S < we have
(L + Dg))
(3((:+1)= - (F(ppt))) S (1 (0:)(((3)))) (Fopt))
2
(21)
2Da V (x; 7
By Condition 4, we have og =... 02--1 and
Tg =... 00 where the implication follows from the definition of function 4.. Thus, we may conclude that o (1ig) (Fop)
Do 4g
$ (1 (fo((g()))) #o((Fopt) + (Lro0 + Lg) DRg
+ 2D V 1
V V
2
(Lyo0 + Ly) ag
< (1 a0) (Dolzo)) - Do((opp)) +
(1 - (o)
2
2m0
2Do (.,(2:) -0.
on) -
where both inequalities are direct consequences of Condition 4 and (21). Note that
11-00)11-1
4-1
g-1 -1- < _
(1-an - (1--))=
00
2=0
im0
where the last equality follows from convergence of geometric series. We thus arrive
(Lioo + Lg) D
(xg) (Epp)) S (1-ag))
(Do(zo) (o(po)))
1=0
(22)
9-1 Σ 2D 2D
Note that by the definition of 4; and the triangle inequality, we have
[V, v S ooll VF. Vf(2+)] -VG:--
Hence, applying Lemma 9 along with union bound argument implies that, for any 8 E (0, 1), with
probability least 1 5 Eosicg 1/(i + 1)(i + 2), have
Tog(g) V4S V log
8(i + 1)(i + 2)
(),()z)) - V < Σ 8D Lg)
8
k=0
Plugging the above probabilistic bound into (22), noting that 2 g and S = q. and using the definition of og complete the proof.
D
26

---

We next analyze the sequence (21 generated by Algorithm 2 after the first q iterations.
Proposition Let {ar)120 denote the iterates generated by Algorithm 2 with a, log(g)) / for any 0 S 1 < 4. 0r = 2/(L + 2) for any t 2 q and S 9. If Assumption 1 holds and the parameters {or)12o are non-increusing and positive, then given E (0, 1), with probability at least 1 1-8 EiE 1/i(i + for any I > q, it holds that
16t
104) VQ - I (8V2t 14) (ooLs + Lg) log
(23)
Proof of Proposition 3. For any i 2 1, we have
- (a.-1 V VF(+;-1)|| + |VG VG(
S (0o VF - VF(=,-1)] ||V VG
(24)
Given d E 10 and g < v 2g, by Lemma and the incquality (24), with probability at least 1 - 8/i(i 1), we have
1 q
8i(i + 1)
i|| V4. V < 8(ooLy - Dig
log
qi(a + 1)
8
Di
88li +
S 8(ooss - Lgg
log
q
Hence, if q <ts 2g, with probability at least 1 - 8 Egsise 1/i(i + 1), have
Σ qsiis
| V -
Σ
8(ooLy + Lg) Di
/
log
16t2
8
qsigt
16t2
I (ooLs + Lg) 10)1 log
8
Egeige& i S 22t 9/2 for all t S 2q. Similarly, given 8 E (0, 1) and i 2g. by Lemma 9 and the inequality (24), with probability at least 8/i(i 1),
where the second incquality holds 1
we have
V - (0.-( 8(ooLy + Di
Si(i + 1)
log
Vilal(i - 1)/91 +1)
8
i
+ 8i(2
8(00Ls Lg)
log
8ili + 1) 8
88V2(000L + Izg) 1gg) Vlog log
where the second inequality follows since qi(i- 1)/g] +1 > i q, and the third inequality follows since i/(i-q) < 2 when > 2g. Thus, if > 2q, with probability at least 1-8 E2 1/i(i+1) =
1 - 8, we have
16t²
Σ 2
V V
Σ 2qeist
8V2(coL + DD) log
16t²)
= =8V2(ooLs Lg D (o((tt2g)/// 20) log
5
For t > 2q, with probability least 1 8 Eneiss 1/i(i 1), the sum over all g i is thus
Σ - V (
gsist
27

---

16t
16t2
400/ log
+ 8V2(0oLs Lt) - 20) 108
-8V2t- /0/2t-(16V2 - 1662+ +2))) (ooLs + Ly)DD/100 Vlog
16t²
16t.
(8v2t- 40) (OOL, + Lg) V
log
Therefore, regardless of whether q < - 2g or > 2q, (23) holds.
The following parameters will appear in our analysis and convergence rates
(1 1+
+ 1)((0-11-5))
Pops
min F(x)) =EX
1)toe
C = sup 129
(25a)
2(00bs + (L) Q)
(t + 1)to,
(a+1) (ax())((oo)) (Lrrooo (3 161/11o 1662
log(a)
(+++)
Cāg sup 129
(25b)
(o0 log
(++1)
Cā.9 = Co.9 + Cg:
(25c)
ExergMa + 1)i(0,11 - o;)0;
Vg == sup 124
(25d)
+t+ 1)to?
Lemma 17 in Appendix D.1 guarantees that these quantities remain finite for any parameter choice satisfying Conditions 1-2 and In particular. these conditions hold when or <(t + 1)2 for any p (0, 1), which is what is used in Theorem 3. We now analyze the sequence {xt in Algorithm for the inner-level problem.
Lemma 11. Let [2:h120 denote the iterates generated by Algorithm 2 with = log(g)/9 for SI < qoa, 2/(1 4 2) for any 2 g, q, and let Co.g be defined as (25c). If Assumption and Condition 1, 2 and 4 hold, then with probability at least - 5, it holds that
G(zz) Gopt I Cs
(26)
for any t 12 q-
Proof of Lemma 11. Combining (9) from Proposition I with the probabilistic bounds in Lemma 10 and Proposition 3, and after some straightforward calculations, with probability least 6, have
G(zz) Gopt
( 16 log 1662
(q + max (fo(zo)
(T.j00 D2
log(4)
(1+1))
2(00L, +g) ②) (8v2t - 4g) (ooLg + D2 V log (1612)
(++1)t
+ (Fope + min F(x)) x
Eiel( 1)i(0,-1-0))
oct
1+
Here, the right-hand side is most Cs.g- and therefore, G(æx) Gopt I Cag for any t 2 g.
We next analyze the convergence of the sequence {=:):20 in Algorithm 2 for both outer- and inner-
level problems.
28

---

Lemma 12. Let frete20 denote the iterates generated by Algorithm 2 with = log(g)/g for
0 stt < q a₁ 2/ 2) for any 2 9, S 9. and let Co.g and Vg defined as (25).
Assumption and Condition 1, and 4 hold, then with probability at least 1 - 6, it (jointly) holds that
F(z)= Popt
(1 1) mmax (fo(20) (oo()ott) + (Lyon Lg)
16x2 + + log (1022)
log(a)
(1 (1-1)) 1)
2(001s + +1g D2)
②) (8v2t - 4q) (ooLs Dy) 1og (2022
(1 1)
G(zz) Gopt S Co +V)o0 for any t q.
Proof of Lemma 12. Recall from Algorithm that we have defined
Si+1 == + 2t + 1)0e11 + Eiet+r + 1)((a-11-1 1
1 (t + 2) + 1)04+1 + EiELL (1+))(00-1111 10))01-1-011z.))
2++1 == Se+1
thus 2, is simply a convex combination of ro...., It for every 1 2 q. Therefore, as F is convex, we can apply Jensen's 's inequality to the left-hand side of the inequality (10) with k q, and after some tedious calculation, for any t 2 q. we arrive at
2000bg + Lg)
(q + 1)g ( (x)g)) $ (x(op))))
F(a)) Fopt I
St
S.
4iD 4iD V4
Vo, 10
KE
Using the inequality Se 2 (t + 1)to, which holds thanks Condition 1, and applying Lemma 10 and Proposition 2, with probability at least 1 8, we have
F(z() Fopt
(q + 1) max (Fo(zo) Po(xopt)) 03 + (L Lg) (1 16 16/log log (1662) log(4)
(t - 1)to:
2(00L, + Dt) 4) + +8v2t - 4g) (ooLs D2 V log (20
1161
(t + 1)ta,
for every 2 This completes the proof of the first claim.
For the second claim, follow the same procedure. In particular, applying Jensen's inequality with respect to the convex function G' to the left-hand side of (26) and using the inequality S₁ 2 (t-1)to,, with probability at least we have
Ca.
(1+1)1OO
G(zz) Gopt &
(i+ (1+1)i(0;-1 -01)0, sE(t//a
Σ
+
The proof concludes by using the definition of Vg.
for t 2 0 and the quantities defined in (25). If p E (0, 1), then the sequence (0r)120 satisfies Condition and with L p. Furthermore,
Lemma 13, Consider the sequence ==
C s (1+2p) Fopt - min F(x)) + 2(cL, D2
2p
Vg S min(1,2(1 - -p)
xeX
29

---

and
maX g(ø) -g(2))
Co. I max F(x) - f(zo) +
DEX
Lig + L
2
D
+ 1 c(1 pp)
+ llog (16/6)
1 -
+ +8V2
L3 4 Lu D2
c(1-p) + log (16/0).
1
Proof of Lemma 13. We observe that Cy. Va be bounded from above by C, V defined in (14)
under the conditions in Lemma 8. Therefore, focus on Co,g for the remainder of the proof. Using the basic inequality log(x)/z & 1/e for any x > O, observe that for any 2 q
(g 1) [aax (x)())) Po (Fopp))) 0} + (L,00 + Lg)
1/2 +16 log (2012)
log(g)
(t + 1)to,
1/2 / log (1612) max (Do(ro) Po( 03 + (L,s + Dg)
log(t)
ctl-p
We have
(o ((ooo)-Po(ooop)) (oope)) = (f(zo)
GGope Is
max F F(x) Fopt mEx
+max g(x) GGptt
zex
which implies
max (Po(xo)= - Po Fo(
<s max F(x) - Popt + max mmxxg()) Gopt.
51--1
We also have
log(t)
2 log(t(2-p)))
2
(11 (1/2
1
(11-p)/2
c(1 p)
and
16t
log(t" -P)
log
log (16/6) + 1- t1ー
W log (16/5) + e(1 p)
-1
8
t セ1ール
Therefore,
(LJs + D2)
1/2 2 1-1611o
log (2612)
log(t)
5t
1 L Lg D
1
+ 16
+ log (16/8)
2
e(1 - p)
Similarly, we have
(8v2t- 49) (ooLs + Dg)D2
1612 log 8
<882
[1 Lg D 1 e(1 p)
log (16/8)
(t+ 1)to,
This concludes the proof.
Proof of Theorem 3. The first part is immediate consequence of Lemmas 12 and 13. Thus, devote this proof for the second part by proving that a slightly more general result that as long as Conditions 1-2 and Condition 4 hold, the asymptotic convergence remains.
Lemma 11 implies that lim,-520 G(vx) = Gapt with probability least 1 8-6. As 8 can be arbitrarily small, we conclude that lim;-+o G(Iz) Gopt. almost surely. This implics that any limit point of
30

---

h22 is in Xopt almost surely. Since F is convex, hence lower semi-continuous over X, and by definition of Fope: we have lim inf,- F(x,) 2 Fopt almost surely.
Besides, by combining Proposition 1, Lemma 10 and Proposition 3, with probability at least 1 - 6, we have
F(x.) - Fopt
(q + 1) max (Bo(2o) - Bo((Eop)) + (L,00 - L2) +
{ + 16 log
1662 log(4)
8
0+-1)1x
2(00hs + [g) 4) + (8v21 - 4q) (aoTis + +Tgggg (2g) V log (2642)
+
(t+ 1)to,
Eiegg 1)i(0;-1- - oz) max Foott F(x.).0) +
1(1 + 1)
Similar to the proof of Theorem 1, all terms on the right-hand side converge to 0 as -> xc, implying
that lim su (
(xx)
F Fopt) S 0 which holds with probability at least 1 - 5 for any 8 E (0. 1).
Thus, lim sup, (x( Fopt) S almost surely. Combined with lim inf, (F(a.) Fop.) 2
O, this yields lim P (x+) = Fopt almost surely, concluding the proof.
C.2 Proof of Theorem 4
Here, we restate Theorem 4 with exact upper bounds on stationary gaps.
loglg + 1)/(a + 1) for any S 1. S % at 1/(t + 1) for any I. > q and = q, and regularization parameters o, <(max/t,q + 13 + 1)-P with p 1/ and w 3. If Assumption 1 holds with the exception that F may be nonconvex and the sequence {,ee)20 is defined as in (4), then with probability at least for every t 2 q. it (jointly) holds that
Theorem 4. Let {are J120 denote the iterates generated by Algorithm 2 with stepsizes
Ei=o BiF(xz)
G((o)) Gapt (25(g + 1) + 5(g + 2)-P)
[[()]]
(a + bb!
sup =EX
E/=0 Br
(q (q+11] 1)
(ooLs + D2 11) 2(q + 1) --
88(1 + 2)2
1 16
log
(a + bt)
8
8(00L, + D() --
8(t+2) 2)2
log
(a + (a+bel -
1- w
+ 2s sup [[()][[++ + 1 (a+bbe be b() =EX
(sL, + D2) (t + 1) - (a + bt pp-)
G(aa) - Gap
g(xx) 5
(q + 1)1-- + (2<(g + 1 P + 5(g + 2) 2)-p)
sup FF())
1"
=EX
(shr + Lg) log(g +1)
[8(g + 222
1+ 1+16 log
t-
2(q + 1)2-w
6
8(s + L.g) D22 11)))---------- -02--op-
8(1+ +
(sT.f + D22) f1-2w
log
1-w w
8
1 1-w
(s(g+1)up
(1 1)2-P g1-p)
+ 24 sup F[))][+++ =EX
+
t- w
sup [F(2)), =eX
1 1- p
where B, 's are defined in (4) and a, b are constants that satisfy
(g 2)+ P
-1
(q + 1) 1-p
a + bt
3
1-
31

---

The proof relies on several intermediate results. We begin with the following probabilistic bound. Lemma 14. Let (zeltzo denote the iterates generated by Algorithm 2 with a4 o any S t S and 04 ()++1)=+ with w for any 9. If Assumption holds with the exception that F may be nonconvex, then for any t 2 0, given E (0,1). 1). with probability at least 1 - 6, it (jointly) holds that
a²9
VF, - VF(aa))
- DL
V /log (8/8)
(27)
a²9
VG, - vG(x))
s VV
v log (8/0),
provided that 0 St < q, and
(t2 (1-22
8 -22
- VF(xa) VF(t))
s 1L
Vlog (8/0)
S(1 2w)
(28)
(t (1-2w s -!-2
| VG(a>)| |GGa)) s
&8LgD
Vlog (8/5),
S(1 2w)
where 8t = g//4), provided that >>
Proof of Lemma 14. Recall from the proof of Lemma 9 that, employing the concentration inequality in [41, Theorem 3.5] yields
X2
VF. VF()))
22) S 4exp
4 22.=++11
4L3
If 1 t < q, one can easily show that
X
P VF. VF.- - VF(x)) 22) s 4exp
16623 D2
If t > 9, we observe that
Σ 0
a = Σ
< 4
pt du
4
(8) 1-22 (1-2m).
82w
82w
2u
6 sma+t1
sma
Thus, have
P VF. VF.a)) 2n) < 4exp
2 - 2w)
(2 (11- 88 20
Arguing similarly for VG., we have
p PTG.-ven (V.-ai))) 22) s 4exp
X [16L D2qa
0 < t and
X²S(1 2w)
V.. ( VG(2a) 2^) s 4exp
6413
2w
if t > q. Given d E (0, and 1 S t g. setting the right hand side 5/2 and solving for À yields
|22g VF( |FFa>1( 81, Dv
/
5
p VF.
Vlog (8/8)
5
and
| |VC vG(zi)| DL
aa9g S
5
P
Vlog (8/8)
2
Applying union bound, we deduce that with probability least 1 5, (19) holds. Arguing similarly for > q, also deduce that (20) holds with probability at least 1 6.
D
32

---

We next analyze the sequence h22 generated by Algorithm over the first q iterations.
Lemma 15. Let { (x 3e20 denote the iterates generated by Algorithm 2 with at = for any S S q and S = If Assumption I holds with the exception that F may be nonconvex and Condition 4 satisfied, then given E (0, 1), with probability at least - Losigo 1/(i 1)(i 2). any S t S q + 1, holds that
t-1
( S (1 - aa)g((o)) + 200 sup [F(2]
00 Σ (1--a)- aF((x)
=EX
1=0
(ooLs + Lg)DPa
8(( + 2)
1+ 16 1 log
Proof of Lemma 15. Applying the bound (12) and after a straightforward re-arrangement, under
Condition 4, for any 0 S sistt we obtain
((x++1) s (1 - (),();)) + (F((())))) aF(x)) - F();+1))
+ 2Da (z,) V (L Dgy)
2
Given 8 (0,1), 1), we apply Lemma 14 deduce that with probability at least - we have
2).
((x++1) < (1 a.) + 0o (())) oF(x;) ((((=)))F(FFt1)) F(2++1))
8(i + 1) +)((++)+)) 2)
+ (L + (L,oo+L,)D'O Ly?
+ + D') |log
2
Applying the union bound, for any 0 S S q. with probability at least 1-6 1-dEosis 1/(i+ we obtain
((=4))(1-
oo (F(x;) aF(x.) F(244))(1-a)) (1
i=0
+1 2
)== 1 log 8(i+1)(++)) + (LootthngDDa (1--)
Using the geometric series bound Σ El (1aa11----- 11/a and observing that
(F(x;) - F(xit)))(( - -a)²
F(x:) ((1 aa) - -(1-a) + F(zo)(1 - a) F((441)
=E[t]
Σ (1=(x)(1-aa)) + F(xo) a)- F((4411
kE(!]
sup [F())
Ekejg a(1 at- (1 a)* +y)+1 2sup [F(2)]
=
conclude the proof.
We finally analyze the sequence (z1h22 generated by Algorithm 2 after the first y iterations.
Proposition 4. Let {atht20 denote the iterates generated by Algorithu 2 with aN = a for any < < a₁ = (t + 1) with w > for any t 2 q and = q. If Assumption holds with the exception that F may be nonconvex and the parameters {0r) are non-incue non-increasing and positive, then given 8 E (0, 1), with probability at least 1 - ō - (+41)6-2)..00 any t > q. it holds that
8(00L, + D(t q)'-m
8(t + 2)2
Σ [e
VΦ.- V |
log
(29)
w
5
33

---

Proof of Proposition 4. For any i 2 O, we have
14; ( - VF VF(z:) + |IG; VG(r))l)
(00l VF. - vF(x))] + | - Vl(x))l)
(30)
Moreover, for any i > g, by the mean value theorem there exists G; E [+ i] such that
(i (i1-2w 8 21-2w)
210 (1 8:) - (i ))2
9
(1 2w)
Given 6 (0 and 5/(i + 1) + 2), we have
q, by Lemma 14 and the inequality (30), with probability at least 1
v (2,(1 S 8(00I.g + Ig)D
/ loo 1((+
(i - 9)m
Hence, if > q, with probability at least 1 - 5 Egeist 1/(i 1) + 2), we have
8(0nls + Lgg)
8(i 1) + 2)
Σ
VΦ,
(o,(2:))
log
(i - ()-))
5
q<iSE
qsise
8(0nLy Dg 1)'-
881 + 2)2
log
w
where the last inequality follows from the Riemann sum approximation.
We now instantiate the regularization parameter and analyze Algorithm 2.
Lemma 16. Let {a+ ( denote the iterates generated by Algorithm 2 with O2 = a log(q + 1)/(g + 1) for any 0 S t S q, Ot = 1/(t + 1)"e for any t q and S = q. If Assumption I holds with the exception that may be nonconvex and Condition 4 is satisfied, then given E (0, 1), with probability at least - E0siet1 1/(i + 1) 2), for any >> q + 1, it holds that
tn (((())) < ((
(g 1)1- + (2<(q + 1) + 5(g 1)
sup [F(2] 2EX
+ (ooL, + D22 log(q 1)
8(q + 2)2
1 16
log
2(q + 1) 1)
8(sL, + W² - 11 --
8(t ((t+ + 1)2
(sLy + D2)
+
log
+
w
8
1-
1-1
+ 2x sup F(2)][ -oolg + 1)th Σ aF (1=)))(1)))+
Σ o.F(1.).
=EX
1=
Proof of Lemma 16. By Lemma 3, for any t 2 + 1, we have
(t (1+1)=()111) s (q + ()=((1)41) 2x sup FF(2)[(t 1 00t1 =eX
2 (2, (o,L, D2)
Σ F(F(( +
2(i + 1)20
i=
i=q-1
Applying Lemma 15, with probability least 1 5
Evsis 1/(i 1) 2), have
g(zg+1) < g a+1 ((xo) + 20 sup F(2)) 0o Σ
aF (xxx)(11 -1)
sEX
i=0
+ (ooLs + D2) log(( + +1)
8(q + 2)2
11 16
1 1
log
2(g + 1)
8
34

---

Combining these two bounds with Proposition 4 then yields
(L+ + 1++)((())+)) v (q 1)1 ((5)) + 25 + 1)-
sup F(z)] =EX
(ooL, + Lg) +
8(q 8 + 2)2
1 1+
16 1616
log
2(g + 1)2-
8(0obs + Lg) - -)2-
8(1+ + 2
log
1 w
5
|F(2)((L + 1) + (sL, Lg) 1 w
24 sup =EX
(1+ 1) 1)--w + a
- 0o + 1)0²
oF (x:))) - (1))(1-0)011 a)0- - - Σ oxF(xi).
1=0
1=9+1
The proof concludes using the simple inequality 0 0.+14 (((++) S <(g + 2) sup:ee [F(z)]
We now well-equipped to prove Theorem
Proof of Theorem 4. We first focus on the terms involving F(z)) in Lemma 16. Note that the func- tion F is defined with respect Xopts not X. Therefore, F(x,) can take both positive and negative values since x; E X. However, we can derive the following bound
cola + 1) Σ aF(x))(1
Σ FFF(),))
1=+1
5 sup =eX
[F()] (106 + 1)tH Ei a(1 - a) + Eim4+1 σi)
[F(=)] 1000 + 1)t0 (1 (1 - a))+t)) + Σوe oi)
sup =Ex
[F())] (5( 2) 1) (1 a)ot2)= + (1
sup =eX
1-p
supup [F(2) ((q 1) ( xeX
where = log(q + 1)/(q + 1). and the second and third inequalities follow from the geometric series bound and the definition of o, Using this bound together with Lemma 16, we arrive at
g(zo)
((xx)) < (g 1)1-w + (2s(a + 1) s(g + 2) 2) sup F(=)]
=EX
(ooLy + D2 log(g + 2(g + 1)
[8(g + 2)2
1 16 log
t-
(31)
8(sI. + Lgg D2(1 -1 1- 1---
8(1 + 1)2 log
(sLs + D2) 1- w
11-20
1- w
8
(slq-1)0-P (1+ (1+1) 1-p
-t-p
24 sup PF())|(+++ =
sup [F(i)
zeX
We next focus the upper-level problem. Since ((x+41) 0, using Lemma 16 and the definition of the sequence { (120 we obtain
1
Σ 3,F(z)) < (q 1)1- g(20) + 2<(q + 1) sup +s(g 2)-P)
sup [F())
sEX
=EX
(o + D2lgl
(8(g + 2)²
1 16 log
2(q + 1
8
35

---

S(ooLy + Lg) - q) 1-
8(t + (8(t+2)) 2)3
log
6 [F(z)](t+ 1) (cL, Lg)
1-
+ 2x sup
(t + 1-+11=0 1) 1-
=E
Observe next that
8' (q + 1)
Σ 3 z
1)a (1 a)tt1) +
1 p
1-P (g 1 25 (q 2) P
+
bt
1 1-p
where a and b are constants defined to make the equality hold. Combining these bounds, we arrive at
Σ 1= FxF())
((
(q (Q+11J= 1)2- ((++))-
+ (20(q + 1) +(q
sup |F(2)) =EX
(a+ Dt -1
Ei-0 3r
log( (ooLs + 1og(g))
8(4 + 2)²
1+ 161 16
log
(a (a+ mt
2(q + 1) 1-
8
S(0oL, + Lg) -1llt--)1-- 1-
8(t + 2)2
log
(a + ++-bt bt
1 w
+ 25 sup |F(z)[(t + 1) (a bt br--p)-1
sEX
(sL, + Lz) (t + 1) (a +a+ bt bb
--
(32)
Both bounds involving and F hold with probability least 8. We want the right hand side of both bounds - 0. In order to guarantee this, we choose to minimize the slowest rate in terms of t:
min max {p- 1, w 1.p w, w. p. 2w,, - p} 4' Ppw
which is realized by setting p = 1/2, w = 3/4 as required.
As for the second claim on asymptotic convergence, we prove more general result: If
max {p- - 1, 1, -
2w, - p} O,
then the asymptotic convergence holds. Under this additional assumption and the fact that (1r) 2 0, we deduce that lim G(x,)= from taking the limit on both sides of (31). Recall that
lim inf F(x)) 8-000
lim inf F(xx).
t-+00 R2t
and
EL 3,F(1;)
Ei Bg infazi F(Tr) El.o 35
Σ1 B
Combining these observations and (32), we have
Dign a Br infuzi F(æN)
Ei Bi
((zo)
(a 1)1-w + (2s(g + 1)w-D + s(g + ")
sup =Ex
[F(z) (a + bb(
+ (ooL, + (Lg)) log(a + 1) (
8(g + 2)2
1 16
log
(a + bt bt!
2(q + 1
8
36

---

Slooby Lg) q)- 1-
(8(t + 2)2
log
(a (c+b6)
1 w
8
+ 25 sup [F(z)[[t+ P (a t bt be (sL, + D2) D2
1- (t+ 11 ba+
=E
By the of the above inequality, obtain lim infe F(xx) I O. Since this holds with probability least 1- for any E (0, 1), it also holds almost surely. Due to the fact that any limit point of {2t h is in Xopt. the continuity of F from Lemma 4 and the fact that F(x) for any Xopt, deduce that lim inf F(t+) 2 0. Thus, we conclude the proof.
theorem (since p E (0, E120 3t = oo) and taking the limit both sides
D Additional Discussions
D.1 Finiteness of constants
The following lemma establishes that the quantities introduced in (14) are finite.
Lemma 17. If Assumption I and Conditions 1-3 hold, then C, Os Cs defined in (14) are finite. Furthermore, if defined in Condition 2 is strictly less than 1, then V defined in (14d) is finite.
Proof of Lemma 17. We first show that under Condition 1 and Condition 3, when the limit in Con- dition 2 exists, the parameter L satisfies < L S 1. While is trivial to see L 2 thanks to Condition L < needs some justifications. For the sake of contradiction, suppose L 1. Then for some sufficiently large I, we have
OL> t+1 = (t+ 1)0+4 < to
>1
J++l
This further implies
(1+ 1)0f S (1+ 1)0 S lo?
which always contradicts Condition 3. Thus, have 0 S L under blanket assumptions.
We now show that C is finite. Observe that
11+0000011-00
(I T- (t 1)( -1
lim t0
lim t(t 1) t-00
(t + 1)to,
1) 2-
where the first equality obtained by diving both the numerator and the denominator by to, and the second equality follows from Condition 2. Moreover, we have
(t + 1) - -0) lim Evero (i + 1)i(o,-1 -o;) Eie
1)i(o; (1t))oo-++ -;)
lim 1000 (1 1)lo, 1(1 1)0,-1 10000
(1+ ()11) 1(1 1)0e-1 (tely + 1)i(o;-1-00 o1)
lim
(t 1)to:
where the second equality follows from the Stolz-Cesàro theorem. This yields
lim Eiety + 1)1(0r)(-11000 0,)
L
Eieje (1 1)i(0s-1 -0;)
sup E21
E (0, (33)
(t+ 1)to
2-L L
(1+1) 1)ta;
Using Condition 2, we have min (t + 1)o, 0. Thus, C is finite. is also straightforward to
verify that C3 is finite by Condition 3. Consequently, C9 is finite as well.
To conclude, show V is finite. From Condition 3, (lor) and {(t + 1)00f) increasing and diverge to oc. Note that
Eieno (1 + 1)i(a1-1- - o:)a: lim
(t+ 2) 1)(a, 041100+11
lim
4-900
(t + 1)to?
1 (t (t + 1)02 (++1)to2 1)to?
(422 t
0 -
lim
ae+1
L
2
a
a
+ +1)
2 a
2(1 T.)
0141
37

---

where the first equality is implied by the Stolz-Cesàro theorem, the second equality is obtained from dividing both the denominator and the numerator by (t+ 1)0 and the third equality comes from Condition 3 and
lim
ot =1
lim t-000
oz - 1) =1.
-1)==
10000 0++1
0(+1
Note that L/2(1 L) E oo) since
[0, 1). Thus, V is finite. This completes the proof.
The following lemma establishes that the quantities introduced in (25) are finite.
Lemma 18. If Asssuupttion 1, Condition 1, 2 and 4 hold, then Cg. Co.g defined in (25b), and (25c) are finite. Furthermore, if L defined in Condition 2 is less than 1, then Vg defined in (25d) is finite.
Proof of Lemma 18. The proof follows a similar argument to that of Lemma 17. Details are omitted for brevity.
D.2 Over-parameterized regression: implementation details
The implementation details are as follows. For IR-SCG, presented in Algorithm 1, we set of = <tt + 1)-1/4, where 10, along with a = 2/ + 2). For IR-FSCG, presented in Algorithm 2, we set S q = [vn]. a. = (max((..) q) + 1) -1/2, where ş = 10, along with ar = 2/(1 + 1) for every / 2 and 0z log(g)/q for every < q. Our linear minimization oracle involves optimization over an f--ormm ball, which admits an analytical solution; see [26, Section 4.1J. We compare our proposed methods against SBCGI with stepsize 7t-- 0.01/(L++ 1), SBCGF with constant stepsize % 10-5 (both using K, 10 1, S = [vn)),
(n. = 10 (t 1)3/4) and short stepsizes (% = 10 ( Pr = aR-IP-SeG with long 0.5),
and SDBGD with long (?r 10-2) and short (7+ = 10 stepsizes. We initialized all algorithms with randomized starting points. For SBCGI and SBCGF, we generated the required initial point v' by running the SPIDER-FW algorithm [57, Algorithm 2] on the inner-level problem in (5), using stepsize of To 0.1/(t + 1). The initialization process terminated either after 10a stochastic oracle queries or when the computation time exceeded 100 seconds, with the resulting point serving as zo for both SECGI and SBCGF The implementation of these algorithms rely certain linear optimization or projection oracles. For SBCGI and SBCGF, a linear optimization oracle over the l fo-morm ball intersecting with half-space is required, which we employ CVXPY [11] solve the problems, similar to the implementation in [4, Appendix F.1]. To compute the projection onto the feasible set required for aR-IP-SO we used [13, Algorithm 1]. To approximate the outer- and inner-level optimal values Font, Gopt, we again employ CVXPY to solve the inner-level problem and the reformulation (2) of the bilevel problem.
D.3 Dictionary learning: implementation details
In our experiment, we obtain A, A', X from the code provided by Cao et al. [4] with n n'' 250 and p = 40, q = 50 In addition, we also choose 6 = 3. For IR-SCG, presented in Algorithm 1, we set o, = <(t + 1) 2/7 and 0₁ = (t + 1) where = 0.1. For IR-FSCG, presented in Algorithm 2, we set
q = LVnj. o, = s(max[4, g + 1) + 1) 1112, where 5 = 0.1, along with a; = (L + 1) 3/1 for every 2 q + and a₂ log(q + 1)/(g + 1) for every S q. In both experiments, the linear optimization oracle over the fn-m ball admits an analytical solution; see [26, Section 4.1]. For performance comparison, we implement four algorithms: SBCGI [4, Algorithm 1] with stepsize % 0.1 + 1) 22/3 SBCGF [4, Algorithm 2] with constant stepsize Tt 10-3 (both using K, 0.01(t + 1) 1 = = Vn)). aR-IP-SeG [27] with long (7+ 10-2/(t++ 1/3/+1)3//4) and short stepsizes (7+ 10-+/(t+1)000 P: = (t+1)1/44,) r 0.5), and the stochastic variant of the dynamic barrier gradient descent (SDBGD) [21] with long (7/- = 10 10-2) and short (% = 5 x 10-3) stepsizes. We initialized all algorithms with randomized starting points. For SBCGI and SBCGF, we generated the required initial point z/j by running the SPIDER-FV FW algorithm [57, Algorithm 2] on the inner-level problem in (5). using a stepsize of 7: 0.1/(L + 1). The initialization process terminated either after 108 stochastic oracle queries, with the resulting point serving as 2o for both SBCGI and SBCGF. The implementation of these algorithms rely on certain linear optimization projection oracles. For SBCGI and SBCGF, linear optimization oracle over
1)33/1
38

---

the mn-morm ball intersecting with a half-space is required. which we employ CVXPY [11] to solve the problems, similar the implementation in [4, Appendix F.1]. To compute the projection onto the feasible set required for aR- IR-SG, we used [13, Algorithm 1] to compute projection on E norm ball and projection onto l norm ball admits an analytical solution. To approximate inner-level optimal value Gopt. we again employ CVXPY to solve the inner-level problem.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have reviewed all claims made and checked that they accurately reflect the contributions and scope.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We describe explicit limitations throughout the work, and in particular in the experimental section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "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 au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
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 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.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
40

---

Answer:
[Yes]
Justification:
All claims are precise, and are either referenced, or proven in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, all details are provided in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
41

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Code is provided in supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: putttps//nips.. cc/
Saallii/guides/CdeSSuubaaa oosieeooiiiiiiioooioooocoo for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.e. wttcccccppccccceeccecc pwwppc/guuudesseep///ppppppp Codeeubmi ssi siPoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experiment details are fully described in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, all experiments include sample sizes to assess variability.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
42

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. 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: [Yes]
Justification: This paper only studies relatively small-scale problems compared to other machine learning areas, and each individual experiment can run on an ordinary laptop.
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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: : http///eerrr/.////e cc
Answer: [Yes]
Justification:
We have checked and believe that we conform the guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theory-and-merhods-foom paper with no explicit societal applica- tion or impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
43

---

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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release a dataset or model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We do not use any assets except publicly-available Python packages, which are documented dependencies for our code, and their companion papers cited.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense 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.
44

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce any 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 part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: There are no human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
There are no human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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 as the institution conducting the review.
16. Declaration of LLM usage
45

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: There no LLM usage.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: /ttpas::///eiis.peeeee httpa//pps.c//oofeeeeeeeecceeeee ccc//aaffrrennee2225///11 for what should or should not be described.
46


Reviews:
[{"review_id": "FinAIM6V6g", "reviewer": "Reviewer_2wsw", "summary": "This paper studies *simple* (stochastic) Bilevel optimization, where the target variable $x$ is minimized over the solution set of a convex lower-level problem. The core contribution is an Iteratively Regularized Conditional Gradient (IR-CG) framework that avoids projection oracles by relying solely on linear optimization over the base feasible set. The authors present two algorithms (IR-SCG and IR-FSCG) for one-sample and finite-sum settings, respectively, and derive non-asymptotic convergence guarantees. Empirical comparisons on two benchmark problems demonstrate improved practical performance relative to baseline methods.", "questions": "-\tLine 89-91: “However, their method requires linear optimization over intersections of X with halfspaces.” – could you clarify what *with halfspaces* means and why this is an issue? Is it computationally prohibitive? \n\n-\tOn vanishing penalty parameters: assume we fix the max iteration $T$ or target accuracy. What happens if we set $\\sigma_t = \\sigma_T$ for all $t$? Does it degrade the convergence result? (if so, how worse would it be?)", "limitations": "Overall, the current presentation needs to be significantly improved. I recommend rejection this round. It is difficult to comprehend the precise novelty, the trade-offs relative to prior work, or the design choices behind the algorithms.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "My main concern is the poor technical writing that makes it difficult to assess their core contributions. With the current draft, it is very difficult to apprehend what the major improvement over the prior work is, and what is particularly interesting in their algorithm design. Detailed examples are below:\n\n-\tThe paper does not clearly explain how the proposed rates improve existing results. For instance, Cao et al. [4], achieves $O(t^{-1/2})$ convergence rates for both levels, while this paper obtains $O(t^{-1/2+p})$ and $O(t^{-p})$ for the upper and lower level, respectively, which seems worse anyway. It is not very clear either how significant the claimed computational gain is quantitatively. \n\n-\tAlgorithm 1 appears to be merely a combination of STORM gradient estimation and Frank-Wolfe updates on a penalized objective (except the last two lines, which is ad-hoc to varying penalty parameter). Aside from the weighting scheme and averaging, the novelty in algorithm design is not highlighted clearly.  \n\n-\tWhile it's reasonable to analyze both one-sample and finite-sum stochastic settings, presenting them in parallel obscures the logical flow. It would be more natural to treat the one-sample case as the more general scenario, and then specialize to finite-sum with in-depth intuition and analysis. This would also help clarify why the rates differ -- something that is rarely the case in related work.", "was_revised": true, "final_justification": "I think the paper needs more polish at least.", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address the concerns raised below:\n*   **Convergence rates, contribution and differentiation with Cao et al..** We thank the reviewer for this important question. The reviewer is correct that our convergence rates are not as strong as those in Cao et al.. However, our work's primary goal is not to improve iteration complexity but to propose a method that is more computationally efficient. We improve upon their approach in several fundamental ways, which we will clarify in the revised manuscript.\n\n    1.  *Improved per-iteration costs.* Cao et al. requires at each iteration solving a linear optimization over $X \\cap H$, where $H = \\\\{x : a^\\top x \\leq b\\\\}$ is some halfspace. In contrast, our algorithm only requires linear optimization over $X$, which in general is cheaper. As Cao et al. use a more powerful oracle, they achieve a better iteration complexity. However, for many examples, optimizing over $X \\cap H$ is expensive compared to just $X$. For example, if $X$ is an $\\ell_1$-ball, then optimizing over $X$ can be done exactly in $O(d)$. In contrast, optimization over $X \\cap H$ has no closed-form expression and thus requires a linear solver. Cao et al. also use a linear solver to implement this oracle. In such situations, we believe our method is beneficial compared to Cao et al. despite the worse iteration complexity, since the *overall* computational cost is better.\n\n        For the sake of illustration, assume that $X$ is a norm ball. Consider the linear minimization oracle problem over $X \\cap H$:\n        $$ \\min_x \\\\{ c^\\top x : \\lVert x \\rVert \\leq r, a^\\top x \\leq b \\\\}. $$\n        One can show that its dual problem takes the form:\n        $$ \\max_{\\mu} \\\\{ -r \\lVert c + \\mu a\\rVert_* - \\mu b : \\mu \\geq 0 \\\\}, $$\n        where $\\lVert \\cdot\\rVert_*$ is the dual norm. Given an optimal dual solution $\\mu^\\star$, the optimal primal solution satisfies\n        $$ x^\\star \\in \\arg\\min_{x} \\\\{ c^\\top x + \\mu^\\star (a^\\top x - b): \\lVert x \\rVert \\leq r \\\\}. \\tag{1} $$\n        \n        In the case of $\\ell_2$-ball, the dual problem is a nonlinear one-dimensional convex optimization problem, which can be solved efficiently with a bisection algorithm. Each iteration of the bisection algorithm costs $O(d)$, so it is not as fast as the closed form for linear optimization over $X$ alone. Once the optimal dual multiplier $\\mu^\\star$ is found, the optimal primal solution $x^\\star$ can be computed in $O(d)$ time since (1) has a unique optimum.\n        \n        In the case of $\\ell_1$-ball, we have $\\lVert \\cdot \\rVert_* = \\lVert \\cdot \\rVert_\\infty$ thus the dual is a piecewise linear one-dimensional convex optimization problem. An exact solution can be obtained by computing the breakpoints, but there are $O(d^2)$ potential points, which is much more expensive than $O(d)$. However, obtaining the optimal dual variable $\\mu^\\star$ does not lead to easy recovery of the primal solution $x^\\star$ as the minimization in (1) may have *multiple* solutions, and in this case, standard duality provides no mechanism for selecting the correct one.\n        In this case, one must use a LP solver or rely on an iterative averaging scheme (e.g., Corollary 12.16 of [*]). The averaging approach, however, converges slowly, at best with a rate of $1/N$ after $N$ iterations. Besides, it negates the core benefit of the Frank-Wolfe method, as the recovered solution is no longer a simple structured vertex.\n        \n        Our numerical experiments in Section 3 directly support this analysis. We also include an additional result where $X$ is defined by the Nuclear norm, showing an even greater improvement as we are dealing with semidefinite programs. We refer the reviewer to our response to `Reviewer TL81`.\n\n        [*] Orabona, Francesco. A modern introduction to online learning. arXiv:1912.13213 (2019)\n    2.  *No initialization requirement.* Their algorithm requires a specific *warm start*: it must be initialized that is already $\\epsilon_g/2$-optimal for the lower-level problem. Finding such a point can be non-trivial especially in stochastic setting as it requires algorithms that have high probability guarantees rather than in expectation. Moreover, as observed in our numerical experiments (consistent with both theoretical and numerical results of Cao et al.), the convergence behavior of the inner-level problem degrades, going from $\\epsilon_g/2$ to $\\epsilon_g$, rather than improving. In contrast, our method is initialization-free and does not requires such pre-computation.\n\n    3.  *Any-time guarantees and asymptotic correctness.* In addition to requiring a warm start with respect to the parameter $\\epsilon_g$, the method of Cao et al. also uses this parameter to define $H$ at each iteration. Thus, their algorithm is *not any-time*: running it indefinitely does not guarantee convergence to an optimal solution of the bilevel problem, but rather to a minimizer of $f$ over the set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g\\\\}$, which is only an *approximate* solution. In contrast, our algorithm enjoys *any-time* behavior with asymptotic convergence guarantees (Theorems 3 and 4 in the appendix).\n\n    4.  *Preserving structural properties.* A key advantage of projection-free algorithms is their ability to maintain low-complexity updates for structured sets. For instance, with the simplex (for sparsity) or the Nuclear norm ball (for low-rankness), the linear oracle over $X$ simply returns an atomic vertex. This crucial benefit is lost in their method, as the oracle over $X \\cap H$ typically returns a dense solution. This negates one of the core strengths of projection-free algorithms.\n\n    5.  *Easy implementation.* In addition to relying on the parameter $\\epsilon_g$ for a careful initialization and defining $H$ at each iteration, the algorithm in Cao et al. also depends on an additional parameter $K_t$ to define $H$, which itself is defined in terms of noise variance, set diameter and objective function smoothness. Besides, the linear minimization oracle in their algorithm is only guaranteed to be feasible with *high probability*, hence the algorithm can stall at any iteration due to oracle infeasibility. In contrast, our algorithm requires only the parameter $\\varsigma$, and our oracle is always feasible. While the optimal choice of $\\varsigma$ depends on the same underlying parameters, this choice only changes the constant factor rather than the convergence rate. In practice, one can simply try $\\varsigma \\in \\\\{0.1, 1, 10\\\\}$ to achieve satisfactory empirical performance.\n    \n*   **Novelty of the algorithm design and analysis.** We thank the reviewer for this observation. While our framework indeed integrates established components like stochastic gradient estimators (STORM/SPIDER) and the Frank-Wolfe method, our core contribution lies in the specific algorithmic innovations required to address the unique bilevel structure. Specifically, we introduce a dynamic regularization term, $\\sigma_t f$, which is crucial for managing the bilevel objective. This new component, combined with any-time step-size rules, require a non-trivial convergence analysis. A key feature of this analysis is a novel *averaging scheme*, which was specifically devised to guarantee *simultaneous* convergence for both inner- and outer-level objectives while preserving the algorithm's any-time properties.\n    \n*   **Presentation:** We thank the reviewers for their constructive feedback on the paper's presentation. In the final version, we will implement several key revisions. Following `Reviewer B9Ux`'s suggestion, we will restructure the paper to better highlight our contributions to the nonconvex case. We will reorganize the main text to present the convex and nonconvex results side-by-side, first in Section 2 for the one-sample case (Theorem 1 and Theorem 5 from the appendix) and then in Section 3 for the finite-sum case (Theorem 2 and Theorem 6 from the appendix). We will also replace the second numerical experiment with the nonconvex example from the appendix. To accommodate these changes within the page limit, the proof sketches will be removed from the paper. Finally, as suggested by `Reviewer ZPtF`, we will revise the title and abstract to better reflect our focus on *simple* bilevel problems, including those with nonconvexity in the outer-level.\n\n**Answers to Questions:**\n\n*   We thank the reviewer for pointing out this ambiguity. We will revise the text to clarify that our comparison refers to intersecting with a *single* halfspace, not multiple. We thus change the text from *halfspaces* to *some halfspace*. Note that the method in requires solving a linear oracle over the set $X \\cap H_t$, where the halfspace $H_t = \\\\{x : a^\\top x \\leq b\\\\}$ is a single, but *dynamically changing* halfspace that approximates the functional constraint set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g/2\\\\}$ at each iteration. As discussed in *Improved per-iteration costs.*, even a single additional constraint can make the subproblem expensive.\n\n*   Fixing $\\sigma_t = \\varsigma T^{-p}$ based on a predetermined total iteration count $T$ would indeed preserve the theoretical convergence rate. However, this approach has two significant drawbacks. First, fixed penalty schedule makes the algorithm's final accuracy dependent on the choice of $T$, whereas our approach guarantees convergence to the true optimum as $t \\to \\infty$. Second, we consistently observe that the dynamic, time-varying regularization scheme achieves better practical results. This, indeed, motivates us to prove the convergence rate for the anytime update rule.\n\nWe thank the reviewer again for their insightful feedback. We hope our response and planned revisions have addressed the main concerns. We were wondering if there are any other points we can clarify that could further improve the manuscript and their assessment of the work?"}, {"review_id": "g52nSedxyw", "reviewer": "Reviewer_TL81", "summary": "This paper tackles the challenge of solving stochastic convex bilevel optimization problems, where the goal is to minimize a stochastic outer function over the solution set of a stochastic inner function. Such problems are difficult because the inner problem's solution set is not explicitly known, which makes standard optimization operations like projections computationally expensive or intractable.  To address this, the authors propose an efficient framework based on the conditional gradient method (Frank-Wolfe-style algorithm) combined with iterative regularization. This approach sidesteps costly projections by relying exclusively on simple linear optimization oracles over the base feasible set, which is a significant advantage over prior methods.\n\nThe authors present two specific algorithms: IR-SCG for the general one-sample stochastic setting (the stochastic objective is averaged over a continuous distribution that only has sample access) and IR-FSCG for the finite-sum setting (the stochastic objective is averaged over finite samples). Both algorithms employ variance reduction techniques (STORM and SPIDER from previous literature) to handle the noise from stochastic gradient estimates. The paper establishes non-asymptotic convergence rates for both algorithms, showing rates of $O(t^{-(1/2−p)})$ for the outer problem in the one-sample case and $O(t^{-(1−p)})$ in the finite-sum case. Experiments on over-parametrized and logistic regression tasks demonstrate that these methods significantly outperform existing approaches in terms of wall-clock time, a practical advantage attributed to the computational efficiency of their simpler linear optimization oracles.\n\nRegarding the major claim of the contributions of the use of linear optimization oracles over the original feasible region $X$ as opposed to the intersection of the feasible region and a hyperplane, this part I don't completely get the computation benefit. When the feasible region $X$ is specified as a polygon, adding a hyperplane to get its intersection doesn't add additional difficulty. When the feasible region $X$ is not a polygon, adding a hyperplane can indeed lead to more difficulty but the original linear optimization in the non-polygon feasible region is also non-trivial if the feasible region is non-trivial. Since this is the major difference compared to prior work by Cao et al. 2023, could you please explain in what cases the linear optimization oracle has a clear advantage over the one by Cao that uses hyperplane? Other than that, I checked the proof in the main paper and Lemma 1, 2. I didn't check the rest of the proof in the appendix but the proof sketch looks correct to me.", "questions": "Please refer to the strengths and weaknesses section.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Clear presentation and clear difference compared to prior work (especially Cao et al.)\n- One difference compared to Cao et al. is the use of the weight $\\rho$ and the dynamic weight sequence $\\rho_t$. This choice of sequence gives an additional dependency of $p \\in (0,1/2)$ or $p \\in (0,1)$ for two cases that the paper considers. From the theory perspective, this is an interesting observation but not very significantly different from prior analysis though.\n- Very detailed summary of the literature! This is very helpful for readers.\n\nWeaknesses:\n- Very similar results compared to Cao et al. 2023. Please clarify the advantage of not requiring intersection over the feasible set in linear optimization. Why does linear optimization with one additional hyperplane cause significant computational issues?\n- Algorithm designs are also directly followed by Cao et al. I didn't check the proof in Cao et al. but I believe it follows a similar strategy.\n- Theoretical results are slightly worse than Cao et al. Could you explain why the use of dynamic weight sequence gives you worse result?\n\nNeutral questions:\n- Experimental results look good, but I wonder how many iterations does each algorithm run? How much worse is the linear optimization oracle in terms of the computational cost? How did you implement the one with additional hyperplane and is its computation cost optimized? I think it is hard to judge the performance by the computation cost merely because I can't tell if the oracles are all implemented in the optimal way.", "was_revised": true, "final_justification": "I have read the authors' response and the response helps address my concerns. I agree that the convergence analysis is slightly different from prior work, and further analysis of the lower bound and impossibility result would be an interesting follow up. Therefore, I update my assessment accordingly.", "rebuttal": "Thank you for your thoughtful review. Below, we address the other specific points and questions from your review.\n\n*   **Linear oracles over $X \\cap H$ versus $X$.** Our central argument is that the lower per-iteration cost of our algorithm's oracle over $X$ often more than compensates for its worse iteration complexity guarantee compared to the oracle over $X \\cap H$. For many important structured sets, this trade-off makes our method superior in terms of execution time. While we acknowledge that for a general polytope $X$, the intersection $X \\cap H$ is also a polytope and both oracles would rely on an LP solver, the situation is different for many structured sets of interest. For sets like the $\\ell_1$-ball, $\\ell_2$-ball, Nuclear norm ball or the unit simplex, the linear oracle over $X$ can be computed exactly and efficiently. In contrast, the oracle over $X \\cap H$ is significantly more complex.\n\n    For the sake of illustration, assume that $X$ is a norm ball. Consider the linear minimization oracle problem over $X \\cap H$:\n    $$ \\min_x \\\\{ c^\\top x : \\lVert x \\rVert \\leq r, a^\\top x \\leq b \\\\}. $$\n    One can show that its dual problem is\n    $$ \\max_{\\mu} \\\\{ -r \\lVert c + \\mu a\\rVert_* - \\mu b : \\mu \\geq 0 \\\\}, $$\n    where $\\lVert \\cdot\\rVert_*$ is the dual norm. Given an optimal dual solution $\\mu^\\star$, the optimal primal solution satisfies\n    $$ x^\\star \\in \\arg\\min_{x} \\\\{ c^\\top x + \\mu^\\star (a^\\top x - b): \\lVert x \\rVert \\leq r \\\\}. \\tag{1}$$\n    \n    In the case of $\\ell_2$-ball, the dual problem is a nonlinear one-dimensional convex optimization problem, which can be solved efficiently with a bisection algorithm. Each iteration of the bisection algorithm costs $O(d)$, so it is not as fast as the closed form for linear optimization over $X$ alone. Once the optimal dual multiplier $\\mu^\\star$ is found, the optimal primal solution $x^\\star$ can be computed in $O(d)$ time since (1) has a unique optimum.\n    \n    In the case of $\\ell_1$-ball, we have $\\lVert \\cdot \\rVert_* = \\lVert \\cdot \\rVert_\\infty$ thus the dual is a piecewise linear one-dimensional convex optimization problem. An exact solution can be obtained by computing the breakpoints, but there are $O(d^2)$ potential points, which is much more expensive than $O(d)$ complexity for optimizing over $X$ alone. However, obtaining the optimal dual variable $\\mu^\\star$ does not lead to easy recovery of the primal solution $x^\\star$ for the $\\ell_1$-norm ball. This difficulty arises because the minimization problem in (1) may have *multiple* solutions, and in this case, standard duality provides no mechanism for selecting the correct one.\n    To solve the primal optimization problem, one must use a LP solver, or rely on an iterative averaging scheme (for example, Corollary 12.16 of [*]). The averaging approach, however, has two severe drawbacks. First, the averaging scheme converges slowly, at best with a rate of $1/N$ after $N$ iterations. Second, this iterative process completely negates the benefit of the Frank-Wolfe method, as the recovered solution is typically dense and no longer a simple structured vertex.\n\n    Our numerical experiments in Section 3 support this analysis. We also include an additional result where $X$ is defined by the Nuclear norm, showing an even greater improvement as we are dealing with semidefinite programs. \n\n    [*] Orabona, Francesco. A modern introduction to online learning. arXiv preprint arXiv:1912.13213 (2019).\n\n*   **Algorithm design and analysis.**\n    We provide a detailed comparison with Cao et al. in our response to `Reviewer 2wsw`. While our gradient estimators are the same as those of Cao et al. , our overall algorithm design, and consequently its analysis, is fundamentally different. The key differences are outlined below.\n    1.  *Type of linear oracle.* As discussed above, our algorithm uses a linear oracle over $X$ only, while theirs requires one for $X \\cap H_t$, where $H_t$ is a dynamically changing halfspace. This results in a different analysis with worse iteration complexity, but better overall running time. Additionally, the linear minimization oracle in their algorithm is only guaranteed to be feasible with *high probability*, hence the algorithm can stall at any iteration due to oracle infeasibility. \n   \n    2.  *Regularization versus sublevel set approximation.* The key difference between the two algorithm designs is their approach. Cao et al. approximates the lower level problem $G(x) \\leq G_{\\text{opt}}$ with an outer halfspace approximation $H_t$ at each step. On the other hand, we use a regularization approach of adding $\\sigma_t f$ to guide the iterates towards the bilevel solution. This is the reason behind the different oracles, and also explains why the analysis is so different.\n\n    3.  *Single stage versus two-stage algorithm.* The algorithm of Cao et al. requires initialization with a point $x_0$ that is $\\epsilon_g/2$-optimal for the lower-level problem. Finding such a point can be non-trivial especially in stochastic setting as it requires algorithms that provide such a point with high probability rather than in expectation. In contrast, our algorithm does not require any such initialization.\n\n    4.  *Any-time versus approximate guarantees.* The warm-start parameter $\\epsilon_g$ of Cao et al. also appears in the definition of the halfspaces $H_t$ at each iteration. In essence, this means that the sublevel set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g\\\\}$ is contained in $H_t$. However, this means that if their algorithm is run indefinitely, there is no assurance that their algorithm converges to an optimal solution of the bilevel problem, but rather it may instead converge to a minimizer of $f$ over the sublevel set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g\\\\}$, which is an *approximate* solution. In contrast, if our algorithm is run indefinitely, we proved in Appendix B.1 that it will converge to an optimal solution of the bilevel problem. In other words, our algorithm is *any-time* whereas theirs is not.\n\n*   **Worst iteration complexity.** The reviewer is correct in saying that the iteration complexity of Cao et al. is better than ours. This is a direct consequence of them utilizing a more powerful linear oracle over $X \\cap H_t$ each iteration, where $H_t$ is a dynamically varying halfspace. On the other hand, we use a much cheaper oracle over $X$.\n    Our experiments in Section 3 demonstrate that our algorithms achieve lower gaps in the same amount of running time, thus there is immense computational benefit to trading off iteration complexity for a lower per-iteration cost.\n\n*   **Answer to Neutral Question.** In Section 3, we included tables reporting the average number of iterations, which equals the number of linear optimization oracle calls. We observe that our algorithms require 2–3 orders of magnitude more linear optimizations compared to. Following Cao et al., we implemented the minimization oracle over $X \\cap H$ using CVXPY. To our knowledge, there is no more efficient method for linear optimization over a norm ball with an additional hyperplane constraint; however, if the reviewer is aware of one, we would be happy to explore it.\n    \n    To further demonstrate our algorithm’s performance relative to Cao et al., we conduct a new synthetic experiment on the following bilevel matrix completion problem\n    $$ \\begin{array}{cl}\n        \\min\\limits_{X \\in \\mathbb{R}^{m \\times p}} & F(X):= \\frac{1}{2mp} \\lVert X\\rVert_F^2 = \\frac{1}{2mp}\\sum_{(i,j) \\in [m] \\times [p]} |X_{i,j}|^2 \\\\\\\\\n         \\text{s.t.} & X \\in \\arg\\min_{\\lVert Z \\rVert_{nuc} \\leq r} G(Z):= \\frac{1}{|\\Omega|} \\sum_{(i,j) \\in \\Omega} H_{\\xi}(M_{i,j}-Z_{i,j}).\n    \\end{array} $$\n    where $X \\in \\mathbb{R}^{m \\times p}$, $H_\\xi$ is the Huber loss function with parameter $\\xi$ and $M$ is a given matrix with only entries $\\{M_{i,j}: (i,j) \\in \\Omega\\}$ are observed. \n    We generate $M$ as follows: we first generate a random matrix $M \\in \\mathbb{R}^{m \\times p}$ where $m=p=100$ and then randomly choose $20\\\\%$ of the entries as being unobserved. We also choose $\\xi = 1, r = 10$. The linear minimization problem $\\text{Tr}(C^\\top X)$ over the Nuclear norm ball is solved analytically by $-\\delta u_1 v_1^\\top$ where $u_1, v_1$ are the left and right singular vectors corresponding to the largest singular value of $C$, respectively. Meanwhile, the linear minimization problem over the Nuclear norm ball intersecting a half-space is solved using CVXPY. We note that although our approach can handle larger-scale problems, the CVXPY solver fails on these instances due to the out of memory error. Below, a summary of our experiment after running each algorithm for $10$ minutes is reported. This further shows that our algorithm has better empirical performance against Cao et al.. \n\n| Method | Oracle Time | Inner Sub-optimality | Absolute Outer Sub-optimality | # Iteration Counts |\n| :--- | :---: | :---: | :---: | :---: |\n| `IR-FSCG` | 8.91e-3 | 8.11e-7 | 2.60e-7 | 57778 |\n| `IR-SCG` | 8.33e-3 | 1.71e-3 | 1.61e-4 | 64295 |\n| `SBCGF` | 1.96e2 | 8.67e-3 | 7.94e-4 | 3 |\n| `SBCGI` | 1.47e1 | 8.94e-3 | 8.12e-4 | 34 |\n\nWe thank the reviewers for their constructive feedback on the paper's presentation. As suggested by `Reviewer 2wsw`, we will reorganize the main text to present the convex and nonconvex results side-by-side, first in Section 2 for the one-sample case (Theorem 1 and Theorem 5 from the appendix) and then in Section 3 for the finite-sum case (Theorem 2 and Theorem 6 from the appendix). To emphasize the nonconvex setting, we will replace the second numerical experiment with the nonconvex example from the appendix. Finally, as suggested by `Reviewer ZPtF`, we will revise the title and abstract to reflect our focus on *simple* bilevel problems.\n\nPlease let us know if there are any remaining points we can address or clarifications we can provide that would be helpful in your final evaluation."}, {"review_id": "BRWF1AgAWT", "reviewer": "Reviewer_B9Ux", "summary": "This paper studies the constrained convex simple bilevel optimization via penalty methods with Frank Wolfe algorithm. The proposed algorithm is projection-free and eliminates the need for optimization over intersections of the base feasible set with halfspaces. Convergence rate is given in both stochastic and finite-sum setting. Numerical results on over-parameterized regression and minimal norm logistic regression validate the effectiveness of the proposed method.", "questions": "1. How to implement $v_t \\in \\underset{v \\in X}{\\arg \\min }\\left\\{\\left(\\sigma_t \\widehat{\\nabla F}_t+\\widehat{\\nabla G}_t\\right)^{\\top} v\\right\\}$ in practice? Is there any closed-form solution or we need iterative algorithm?", "limitations": "Same as weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: 1) The proposed method is easy-to-implement and theoretical sound. 2) The method has strong empirical performance. \n\nWeakness: 1) The novelty of this work is limited, as both penalty methods and the Frank-Wolfe algorithm have been extensively studied in the context of simple and general bilevel optimization. 2) The convergence rate of the proposed method appears to be worse than that of Cao et al. [4, Algorithm 2], even when $p$ is chosen to optimally balance the upper- and lower-level objective value gaps. 3) This paper only considers the convex setting rather than the nonconvex case, which restricts the practical applicability of the algorithm. 4) The theoretical guarantee for the upper-level objective is weak. Specifically, $f^$ is not defined as the global minimum over the entire domain, so the actual objective value $f$ can be smaller than $f^$. As a result, the theory provides only an upper bound on $f - f^*$, without a corresponding lower bound.", "was_revised": true, "final_justification": "This paper proposed a simple but efficient algorithm tailored for stochastic simple bilevel optimization problem. It has both theoretical guarantee and strong empirical performance. The merit of the proposed algorithm is its simple implementation and empirical performance, so my previous concerns are mainly around its theoretical guarantee compared with existing works. \n\nThe authors solve my concerns during rebuttal including: \n1) technical novelty of proving finite-time convergence in the stochastic setting without using linear optimization oracle of the intersection of a hyperplane. \n2) although the convergence rate provided is loose than the existing works (the only weakness after the rebuttal), considering its simple implementation, it is still acceptable. \n3) the authors have included the results for nonconvex objectives in Appendix which they will highlight in the main paper in the revision.\n4) For the lower bound of $f(z_t)-f^*$, the author provided asymptotic guarantee in Appendix B.1. \n5) Implementation details and the complexity of linear optimization oracle are provided. \n\nBased on the above justifications, I find this paper to be technically solid, presenting a simple yet practically efficient algorithm with sufficient theoretical guarantees. Therefore, I have changed my score to positive.", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address the concerns raised below.\n*   **Novelty of the work.** We agree that penalty methods are well-studied in the bilevel optimization literature. However, for simple bilevel optimization, to our knowledge only Jiang et al, Giang-Tran et al, Doron and Shtern (2022) and Cao et al. explored Frank-Wolfe-based methods. Amongst these, the stochastic setting was only considered by Cao et al.. Our work improves upon theirs in two ways: we allow for an oracle over only $X$ rather than $X$ intersected with a hyperplane, and we obtain *any-time* convergence guarantees. (That said, the reviewer is correct that our iteration complexity is worse than theirs; we address this in the next point.) We take a completely different approach to their paper by using an iterative regularization (penalty) method, which combined with Frank-Wolfe type updates has not been considered in the stochastic setting. Our algorithm design and analysis are non-trivial, requiring a carefully constructed averaging scheme to obtain convergence rates, and also particular attention to the initialization of the gradient estimates in the finite-sum setting. Therefore, we believe that our paper is novel compared to current bilevel optimization literature. If we have overlooked any related work, we would be grateful for suggestions and would be glad to consider them carefully.\n\n*   **Convergence rates.** The reviewer is correct in stating that our iteration complexity (and hence also sample complexity) is worse than that of Cao et al.. However, we believe that our algorithm is still of value despite this, for four key reasons.\n    1.  *Type of linear oracle.* As mentioned above, our algorithm uses a linear oracle over $X$ only, while theirs requires one for $X \\cap H_t$, where $H_t$ is a dynamically changing halfspace. Generally, linear optimization over $X$ only is often much cheaper than linear optimization over the intersection $X \\cap H$, where $H$ is a halfspace. This is true even in cases where $X \\cap H$ has an efficiently implementable (e.g., polynomial time) linear oracle. An example from the paper is when $X$ is an $\\ell_1$-ball. Since $X$ is a polytope, $X \\cap H$ is also a polytope, hence linear optimization can be computed using any off-the-shelf LP solver. (This is also how Cao et al. implement this example in their paper.) While LP solvers are generally efficient, linear optimization over $X$ alone can be computed in $O(d)$ time, which is much more efficient than using a solver. (See our response to `Reviewer 2wsw` for shortcomings of another approach besides LP.)\n\n        As the reviewer has noted, the empirical performance of our method is strong compared to others, including Cao et al., and we directly attribute this to the cheaper linear optimization oracle required. Therefore, we have shown that trading off iteration complexity for a cheaper per-iteration cost can bring computational benefits.\n    2.  *Easy initialization.* The algorithm of Cao et al. requires initialization with a point $x_0$ that is already $\\epsilon_g/2$-optimal for the lower-level problem. Finding such a point can be non-trivial especially in stochastic setting as it requires algorithms that provide such a point with high probability rather than in expectation. In contrast, our algorithm does not require any complicated initialization.\n    3.  *Any-time guarantees.* The warm-start parameter $\\epsilon_g$ of Cao et al. also appears in the definition of the halfspaces $H_t$ at each iteration. In essence, this means that the sublevel set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g\\\\}$ is contained in $H_t$. However, this means that if their algorithm is run indefinitely, there is no assurance that their algorithm converges to an optimal solution of the bilevel problem, but rather it may instead converge to a minimizer of $f$ over the sublevel set $\\\\{x : G(x) \\leq G_{\\text{opt}} + \\epsilon_g\\\\}$, which is an *approximate* solution. In contrast, if our algorithm is run indefinitely, we proved in Appendix B.1 that it will converge to an optimal solution of the bilevel problem. In other words, our algorithm is *any-time* whereas theirs is not.\n    4.  *Feasibility of the linear oracle.* The linear minimization oracle in their algorithm is only guaranteed to be feasible with *high probability*, hence the algorithm can stall at any iteration due to oracle infeasibility. In contrast, our algorithm requires only the parameter $\\varsigma$, and our oracle is always feasible.\n\n*   **Non-convex objectives.** We have already provided results for the non-convex outer level setting in Appendix B.2. That said, to highlight this further, we intend to reorganize the paper slightly by placing these results in the main text, and moving the proof outlines to the appendix.\n\n*   **Guarantee for outer-level objective.** We agree with the reviewer that since each iteration $x_t$ may not satisfy $G(x_t) \\leq G_{\\text{opt}}$, they may in fact be *super*optimal and we have $F(x_t) < F_{\\text{opt}}$. In fact, in Appendix B.1. we show that $F(x_t) \\to F_{\\text{opt}}$, which gives reassurance on the behavior of the outer-level objective. The reviewer is correct that we do not provide a lower *bound* on this gap. We are aware of such lower bounds in the deterministic setting under an additional error bound assumption for the inner level objective; see, e.g., Jiang et al. (2023) and Merchav et al. (2024). However, we are unaware of such results in the stochastic bilevel setting, and we think it is indeed a very interesting direction. Given the length of our current manuscript, we decided to defer this investigation for future work.\n\n*   **Answer to Question.** The implementation of the linear optimization oracle for $X$ is highly dependent on the structure of $X$. In cases such as $\\ell_1$- or $\\ell_2$-norm ball, there is a closed form which can be computed in $O(d)$ time. When $X$ is a Nuclear norm ball, the solution involves computing a leading singular vector, for which algorithms exist. In our paper we considered the $\\ell_1$-ball, and we implemented the linear optimization oracle via this closed form expression:\n$$ \\arg\\min_{v \\in X} z^\\top v = \\text{sign}(z_i) e_i, \\quad i \\in \\arg\\max_{j \\in [d]} |z_j|. $$\n\nWe thank the reviewers for their constructive feedback on the paper's presentation. To improve clarity and flow in the final version, we will implement several key revisions. As suggested by `Reviewer 2wsw`, we will reorganize the main text to present the convex and nonconvex results side-by-side, first in Section 2 for the one-sample case (Theorem 1 and Theorem 5 from the appendix) and then in Section 3 for the finite-sum case (Theorem 2 and Theorem 6 from the appendix). To further emphasize the nonconvex setting, we will also replace the second numerical experiment with the nonconvex example from the appendix. Finally, as suggested by `Reviewer ZPtF`, we will revise the title and abstract to better reflect our focus on *simple* bilevel problems, including those with nonconvexity in the outer-level. Please let us know if there are any remaining points we can address that would be helpful in your final evaluation."}, {"review_id": "lnIQhv2iHG", "reviewer": "Reviewer_aKVj", "summary": "This work studies stochastic bilevel optimization problem where the inner & the outer objectives are smooth convex functions. Additionally, the inner problem is constrained on a convex compact set. After a thourough literature review, the paper uses a regularized objective $\\sigma_t F + G$ where the optimization algorithm focuses mainly on $F$ and gradually shifts toward minimization of G through decreasing $\\sigma_t$. The gradient estimations were done by two distinct well-known variance reduction methods: STORM & SPIDER. The convergence rates of the proposed methods were studied * simple numerical results supported the superiority of the proposed methods.", "questions": "First of all, thanks for your efforts.\n\n1- Why does the paper consider a 4-minute stopping criteria and not a stopping criteria based on suboptimality or Frank-Wolfe gap?\n\n2- As the lower level problem is constrained, objective suboptimality is not a correct measure of stationarity. In such cases the Franke-Wolfe gap is a suitable measure instead. This applies to both your simulations and theorems 1 and 2. Could you please explain why didn't you use the FW gap?\n\n3- Did you try other step-size strategies for your stochastic conditional gradient method?\n\nThanks!", "limitations": "Limitations were not discussed or at least I could not find them in the main body.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1- Well-written paper\n\n2- Good literature review\n\n3- good contribution\n\n**Weaknesses**\n\n1- Numerics are either simple, or not even bilevel problems originally. My main issue is with section 3.2. This problem is a strongly convex constrained optimization. I guess one should consider other methods in this class of functions if we choose such a simulation.", "was_revised": true, "final_justification": "After reading al the comments I decided to keep my score for two main reasons:\n\n1- As raised by many reviewers, the theoretical results reported in this work are worse than the state of the art,\n\n2- I was happy with the fact that the authors provided additional detail on the experiments, but as raised by Reviewer ZPtF, the practical performance is quite problem-based. Therefore, I keep my borderline positive rating.", "rebuttal": "We thank the reviewer for the thoughtful feedback. We address the concerns and questions raised below.\n\n1.  We thank the reviewer for this point. We agree with the reviewer that the experiment from Section 3.2 is adapted from an $\\ell_2$-regularized learning problem. However, we wish to note that $\\ell_2$-regularization is one of the early inspirations for bilevel optimization: Tikhonov and Arsenin showed that solutions of $\\min_{x \\in X} \\\\{\\sigma F(x) + G(x)\\\\}$ converge to the bilevel solution as $\\sigma \\to 0$; see also Beck and Sabach (2014) for further discussions on minimum norm problems. Bilevel optimization methods then arose to enable us to converge to the bilevel solution without having to solve $\\min_{x \\in X} \\\\{\\sigma F(x) + G(x)\\\\}$ completely at each iteration.\n\n    We agree that ideally, we would compare against methods that exploit the strong convexity and deterministic nature of the outer-level function $\\frac{1}{2} \\lVert x\\rVert_2^2$. To that end, Doron and Shtern (2023) provide a class of *deterministic* algorithms that do so for coercive outer-level functions. However, our paper focuses on the *stochastic* setting. We are not aware of any methods that both handle this stochasticity and exploit the specific structure of the outer-level problem in the same way. This is why our comparison focuses on general-purpose stochastic bilevel methods. While our experiment uses a classic $\\ell_2$-regularized problem, this serves as a fundamental benchmark for the class of stochastic algorithms we are developing. We welcome any suggestions for work we may have overlooked.\n\n2. A through comparison between our proposed method against the one in Cao et al. (2023) is available in our responses to `Reviewer 2wsw`. We also run additional experiment on a bilevel matrix completion problem discussed in the reponse for `Reviewer TL81` to further demonstrate our algorithm’s performance relative to Cao et al.\n\n**Answers to questions**\n\n1.  **Stopping criterion.** Our choice of stopping criterion based on running time rather than an error threshold is chosen because, in practice in the stochastic setting, one would not be able to compute the Frank-Wolfe or suboptimality gap without a full gradient evaluation. Therefore, using running time as a stopping criterion seems more natural. That said, we evaluate the progress at the time of stopping via the suboptimality gap. Also, using running time allows us to have more control over how much we need to use the limited computational resources at our disposal. That said, we do not expect that our comparisons will change if we use a gap-based stopping criterion.\n\n    *Table 1: Time Elapsed to Reach Specific Inner Sub-optimal Levels on Over-parameterized Regression Problem*\n    | Algorithm | 0.1 | 0.01 | 0.001 | 0.0001 |\n    | :--- | :--- | :--- | :--- | :--- |\n    | **`IR-FSCG`** | 1.00e0 | 1.00e0 | 1.00e0 | 1.00e1 |\n    | **`IR-SCG`** | 1.04e0 | 2.01e0 | 4.90e1 | N/A |\n    | **`SBCGF`** | 3.19e1 | 3.19e1 | 3.19e1 | 3.19e1 |\n    | **`SBCGI`** | 3.08e1 | 3.08e1 | 3.08e1 | 3.08e1 |\n    | **`aR-IP-SeG` (long step)** | 1.00e0 | 1.00e0 | 1.00e0 | 1.50e1 |\n    | **`aR-IP-SeG` (short step)**| 1.00e0 | 1.00e0 | 5.00e1 | N/A |\n    | **`SDBGD` (long step)** | 1.00e0 | 1.00e0 | 1.40e1 | 3.40e1 |\n    | **`SDBGD` (short step)** | 1.00e0 | 1.00e0 | 1.40e1 | 3.30e1 |\n\n\n    *Table 2: Time Elapsed to Reach Specific Outer Absolute Sub-optimality on Over-parameterized Regression Problem*\n    | Algorithm | 0.1 | 0.01 | 0.001 | 0.0001 |\n    | :--- | :--- | :--- | :--- | :--- |\n    | **`IR-FSCG`** | 1.00e0 | 1.00e0 | 1.00e0 | 2.00e0 |\n    | **`IR-SCG`** | 1.03e0 | 4.00e0 | 9.01e0 | 1.12e2 |\n    | **`SBCGF`** | 3.19e1 | 3.19e1 | 8.20e1 | N/A |\n    | **`SBCGI`** | 3.08e1 | 3.08e1 | 3.40e1 | N/A |\n    | **`aR-IP-SeG` (long step)** | 1.00e0 | 1.00e0 | N/A | N/A |\n    | **`aR-IP-SeG` (short step)**| 1.00e0 | 1.00e0 | N/A | N/A |\n    | **`SDBGD` (long step)** | 1.00e0 | 1.00e0 | N/A | N/A |\n    | **`SDBGD` (short step)** | 1.00e0 | 1.00e0 | N/A | N/A |\n\n2.  **Suboptimality vs. Frank-Wolfe gap.** When the inner-level function is convex, which is the case for our experiments in Section 3, the suboptimality gap is upper-bounded by the Frank-Wolfe gap: $0 \\leq G(x) - G_{\\text{opt}} \\leq \\max_{v \\in X} \\nabla G(x)^\\top (x - v)$. Therefore the suboptimality gap gives a more accurate measure of progress. Note also that in practice the optimizer does not have access to $G_{\\text{opt}}$, so if one were to use a gap measure as a stopping criterion we could use the Frank-Wolfe gap, but we are using the suboptimality gap as an \"ideal\" measure to assess the performance of the algorithms. Besides, we are not aware of any existing algorithms, particularly in the stochastic setting, that use the Frank-Wolfe gap as a stationarity measure. To the best of our knowledge, both projection-based and projection-free methods typically use suboptimality to quantify stationarity. That said, we welcome any suggestions if there is relevant work we may have overlooked\n\n3.  **Other step-size strategies.** We have considered exact line search and closed-loop strategies, which are commonly used in Frank-Wolfe–type algorithms for *deterministic* problems. However, we are not aware of *stochastic* variants of these strategies, and implementing them in practice appears to be nontrivial. For this reason, we adopt the open-loop strategy.\n\nWe thank the reviewers for their constructive feedback on the paper's presentation. To improve clarity and flow in the final version, we will implement several key revisions. As suggested by `Reviewer 2wsw`, we will reorganize the main text to present the convex and nonconvex results side-by-side, first in Section 2 for the one-sample case (Theorem 1 and Theorem 5 from the appendix) and then in Section 3 for the finite-sum case (Theorem 2 and Theorem 6 from the appendix). To further emphasize the nonconvex setting, we will also replace the second numerical experiment with the nonconvex example from the appendix. Finally, as suggested by `Reviewer ZPtF`, we will revise the title and abstract to better reflect our focus on *simple* bilevel problems, including those with nonconvexity in the outer-level. We welcome any further questions that may arise as you finalize your review, and we thank you again for your time and guidance."}, {"review_id": "AkgoGyRQ8L", "reviewer": "Reviewer_ZPtF", "summary": "In this paper, the authors propose projection-free methods for solving stochastic convex bilevel optimization problems. They establish non-asymptotic convergence rates of $\\mathcal{O}(t^{-(\\frac{1}{2} - p)})$ for the outer objective and $\\mathcal{O}(t^{-p})$ for the inner objective in the one-sample stochastic setting, where $p \\in (0, \\frac{1}{2})$ controls the decay of regularization. In the finite-sum setting with a mini-batch scheme, they obtain convergence rates of $\\mathcal{O}(t^{-(1 - p)})$ for the outer objective and $\\mathcal{O}(t^{-p})$ for the inner objective, where $p \\in (0, 1)$.", "questions": "1. The authors claim that the proposed algorithms eliminate the need for optimization over intersections of the base feasible set with halfspaces. However, for common feasible sets such as the $\\ell_1$ or $\\ell_2$ ball, linear minimization over their intersection with a halfspace admits a closed-form solution and does not introduce additional computational cost. Could the authors provide concrete examples or experimental evidence showing that such operations are indeed computationally expensive?\n\n2. How should the parameter $\\varsigma$ be chosen in both theory and practice? Does it depend on other problem-specific constants such as $D$, $L_f$, $L_g$, $\\sigma_f$, or $\\sigma_g$?\n\n3. In Theorem 1, what is $d$? Is it intended to be $D$?\n\n4. The appendix includes results for the case of a non-convex upper-level objective. Why are these results not presented in the main text? \n\n5. The notation $\\sigma_t$ is used for the regularization parameter, while $\\sigma_f$ and $\\sigma_g$ denote variance terms. This could be confusing. Consider using a different symbol for the regularization parameter to avoid ambiguity.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The theoretical foundations of the paper are solid and largely correct.\n\n2. The presentation is clear and easy to follow.\n\nWeaknesses:\n\n1. The main weakness is that the sample complexities of the proposed algorithms are worse than those in [1] under the same setting. There are also minor issues that could be addressed to improve the accuracy of the paper.\n\n2. The paper focuses on simple bilevel problems, which differ from general bilevel problems by excluding an additional upper-level variable. It would be better to specify this in the title and abstract.\n\n3. It would be preferable to present the exact upper bounds of the function gaps in the main theorems, rather than using big-𝒪 notation.\n\n4. Since some log terms appear in the convergence rates, the rates stated in the abstract should be written using $\\tilde{\\mathcal{O}}$ instead of $\\mathcal{O}$.\n\nReference:\n\n[1] J. Cao, R. Jiang, N. Abolfazli, E. Yazdandoost Hamedani, and A. Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, pages 6105–6131, 2023.", "was_revised": true, "final_justification": "After the rebuttal period, my main concern remains: the proposed method has worse complexity than (Cao et al., 2023) in the convex setting. As the authors suggest moving the nonconvex setting from the appendix to the main text, I note that its complexity is even worse than (Cao et al., 2023). Hence, I maintain my original score.", "rebuttal": "We thank the reviewer for the thoughtful feedback. We address the concerns raised below.\n\n1.  **Convergence rates.** Cao et al indeed has better iteration complexity. However, this is due to using a two stage algorithm that results in three limitations: (i) a requirement to initialize at a point that is $\\epsilon_g/2$-optimal for the inner-level problem; (ii) a more expensive linear optimization oracle over $X$ intersected with a halfspace $H$ at each iteration; and (iii) lack of any-time guarantees. So, while it is true that our iteration complexity is worse, our overall algorithm aims to save on per-iteration costs, and also provide stronger any-time guarantees. Our numerical experiments show that the per-iteration savings are indeed valuable: our algorithm outperforms theirs on key examples, due directly to this more expensive per-iteration cost. Please see responses to other reviewers for more details.\n\n2.  **\"Simple bilevel\" terminology.** This is a valid point and we will clarify the terminology accordingly. It seems that in the bilevel optimization literature, \"simple bilevel\" and \"convex bilevel\" are sometimes used synonymously; see, e.g., Doron and Shtern (2022), Sabach and Shtern (2017). That said, given that our paper addresses both convex and non-convex outer-level objectives, we agree that \"simple bilevel\" is more appropriate terminology.\n\n3.  **Avoiding big-O notation:** The exact upper bounds for convex outer-level objective function with one-sample gradient estimator takes the form\n$$\n\\begin{align*}\n    &F(z_t) - F_{\\text{opt}}\\\\\\\\\n    &\\leq \\frac{2( L_f+L_g/\\varsigma)D^2}{(t+1)^{1-p}} +\n    \\frac{4c\\left(4( L_f+L_g/\\varsigma)D+3(\\sigma_f+\\sigma_g/\\varsigma)\\right)}{(t+1)^{1/2-p}}\\sqrt{\\log\\left(\\frac{8dt^2}{\\delta}\\right)},\\\\\\\\\n    &G(z_t)-G_{\\text{opt}}\\\\\\\\\n    &\\leq \\left((1+2p) \\left(F_{\\text{opt}}-\\min_{x \\in X} F(x)\\right)\\varsigma + 2(\\varsigma L_f +L_g)D^2\\right.\\\\\\\\\n    &\\quad \\left.+4c\\left( 8 \\left(L_f \\varsigma+L_g\\right)D^2+3\\left(\\sigma_f \\varsigma+\\sigma_g\\right)D\\right) \\sqrt{\\frac{2}{(1-2p)e}+\\log\\left(\\frac{8d}{\\delta}\\right)}\\right)\\left(1+\\frac{2p}{\\min\\{1,2(1-p)\\}}\\right) (t+1)^{-p},\n\\end{align*}\n$$\n    We note that this bound is also provided in the proof of Theorem 1 in the appendix. For other cases, particularly the nonconvex setting, the exact bounds are more involved. We will make every effort to include these exact rates in the final version. If space constraints prevent this, we will state the convergence results in big-O form in the main paper, while in the appendix we will restate each theorem explicitly with the exact bounds and then provide the corresponding proofs in full detail. We hope this addresses your concerns. \n\n5.  **Hiding logarithmic terms.** Thank you for pointing this out; we will check all terms and ensure they are correctly expressed with either $O$ or $\\tilde{O}$ notation.\n\n**Answers to Questions.**\n\n1.  **Computational cost of linear minimization over $X$ intersected with a halfspace.** Our claim is that linear optimization over $X$ is often cheaper than over $X \\cap H$, where $H$ is a halfspace. In many cases of interest, we believe that the difference is significant enough that our algorithm can outperform that of Cao et al, despite the worse iteration complexity guarantee.\n\n    This is evidenced by our experiments in Section 3, where $X$ was an $\\ell_1$-ball. Linear optimization over $X$ can be computed in $O(d)$ operations. We used a LP solver to compute linear optimization over $X \\cap H$, which is what was done in Cao et al. We see that our algorithm outperforms theirs, and the tables reported shows that this is because we are able to perform 2-3 orders of magnitude more iterations in the 4 minute time limit, a direct result of the cheaper per-iteration cost.\n\n    When $X$ is $\\ell_1$- or $\\ell_2$-norm ball, linear optimization over $X$ can indeed be expressed as a closed form and computed in $O(d)$ time. When we consider $X \\cap H$ instead, we are unaware of any results that provide a closed form for this. If we analyze the linear optimization problem over $X \\cap H$\n    $$ \\min_x \\\\{ c^\\top x : \\lVert x \\rVert \\leq r, a^\\top x \\leq b \\\\}, $$\n    one can show that its dual problem takes the form:\n    $$ \\max_{\\mu} \\\\{ -r \\lVert c + \\mu a\\rVert_* - \\mu b : \\mu \\geq 0 \\\\}, $$\n    where $\\lVert \\cdot\\rVert_*$ is the dual norm. Given an optimal dual solution $\\mu^\\star$, the optimal primal solution satisfies\n    $$ x^\\star \\in \\arg\\min_{x} \\\\{ c^\\top x + \\mu^\\star (a^\\top x - b): \\lVert x \\rVert \\leq r \\\\}. \\tag{1} $$\n\n    In the case of $\\ell_2$-ball, the dual problem is a nonlinear one-dimensional convex optimization problem, which can be solved efficiently with a bisection algorithm. Each iteration of the bisection algorithm costs $O(d)$, so it is not as fast as the closed form for linear optimization over $X$ alone. Once the optimal dual multiplier $\\mu^\\star$ is found, the optimal primal solution $x^\\star$ can be computed in $O(d)$ time since $\\min_{x} \\\\{ c^\\top x + \\mu^\\star (a^\\top x - b): \\lVert x \\rVert_2 \\leq r \\\\}$ has a unique optimum.\n    \n    In the case of $\\ell_1$-ball, we have $\\lVert \\cdot \\rVert_* = \\lVert \\cdot \\rVert_\\infty$ thus the dual is a piecewise linear one-dimensional convex optimization problem. An exact solution can be obtained by computing the breakpoints, but there are $O(d^2)$ potential points, which is much more expensive than $O(d)$ complexity for optimizing over $X$ alone. However, obtaining the optimal dual variable $\\mu^\\star$ does not lead to easy recovery of the primal solution $x^\\star$ for the $\\ell_1$-norm ball. This difficulty arises because the primal recovery problem $\\min_{x} \\\\{ c^\\top x + \\mu^\\star (a^\\top x - b): \\lVert x \\rVert \\leq r \\\\}$ may have *multiple* solutions, and in this case, standard duality provides no mechanism for selecting the correct one. To solve the primal optimization problem, one must use a LP solver, or rely on an iterative averaging scheme (for example, Corollary 12.16 of [*]). The averaging approach, however, introduces two severe drawbacks. First, the averaging scheme itself converges slowly, at best with a rate of $1/N$ after $N$ iterations. Second, this iterative process completely negates the core benefit of the Frank-Wolfe method, as the recovered solution is typically dense and no longer a simple structured vertex.\n    \n    Our numerical experiments in Section 3 directly support this analysis. We also include an additional result where $X$ is defined by the Nuclear norm, showing an even greater improvement as we are dealing with semidefinite programs. We refer the reviewer to our response to `Reviewer TL81`. \n\n    Besides, the linear minimization oracle in their algorithm is only guaranteed to be feasible with *high probability*, hence the algorithm can stall at any iteration due to oracle infeasibility. In contrast, our oracle is always feasible.\n    We would be grateful for any suggestions if the reviewer thinks we may have overlooked something.\n    \n    [*] Orabona, Francesco. \"A modern introduction to online learning.\" arXiv preprint arXiv:1912.13213 (2019).\n\n2.  **Choice of $\\varsigma$.** In theory, since we have two objective functions so there are many criteria to assess to which choice of $\\varsigma$ is optimal. Here, let's say we choose $\\varsigma$ such that the maximum of the coefficients of the dominant terms in the upper bounds for both level to be smallest. One can see that in all settings, we need to solve the problem of the forms\n    $$\\inf_{\\varsigma > 0} \\max\\\\{a+b\\varsigma, c+\\frac{d}{\\varsigma}\\\\},$$\n    where $a,b,c,d$ are positive constants depending on $p,q, \\omega, D, L_f, L_g, \\sigma_f,\\sigma_g, \\sup_{z \\in X}|F(z)|, F_{\\text{opt}}$, $\\min_{x \\in X} F(x), \\max_{x \\in X} F(x),F(x_0), G_{\\text{opt}}, \\min_{x \\in X} G(x), \\max_{x \\in X} G(x), G(x_0)$. We observe that the equation \n    $$a+b\\varsigma= c+\\frac{d}{\\varsigma} \\iff b \\varsigma^2 +(a-c)\\varsigma -d= 0,$$\n    always has a unique positive solution, which is $\\varsigma_{\\text{opt}}=\\frac{c-a+\\sqrt{(a-c)^2+4bd}}{2b}$. We note the objective is a convex function with respect to $\\varsigma > 0$ and\n    $$0=(\\frac{d}{d+b\\varsigma_{\\text{opt}}^2})b + (\\frac{b\\varsigma_{\\text{opt}}^2}{d+b\\varsigma_{\\text{opt}}^2})(-\\frac{d}{\\varsigma_{\\text{opt}}^2}) \\in \\partial\\max\\\\{a+b(\\cdot), c+\\frac{d}{(\\cdot)}\\\\} (\\varsigma_{\\text{opt}}),$$\n    which implies $\\varsigma_{\\text{opt}}$ is indeed, the optimal choice. In practice, we observe that $\\varsigma = 0.01, 0.1, 1, 10$ result in good performance.\n    \n3.  **Definition of $d$.** This is not a typo and $d$ is defined to be the dimension of variable $x$, which is mentioned in the introduction.\n    \n4.  **Moving the non-convex results.** This is a valid comment, we will move the non-convex results to the main text, replacing the proof sketches for the convex setting.\n    \n5.  **$\\sigma_t$ notation.** We thank the reviewer for this excellent suggestion. To avoid any ambiguity with the variance terms, we will change the notation for the regularization parameter from $\\sigma_t$ to $\\gamma_t$ in the revised manuscript.\n\nWe really appreciate the reviewer's detailed feedback and have aimed to address all points thoroughly. As suggested by `Reviewer 2wsw`, we will reorganize the main text to present the convex and nonconvex results side-by-side, first in Section 2 for the one-sample case (Theorem 1 and Theorem 5 from the appendix) and then in Section 3 for the finite-sum case (Theorem 2 and Theorem 6 from the appendix). To further emphasize the nonconvex setting, we will also replace the second numerical experiment with the nonconvex example from the appendix. Finally, we will revise the title and abstract to better reflect our focus on *simple* bilevel problems, including those with nonconvexity in the outer-level. We would welcome any further suggestions you may have that would help strengthen the manuscript and improve your final evaluation."}]

Author rebuttal:

Meta-review: This work proposes projection-free algorithms for stochastic convex bilevel problems (with nonconvex extensions in the appendix). The problem is $\min_{x\in X_{opt}} f(x)$ where $X_{opt}=\arg\min_{z\in X} g(x)$. In particular, the authors provide an algorithm that uses linear oracles over the set $X$ instead of the prior work [Cao et al 2023] that used linear oracles over the intersection of $X$ and dynamic selected half spaces $H_t$. 

This work had diverging reviews with some reviewers suggesting acceptance and some reviewers suggesting rejection.

The main weakness of this work pointed out by some of the reviewers was that the resulting sample complexities in this work are not as good as [Cao et al. 2023]. In particular, the new rate is $O(1/T^{1/4})$, whereas the state-of-the-art rate was $O(1/T^{1/2})$ in the prior work in the stochastic case. Similarly, the rate in this paper is $O(1/T^{1/2})$ in the finite sum case whereas the state-of-the-art is $O(1/T)$. The authors argued that their oracle is simpler than the previous work to justify the worse sample complexity and that they suspect their complexities under their oracles to be tight. However, no formal guarantee is provided. Empirical results seem promising.

In the previous work, the linear minimization problem over the intersection of two sets had to be solved by off-the-shelf solvers such as cvxpy whereas the oracle in this work is the linear minimization problem over the compact set $X$ for which there are good examples where lmo over $X$ is more preferable than projection, especially with matrix problems. The authors provided a new numerical experiment on this line.

After reading the reviews and the discussions as well as the paper with the relevant literature, I do agree with the reviewers who suggest acceptance. In particular, I think that having a simpler oracle (just lmo over a compact set $X$) compared to the lmo over the intersection of sets for which one needs a subsolver (which was used in the previous work) is interesting. In particular, in such a case with different oracles, comparing convergence rates is not always fair. Therefore, I value and find compelling the motivation of the paper as well as its theoretical and empirical contribution. I also appreciate that the paper and the appendix are well-written.

I recommend the authors to clearly describe the differences between their work and [Cao et al., 2023] involving their informal explanations justifying their worse convergence rate. Another small recommendation for the authors: you may consider slightly changing your title to clarify that you are focusing on an algorithm with a "simpler oracle". This can be more descriptive than using "efficient" to describe your method.

[Cao et al., 2023] J. Cao, R. Jiang, N. Abolfazli, E. Yazdandoost Hamedani, and A. Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. In Advances in Neural Information Processing Systems, pages 6105–6131, 2023.
Decision: Accept (poster)