TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Authors: Songtao Lu
Venue: ICML 2025 poster (2025)
Keywords: Primal-dual method
bilevel optimization
stochastic gradient descent
Primary area: optimization->nonconvex
TL;DR: This work proposes a stochastic first-order method with smoothing on both primal and dual variables, capable of finding KKT points for a broad class of nonconvex bilevel problems, with provable theoretical guarantees.

Abstract: Extensive research has shown that a wide range of machine learning problems can be formulated as bilevel optimization, where two levels of learning processes intertwine through distinct sets of optimization variables. However, prevailing approaches often impose stringent assumptions, such as strong convexity of the lower-level loss function or uniqueness of the optimal solution, to enable algorithmic development and convergence analysis. However, these assumptions tend to be overly restrictive in real-world scenarios. In this work, we explore a recently popularized Moreau envelope based reformulation of bilevel optimization problems, accommodating nonconvex objective functions at both levels. We propose a stochastic primal-dual method that incorporates smoothing on both sides, capable of finding Karush-Kuhn-Tucker solutions for this general class of nonconvex bilevel optimization problems. A key feature of our algorithm is its ability to dynamically weigh the lower-level problems, enhancing its performance, particularly in stochastic learning scenarios. Numerical experiments underscore the superiority of our proposed algorithm over existing penalty-based methods in terms of both the convergence rate and the test accuracy.

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Songtao Lu
Abstract
the two learning objectives. Typical applications include hy- perparameter optimization (Franceschi et al., 2017; Shaban et al., 2019), meta-learning (Rajeswaran et al., 2019; Raghu et al., 2020), coreset selection (Zhou et al., 2022; Hao et al., 2024), actor-critic schemes in reinforcement learning (Hong et al., 2023). and many more (Liu et al., 2021a; Lu, 2023). Specifically, it takes the form of:
Extensive research has shown that wide range of machine learning problems can be formulated as bilevel optimization, where two levels of learn- ing processes intertwine through distinet sets of optimization variables. However, prevailing approaches often impose stringent assumptions, such as strong convexity of the lower-level loss function or uniqueness of the optimal solution, to enable algorithmic development and conver- gence analysis. However, these assumptions tend to be overly restrictive in real-world scenarios. In this work, we explore a recently popularized Moreau envelope based reformulation of bilevel optimization problems, accommodating noncon- vex objective functions at both levels. We pro- pose a stochastic primal-dual method that incorpo- rates smoothing on both sides, capable of finding Karush- Beach--Kunn-Tuckcee solutions for this general class of nonconvex bilevel optimization problems. A key feature of our algorithm is its ability to dynamically weigh the lower-level problems, en- hancing its performance, particularly in stochastic learning scenarios. Numerical experiments under- score the superiority of our proposed algorithm over existing penalty-based methods in terms of both the convergence rate and the test accuracy.
min [(x, y), s.t. S(x) - arg mig g(2, y), (1) x.BES(z)
where f(x, y) and g(x, y) denote the upper-level (UL) and lower-level (LL) objective functions, S(x) represents the feasible sets that are the optimal solution set that contains all the global optimal solutions of the LL problem with re- spect (w..t.). the block-y. However, solving this class of problems is challenging. Even when both functions f(r v) and g(z, 3) are differentiable and smooth, computing the gradient of the UL loss function with respect to x may in- volve the computation of high-order derivatives of the LL loss function. For example, when the LL. loss function is strongly convex, the closed-form expression of this gradi- ent requires the computation of both the Jacobian and the inverse Hessian matrix w.r.t. the LL. loss function (Ghadimi & Wang, 2018). Many works have focused on directly opti- mizing the UL and LL loss functions by applying iterative numerical methods to perform the Hessian inverse operation, such as reverse-movt mode iterative differentiation, approximate implicit differentiation techniques (Grazzi al., 2020; Ji et al., 2021), and the Lanezos method (Gao et al., 2025), achieving good performance. However, major assumption they cannot avoid is the uniqueness of the LL optimal solu- tion, i.e., the optimal solution set S(x:) must be a singleton. This restrictively constrains the applicability of these algo- rithms for many machine learning problems where the LL loss function contains multiple optimal solutions. For exam- ple, convex LLL objective function is one of the simplest cases where this issue arises.
1. Introduction
Bilevel optimization problems have been established as general formulation for a wide range of machine learning tasks. The two-level structure enables the integration of different learning or optimization processes. This approach ensures that the solution obtained strikes balance between
Targeting this challenge, one of the most straightforward approaches is to penalize the LL optimization problem in the UL., forming a single-level optimization problem that can be tackled with existing constrained optimization methods. Specifically, the original bilevel optimization problem can be written as
'epartment of Computer Science and Engineering and Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong, Hong Kong. Correspondence to: Songtao <stlu@ eee...ccci edu...k......
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
min f(x, v), s.t. g(æ, v) (x) 5 ax

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
where g (x) A ming ((x,)) y) (which is also called value function (Liu et al., 2021b)) is obtained by minimizing g(Z, y) over y, and 6 2 0. It can be easily checked that when 8 = O, problem (2) reduces to the original one (1). In this way, optimizing the L.L loss function is transformed into enforcing constraint satisfaction, assuming that g (æ) can be obtained by some oracles. When g(z, y) w.r.t. y is convex or satisfies certain conditions, such as the Polyak-Lojasiewiez (PE.) condition, applying gradient descent is sufficient to reach the optimal solution. When 8 > O, there is always strictly feasible solution for this constraint since g" (1)) is the minimum value of the LL function. However, finding the optimal solution g" (z) generally requires an inner loop algorithm, which weakens the numerical performance of the developed algorithm in practice and complicates the theoretical analysis of the stochastic bilevel algorithm. This is because additional criteria are needed to determine when to stop the inner loop optimization process. This motivates us to explore the following question:
multipliers (sl-BAMM) (Liu et al., 2023) is still possible to perform Hessian inverse operation, provided with strong convexity property, through dynamically averaging the UL loss function with the convex LL loss function. Further, under the assumption that the LLL loss function satisfies the PL condition, it has been shown that solving the penalized version of (2) is equivalent to solving the original one in terms of the local and global optimality conditions when the penalty parameter is sufficiently large enough (Shen & Chen, 2023). The authors further develop a double-loop structured value gap-based penalty-based bilevel gradient descent (V-PBGD) algorithm that can find the stationary points of the reformulated penalty-based problem at a rate of (vv/²)) where v is the penalty parameter. The choice of v can be constant or a dynamically increasing sequence. Another possible way of choosing this parameter is con- structing a barrier function that can ensure the decrease of the LLL loss function, which is called optimization made easy (BOME) (Liu et al., 2022) algorithm, but the convergence rate of BOME is rather slow. Recent works can sharpen the convergence rate of finding the stationary points of bilevel problems up to ((1/2) when the LL loss satisfies the PL. condition, but the convexity assumption and the computa- tion of the Jacobian matrix are further required (Xiao et al., 2024).
Can we design a first-order algorithm capable of solving stochastic bilevel optimization problems where both the UL. and LL objectives are noncorvex (or weakly convex)?
1.1. Related Work
Bilevel Optimization without LL Strong Convexity. There has been a line of work focusing on solving bilevel opti- mization problems without assuming the strong convexity of the LL objective functions (Liu et al., 2020). For example, the convexity assumption can be replaced by convexity or a certain type of nonconvex property, such as the PE. con- dition (Huang, 2024). Aiming at the nonsmoothness issue raised by the multiple LLI optimal solutions, a variant of stationary points, i.e., Goldstein stationary points, is used as the metric to quantify the solutions that can be achieved by the zeroth-order switching gradient method with con- vergence rate depending on the problem dimension (Chen et al., 2023; Liu et al., 2024b:c). This kind of switching idea has also been adopted in the conditional crudient-basee method for solving simple bilevel problems, where one step is searching for the feasible set based on the convex LL loss function while the other one is for minimizing the UL loss function given the obtained solution set. It is shown that this method can achieve (1/c²) convergence rate to find the e-stationary points under the Frank-Wolfe gap (Jiang et al., 2023; Cao et al., 2024).
Moreau Envelope Based Methods for Nonconvex Opti- mization. Even though penalty methods have achieved great success in solving bilevel optimization problems, their numerical performance often falls short compared to the La- grangian method. The Lagrange multiplier or dual variable inherent in the Lagrangian method allows for automatic ad- justment of constraint violations, leading to faster empirical convergence rates, particularly in scenarios involving mul- tiple constraints (Boob et al., 2023; Jin & Wang, 2022; Li et al., 2024c). However, in cases where the objective func- tion, even in single-level constrained problems, noncon- vex, traditional primal-dual algorithms may fail to converge due to the zero-sum nature of the game involving the in- crease and decrease of the Lagrangian function. Smoothness serves as an effective strategy to stabilize the convergence of such algorithms. For instance, the smooth Lagrangian method proposed in (Zhang & Luo, 2020; Zeng et al., 2022) has demonstrated efficacy in finding Karush-Kuhn- Kuhn-Tucker (KKT) solutions for nonconvex optimization problems un- der linear constraints, with further extensions to convex or functional constrained scenarios (Zhang & Luo, 2020; Lu, 2024). Various types of smoothed gradient descent-ascent algorithms have achieved state-of-the- convergence rates in both max optimization problems (Zhang et al., 2020; Zheng et al., 2023; Jiang et al., 2025; Huang & Lin, 2023). This notable performance can be attributed to the equivalence between the smoothed gradient method and the Moreau envelope formulation of nonconvex optimization problems (Nesterov,
Given the problem formulation (2), the penalty method is one of the most standard ways to solve the constrained opti- mization problem. A min-max reformulation of (2) is con- sidered in (Lu & Mei, 2024), where the minimization is per- formed with respect to the UL problem while maximization is used for optimizing the LL problem by introducing an aux- iliary variable. Besides, if the UL loss function is strongly convex w.r.t. y, a single-loop bilevel averaged method of
(Zhao, 2024) and nonconvex min-
2

---

bilevel optimiza- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Table 1. Commaarioo of representative existing works on nonconvex hilevel optimization and stochastic functionally constrained optimiza- tion, where "gradient" indicates the requirements for accessing the first- or second-orde derivative of either UL or LL loss functions, "singleton" refers to the uniqueness of the LL optimal solution, "LL" denotes the property that the LL objective function needs to satisfy, and "KKT"" represents the case that constraint satisfaction is achieved while the slackness condition is not verified. Additionally, "cvx" stands for convex, "nevx" stands for nonconvex or weakly convex, and "scvx" denotes strongly convex.
Algorithms
Solution
Method
Gradient
Singleton
LL # of Loops
Rate
Inexact-ConEx (Boob et al., 2023)
KKT
primal-dual primal-dual
stochastic (Ist)
n/a n/a
double
O
Stoc-iALM (Li et al., 2024c)
KKT
stochastic (Ist)
n/a
n/a
double
O
MA-SOBA (Chen et al., 2024)
stationary
SGD
stochastic (2nd)
SCvx single
O
F2SA (Kwon et al., 2023)
stationary
penalty
stochastic (2nd)
sCvx
double
o (c-5)
O (c-0))
BOME (Liu et al., 2022)
KKT
penalty
deterministic (1st)
PL
double
0 (
SLM (Lu, 2024)
KKT
primal-dual
deterministic (1st)
PE
double
0 (
sl-BAMM (Liu et al., 2023)
KKT
penalty
deterministic (2nd)
cvx
single
0 (e-55)
penalty method (Lu & Mci, 2024)
KKT
penalty
deterministic (1st)
CVX
multiple
O (
V-PBGD (Shen & Chen, 2023)
stationary
penalty
deterministic (1st)
PE
double
(Iv"
MEHA (Liu et al., 2024a)
stationary
penalty
deterministic (Ist)
nevX
single
0 O
TSP (this work)
KKT
primal-dual
stochastic (1st)
ncvx
single
0 (
2005). Recent research has reformulated original bilevel optimization problems using the Moreau envelope, demon- strating that the developed algorithms can identify well- defined KKT points, particularly when the LL loss function is convex (Gao et al., 2023). Moreover, this formulation has been adapted to accommodate additional functional con- straints in the LL optimization problem (Yao et al., 2024; 2025). In (Liu et al., 2024a), it was shown that single-loop Hlssiannffree algorithm (MEHA) can find stationary points of the reformulated bilevel prob- lem, even in scenarios where both UL and LL loss functions are nonconvex.
tribute to the limited exploration of convergence guarantees for stochastic primal-dual or penalty algorithms in bilevel optimization.
1.2. Main Contributions of This Work
In this work, we propose two-sided smoothed primal- dual method, abbreviated as TSP, for solving nonconvex (stochastic) bilevel optimization problems. Benefiting from the Moreau envelope-based reformulation of the bilevel optimization problem, the TSP algorithm is structured as a single loop, making it easily implementable in a stochastic fashion. By quantifying the descent of our constructed potential function, we demonstrate that the proposed TSP algorithm can find the KKT points of the reformulated bilevel problem with a convergence rate of (11Ee)) with high probability. To the best of our knowledge, this is the first result established for quantifying the convergence rate of first-order stochastic methods in finding the <KK points for this class of bilevel optimization problems. Our numerical results validate the superior performance of this formulation as well as the quality of the obtained solutions in terms of generalization errors.
Moreau envelope-basee
Stochastic Algorithms for Constrained and Bilevel Opti- mization. More attractively, this kind of single-loop struc- ture is more accessible for developing stochastic algorithms. For bilevel optimization with a strongly convex LL objec- tive function, numerous existing stochastic algorithms have been proposed (Kwon et al., 2023; 2024b; Hong et al., 2023;
Chen et al., 2022; Shen & Chen, 2022; Yang et al., 2023: Kwon et al., 2024a; Chen et al., 2024). However, due to the constrained nature of bilevel optimization, especially in cases without strong convexity at the LL, demonstrating the convergence of stochastic algorithms is highly chal- lenging. This challenge arises because the dual variable, when utilizing stochastic gradients or functions, can be- come unbounded, leading to the failure of enforeing the constraint. Existing works on constrained optimization as- sume the boundedness of the feasible set enforce the boundedness of the gradient size (Li et al., 2024c; Jin & Wang, 2022; 2024), which is theoretically overly restric- tive, or they adopt variance reduction techniques or large batch sizes to mitigate random noise (Alacaoglu & Wright, 2024; Shen& & Chen, 2023). These factors collectively con-
The main contributions of this work are highlighted as fol- lows:
The developed TSP algorithm is gradient- based, single- looped, and stochastic, making it easily implementable for solving bilevel machine learning problems in a com- putationally efficient way.
The theoretical iteration complexity of TSP is O(c with high probability for finding the <KKT solutions of the Moreau envelope-reformulate tion problem. To the best of our knowledge, this the first time a stochastic first-order method has successfully
3

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
achieved the approximate KKT points of the bilevel op- timization problem where the LLL objective function is weakly convex.
terms to the UL objective function, similar to existing works dealing with nonconvex optimization (Zhang & Luo, 2020;
Zheng et al., 2023; Lu, 2024), resulting in the following smoothed Lagrangian.
Numerical results further emphasize the importance of finding the KKT points of this class of problems in com- parison with the stationary points in the penalty-based reformulation of bilevel optimization problems in terms of generalization performance.
K (I, 2. 0: A) A f(z, + >(g(x((( (1((,))) v) - 12, v)
6)
2 11--211 21 + L¹ 1l
01'
(6)
2
where E. y have the same size as x, y. It can be easily checked that given T, D. the smoothed Lagrangian strongly convex w.r.t. x and y when p is sufficiently large. Next, the algorithm design for finding the equilibrium points of m.. maxx20 (xx,, y, T. y: x) is fairly straightfor- ward. We can apply the linearized Lagrangian method or primal-dual method to update the optimization variables using only (stochastic) gradients.
Due to space constraints, all technical proofs are provided in the supplementary material.
2. Primal-Dual Method for Moreau Envelope-Based Bilevel Optimization
In this section, will introduce a single-lopp gradient- based primal-dual method designed to solve the following Moreau envelope based reformulation (Gao et al., 2023; Yao et al., 2024; Liu et al., 2024a) of the following general stochastic bilevel optimization problem.
Dual Update. Based on the Moreau envelope- based LL optimization problem (6), we further propose updating the dual variable using a moving average technique, follows.
min
f(x.y)= - F(2.1:)) 2.
(3a)
E-Dui.
h"
(1-0)h"
s.t. g(a,y) - F7 v) 8
(3b)
+ +0()(""''")- - )') - || - y''l" -0), (7a) 27
where
X = Proizo (X" + +
(7b)
(2, e min min E G(a, 2))) E-Duu.
2/ 11= yl1 27
(4)
X++1 (1 1) + +Nx
(7c)
denotes the value function of this problem and serves as
where r stands for the index of the iterations, T denotes the step-size for updating the dual variable XC. Proj2 0 is the nonnegative projection operator that ensures the iterates re- main in the nonnegative orthant, and μ and 0 are smoothing dampening parameters for the dual variable À and the auxiliary variable h. respectively. Here, g(r. y) denotes mini-batch stochastic approximation of g(x, v). computed using a fixed number of i.i.d. samples from the LL data distribution DLL The moving average applied to model parameter updates reduces their aggressiveness compared to traditional primal-dual methods, improving the algorithm's robustness stochastic errors.
a lower bound of the original LL loss function, F(x, y: E) and G(r,, yr () respectively denote the stochastic UL. and LL loss functions, PLL DUL respectively denote the UL and LL data distributions at each level, and y > 0. Let g(2, y) A EE-DLL G(z, y; g). When 8 = O, it has been proven in Theorem 1 (Gao et al., 2023) that the problem formulations (1) and (3) are equivalent when g(z, y) is con- vex and in (Liu et al., 2024a) that the solutions of (3) that satisfy the constraint (3b) are also stationary points of the LL problem (i.e., satisfying [/ (1, 9)1l 0) in the orig- inal formulation (I), when g(r, y) is weakly convex with respect to y.
Primal Update. After that, we can use stochastic gradient descent (SGD) to get an estimate of 2* *x1,, v) given and y.
It is also worth noting that when y is small, the I.I. loss function becomes strongly convex in z, ensuring a uniquely well-defined LL optimal solution. This motivates the devel- opment of an algorithm based on this smoothed problem (Bai et al., 2024), particularly in practical stochastic settings. Towards this end, we can construct the Lagrangian function of this bilevel problem as follows:
1 (x (or--') -3))
2 ++ = x" - hx 2²) +
(8)
where is the step-size, and ng (zx 2) represents the stochas- tic gradient estimate of V=g(æ, =) with a constant mini- batch size of independent samples.
C(x, y; A) - f(x, v) + M(g(z, v) - (2, y) - 5)
(5)
It has been established that function 95 y) is differen- tiable when E (0, 1/2))) The rest of the algorithm design involves simply applying SGD with respect to the remaining variables using the function K(x, y. J. G: X) and replacing the unknown 2 with its surrogate +1+1_ Specifi- cally, the updates for y is
where the nonnegative À denotes the Lagrange multiplier or dual variable for the inequality constraint (3b).
After using the Moreau envelope smoothing technique on the I.I. objective function, we apply the proximal smoothing
4

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
nxth = 30"
A3. (Coercivity) The set {.,v][(x,)) R, R,g(,,)) (4,2x, S 6) is bounded for any R>0 0.
+x (1g((".0))
2 5²) --ー) + ply - 8)). (9)
7
Assumption Al implies that g(z, y) is weakly convex in y for any fixed æ; with weak convexity parameter p used throughout the paper.
followed by
-+1==-- +
(10)
Remark 1. Assumption A3, which requires the objective
where 3 denotes the step-size for updating variable y, and < w 1 is the smoothing factor for updating 7. and (1, y) and hg(2, y) represent the stochastic gradient esti- mates of VyJ (2, y) and V v1 v). respectively.
function to be closed over its open domain, is widely used in optimization theory to ensure bounded level sets and the existence of minimizers (Boyd & Vandenberghe, 2004). In practice, incorporating a small l2-penalty into the loss function is common technique to enforce bounded level sets.
Similarly for v, it is updated by
x x+1 xx - a [1d (I" ((""",," ,y + X* x*+1((1((zx (12(2"), ,r
Further, we make the following standard assumptions on the stochastic properties of the gradient estimate. Let us define the gradient estimation noise involved in the primal variable update: Egg (x, y) - hg(z, v) Vag(r, y). Egg (2. y) & ( v) - Vug(z, Eg. (x, v) & hg(2,, =) V u2( =), E,z (/f(,, -) V.,((,, w), EX, A h v) y) V v (2,, y), define the stochastic gradient
12" [x((,,²)) + plx² -F)) (11)
followed by
= 3 + +ww F"),
(12)
where a denotes the step-size for updating variable z, and O < < 1 is the smoothing factor for updating T. and (z, y) and hg (z, y) represent the stochastic gradient es- timates of v= y) and Vag(z, y). respectively. A sum- mary of the implementation of the TSP algorithm is pro- vided in Algorithm 1.
Regarding the dual update, estimation noise as cq. - 6(r, v)).)())(rr))))) y), Eg. - 0(x,
2). To ensure theoretical tractability, we make the following assumptions on these quantities.
A4. (Stochasticity of Gradient Estimate in Primal Variable Update) Gradient noise E[s, = 0 and E[[ls [|2] og and E[s,,] represents any of x; y, with respect g, and x.
and ,||lE, = o where
Algorithm Single-loop stochastic Two-sided Smoothed Primal-dual (TSP) method for bilevel optimization
with respect to f. while E denotes the expectation conditioned on all past gradient estimates up to the most recent iteration.
Initialization: step-sizes: T, 0, 17, a, B, variables:
x², ",,",,2,," ,," X 1 =0
1: for- 1,2,,...- , ,T do
2: Compute hr*1 by (7a)
A5. (Stochasticity of Function Estimate in Dual Variable Update) Function noise B(Eg.] = 0 and Ei]leg Il 0g. where - represents anyone of y, z.
3: Update *++ x , by (7b) and (7c)
4: Update 2*+1 by (8)
5: Update y*t! and g+ by (9) and (10)
6: Update x1+1 and +1 by (11) and (12)
3.2. Iteration Complexity of TSP to the KKT points Given the above preliminary assumptions, we define G(x, A) as
7: end for
V V.C(x, yi A) V, y A)
3. Theoretical Convergence Results
((x, A
We first need make the following blanket assumption to showcase the convergence behavior of the proposed TSP algorithm.
and use [| y; A) as the stationary gap. Then, an (c, 8)- approximate KKT point of the constrained problem (3) is naturally defined as follows.
3.1. Assumptions
Definition of (e, AApppooxieet KKT Points. A point (x", (x",y", , x²) called an (e, appproximmtee KKT point if satisfies the following three conditions: 1) stationarity condi- 2) constraint violation condition:
These assumptions are mainly related to the continuity and boundedness of the UL. and LL objective functions.
A1. (Smoothness) Assume that functions f(r y). g(x, y) are differentiable and jointly smooth with constants Lf, L, w.r.t. both x, y.
tion: [| y²; X <
Ig(x*, - g3 v²) 5) S 3) slackness comple-
mentarity condition: [1 ".at,,0 ,y") 9, (2", "et"", y²" - -||||**|| <
A2. (Boundedness) Assume that the objective function fzz y) is lower bounded and denoted as f.
Now, we are ready to show the following theoretical conver- gence rate of TSP.
5

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Theorem 1. (Convergence Rate of TSP to the (e,e)- Approximate KKT Points of Problem (3))- Sup- pose that AI-A5 hold. Assume that the iterates {x", ,,,""", ",, """" X", X are generated by TSP. If the step-sizes a, 3, T, wi 7) P. 0 are chosen as (1/VV)) and the parameter p OX"), then for T 2 () the fol- lowing results hold with high probability:
D(G,0:A) _ min ( z.y
(14a)
P(t, 0) _ min  - ح|
+ - 71 (14b)
a.EE)(a)
where }(x) _ { g( g² y) s 8). and
x² (T. T; X), y (i, 0: A) ف arg min K (z, y. G. A) (15)
s.y
denote the optimal solutions of problem (14a) given the reference point (7, G, A). Similarly,
19((', ;0;x,+ sc,
(13a)
x (T. 1). D (T, arg min f(a, v) + 21 - -21 P (.))V(a))
Σ
g0(" v²) - (2'x""²²)) -el- Se,
(13b)
lly 2
(16)
T r
Σ K
|la(" ,²) 97 - 1 S 2 (13c)
denote the optimal solutions of (14b) given (σ. 7). Then, we can utilize these quantities, which serve as intermediate anchors for monitoring the optimization process, derive the descent lemma for TSP.
T
where e > 0, 1. denotes the positive part, and T is the total number of iterations.
Descent Lemma. After one round update of vari- ables by TSP (i.c.. from (x", yy,,"" T", V,,,", xD) to (x'+1 .y² 21 pr+1, g X xIt1), ) we obtain the following intriguing result.
Remark 2. The convergence rate achieved by TSP is optimal, as it matches the lower bound of standard SGD for solving single-level smooth nonconvex problems (Arjevani et al., 2023).
Lemma 1. (informal) Assume that A AI-A5 are satisfied. Sup- pose the sequence {s", .y,, 2", H V. N X__ Vr} is gen- erated by TSP, with p > L and X" S A. Additionally, as- sume that y", " I), and (F",, x+++ are bounded. Then, if the step-sizes are chosen appropriately, we have either
Remark 3. The batch size used in TSP is a constant or of size 1; therefore, the sample complexity of TSP is also ( O))")), which is consistent with SGD.
Remark 4. When g(z,y) y) -f(z, y), the bilevel problem (1) reduces to the min-max optimization prob- lem min, max, (x, y) under the weakly-convex weakly- concave setting. Under assumptions A1-A5, the analysis shows that the iterates generated by TSP remain within a bounded region without requiring additional projection. This implies that the loss values remain bounded over the constrained domain, where approximate stationary points of nonconvex-nonconee. min-max problems are shown to al- ways exist and can be found in polynomial time (Daskalakis et al., 2021).
-
- O
E
[1" 11 x²] x²]1
2011 1 1 0-1
E
[
8a
83
1
1-112- - P
8w
- O2 (1- ||" =="(x", "="<=",""|l" )²
4
| (8", "") - 211 + nte
(17)
16p7
3.3. Proof Sketch
Ex
x²1
1
11 -
P | 3T1R
4a
'43
' 'ww
The theoretical proofs guiding the algorithm to achieve this iteration and sample complexity mainly consist of three key steps: 1) constructing a potential function Q" to track the convergence progress as the algorithm proceeds, 2) bound- ing the size of the dual variable given the bounded gradients, and 3) deriving the probability that the iterates remain within the bounded region.
0711 (1 (1-p)C ==-==""x",,""" (=''"""")1" m²)
4w |1
2
O(A2 and ||' - X,,(", 0-)l - O(TTA) -(TA) (18)
where nia is the noise term resulting from the gradient esti-
mate, 0 < 4 < 1, the coefficient C² = O(x), and L, A are some positive constants.
Thanks to the smoothing terms introduced in the Moreau envelope reformulation, the function K(-) with respect to the variables x or y exhibits strong convexity in each sub- problem. Mathematically, these subproblems can be defined by the following quantities:
From this lemma, it follows that the potential function is either monotonically decreasing up to some noise ball or the generated iterates have already converged to neighborhoods of the stationary points with radius of (ATT)) In the first
6

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
case, we can easily show that the algorithm will eventually converge e-stationary points, provided that Q" is lower bounded by some constant Q. In the latter case, we need to derive an upper bound for the dual variable by selecting sufficiently small step-sizes for TSP, allowing us to conclude that the iterates have reached the e-KTT points.
where {() is the cross entropy loss function, Y denotes the ith entry of y', and d is the dimension of the LL vari- able. The LL objective function is defined & (r, y) & Σn= (2,))((, Et), where & ~ Du. m denotes the total number of training data samples, Ty denotes the ith entry of vector z with dimension m. Here, y denotes the weights of the neural network, including one hidden layer with param- eters of size 10 784 and corresponding bias, and p is the nonconvex regularizer parameter. To ensure fair compari- son, we follow the numerical experiment setup from (Shen & Chen, 2023). Specifically, we use the MNIST dataset, splitting it into three parts: 5, 000 training samples, 5, 000 validation samples, and 10, 000 test samples. Additionally, 50% of the training data samples are randomly assigned incorrect labels as polluted data.
Bounding the Dual Variable. Given Lemma 1, we can quantify the difference between successive iterates, which plays crucial role in upper bounding the dual variable.
Lemma 2. Under AI-A5, suppose the sequence f- yy, ,2",,", .y, N, N4,,Vr is generated by TSP. As- sume that y². hlg and hg are bounded. When 8 > O, p p (1)), 8 = Oe), and the step-sizes are chosen on the orler T-/22, then X' is upper bounded, ie., there exists a positive constant A such that X S Vr.
Experiment Setup. In the experiments, mainly com- pare the performance of the proposed TSP algorithm with three closely related algorithms: BOME (Liu et al., 2022), PBGD (Shen & Chen, 2023), and MEHA (Liu et al., 2024a). All these algorithms are variants of penalty methods, with MEHA being designed based on the Moreau envelope- problem formulation, similar to TSP. Due to the similarity in algorithm structure, we use the same step-sizes and initial points for all tested algorithms. For TSP, we further choose the step-sizes for updating the dual variable À as 0.01 and set = 1. We also adopt the test accuracy to evaluate the quality of the obtained model parameter y and the Fl score to measure the effectiveness of the hyperparameter x.
This result indicates that the dual variable X" remains bounded. However, since the gradient estimate can be un- bounded due to stochasticity, we further assess the probabil- ity that the gradient estimate remains bounded.
Bounding the Random Noise. By leveraging the prob- abilistic bounds on gradient magnitudes generated by Adam or SGD (Li et al., 2024a;b), we establish a heavy- tailed noise bound for TSP with bounded variance in the proof of Theorem 1. Specifically, we define the follow- ing random variables: 4 _ min {r Q" -0-Q= > }m) A T, t2 é min (r ||="max|| > Gm A T, where a A b de- notes minfa,b), b), and emax represents the largest magnitude of gradient estimate errors among Eg.. The thresh- olds Qth and Gn are predefined thresholds.
Experiment Results and Discussion. can be observed from Figure ((a) that TSP achieves the highest test accu- racy among others, which is the major learning objective of this problem. This suggests that the model obtained by TSP generalizes well to the test dataset. Although MEHA also achieves high test accuracy, it is worth noting that the accuracy obtained by MEHA drops rapidly as the algo- rithm progresses. This is major issue with penalty- beased methods, as the penalty parameter continually increases to enforce the constraint, leading to overfitting of the model to the LL learning problem. Similar issues are evident in the results obtained by BOME and MEHA. However, it is not entirely fair to compare these two algorithms, as they are designed for cases where the LL loss function satisfies the PL condition, which is not the case here. Figure 1(b) shows the F1 scores obtained by these methods. Both TSP and MEHA exhibit similar results, further confirming that while the UL solutions may output similar results, the LL solu- tions can differ significantly as the LL optimization variable is optimized across the two levels. It is implied that the KKT solution, (which is further explained in the appendix), may provide more generalizable results. Figure ((a) illustrates the convergence behavior of the tested algorithms during the training phase. It can be observed that TSP exhibits a faster convergence rate in terms of iterations compared to the oth-
The variable to quantifies the time at which the iterates become unbounded, while & links the term Q" to mea- sure the gradient magnitude throughout the iterations. Let t a min(t1, t2). Based on the derived descent lemma and concentration inequalities, we show that the probability of t < T is small, implying that the probability of = T is high. This directly ensures that the gradients remain bounded before T.
4. Numerical Results
In this section, we evaluate the numerical performance of the proposed TSP algorithm by comparing it with state-of-the- art bilevel optimization algorithms, particularly those based on penalty methods. These methods are closely related to the idea of penalizing the LL loss function using the UL
loss function.
Data Hyper-Cleaning Task. This problem can be formu-
lated as
min tH RER" WERd
E (),,E),
(19a)
2
s.t. y E arg min (x, B'ER
(x, v/) + -p)
(19b)
+ y!
7

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
92-4
92
test accuracy
F1 score
91.3
91.4
TSP BOME PBGD MEHA
TSP BOME PBGD
90.3
MEHA
90.8
100
300
400
600
700
200
1000
400
700
soo
1000
number of iterations
number of iterations
(a) Test accuracy
(b) Fl score
Figure 1. Convergence and generalization performance comparison of TSP, BOME (Liu al., 2022), PBGD (Shen & Chen, 2023), and
MEHA (Liu et al., 2024a) in solving the data hyper-cleaning problem.
100
meta test accuracy
meta train accuracy
96-
99
85
ANIL
ANIL PBGD
PBGD
MEHA
MEHA BOME TSP
BOME
TSP
number of iterations
number of iterations
(a) Test accuracy
(b) Train accuracy
Figure 2. Convergence and generalization performance comparison of TSP, ANIL (Raghu et al., 2020), BOME (Liu et al., 2022), PBGD (Shen & Chen, 2023), and MEHA (Liu al., 2024a) solving the meta-leaning problem.
ers, which is generally attributed to the dual variable update that balances the two levels of the learning process. It is indeed well-known that primal-dual algorithms practically converge faster than penalty methods, although the theoreti- cal analysis of this method is much more challenging than that of penalty- -based approaches.
1 K
min a.wo))
f(x, (v(o))
(x,
ErDDeal
K
s.t. V(o) E arg min E V((
((x, M()):
for [K].
E-D((
Here, the UL problem involves shared model parameter layer, denoted by æ, which typically corresponds to the common feature encoder or backbone network shared across all tasks. The variable y(1) represents the task-specific head parameters, i... the final classification layer for task i, which is optimized using the sask-specific training data (())
We further check the peak test accuracies obtained by these algorithms, which are follows. TSP achieves a peak test accuracy of 90.4% with a variance of 0.0429% and a peak Fl score of 92.4% with a variance 0.10.. comparison, the peak test accuracy BOME is 90.06% + 0.23% with an Fl score 91.99% + 0.17%, the peak test accuracy of PBGD is 90.01% 1 + 0.23% with F1 score of 91.95% + 0.17%, and the peak test accuracy of MEHA is 30.34%+20 + 0.17% with an Fl score of 92.38% + 0.12%.
Experiment Setup. this experiment, the shared hidden representation has size of and is followed by eight indi- vidual perceptron layers, each corresponding to a specific task. The MNIST dataset is partitioned into eight subsets based on digit labels, with each subset containing 2, 500 training samples and 1, 500 validation samples. Each task involves recognizing digits in a distinct way, where the data samples contain only one type of digit per task. We use sam- ples labeled with digits through 7: five digits are allocated
Representation Learning with Multi Head Architectures. We further evaluate these algorithms on meta-learning prob- lems using a multi-head neural network structure. typical
formulation can be written as follows.
8

---

TSP: A Two-Sided Smoothed Primal-Dusl Method for Nonconvex Bilevel Optimization
for training and validation, while the remaining three are used for both meta-training and meta-testing. Each meta- task corresponds to learning from one digit class, and each LL problem is associated with its own task-specific head and dual variable. We conduct an exhaustive search over initial step-sizes from {1, 0.1, 0.01, }.001} and penalty pa- rameters from {1, 0.1, 0.01, 0.001, 0.0001). }. reducing them in the order of VF. The gradients used in all implemented algorithms are stochastic, with batch size of 32.
References
Alacaoglu, A. and Wright, S. J. Complexity of single loop algorithms for nonlinear programming with stochastic objective and constraints. In International Conference on Artificial Intelligncce and Statistics (AISTATS), pp. 4627-4635, 2024.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Experiment Results and Discussion. As shown in Fig- ure 2, TSP achieves the best generalization performance, even though it does not attain the highest meta-training accu- racy. The key role of TSP in this framework is to adjust the dual variables individually for each lask-specific head. This flexibility helps balance the optimization dynamics between the shared and task- sss--specific components, thereby improving the generalization capability of the learned representation across unseen tasks. This numerical example further high- lights the advantage of solving bilevel learning problems using the TSP method and underscores the importance of its ability to achieve KKT solutions.
Bai, X., Zeng, S., Zhang, J., and Zhang, L. Alternating gradient-type algorithm for bilevel optimization with in- exact lower-level solutions via Moreau envelope-basee based reformulation. arXiv preprint arXiv:2412. 18929, 2024.
Bertsekas, D., Nedic, A., and Ozdaglar, A. Convex Analysis and Optimization, volume 1. Athena Scientific, 2003.
Boob, D., Deng, Q., and Lan, G. Stochastic first-order meth- ods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(())215- 279, 2023.
5. Concluding Remarks
In this work, we propose a single-loop structured gradient- based Lagrangian method for solving nonconvex stochastic bilevel optimization problems. By leveraging the Moreau envelope reformulation of the LL problem, our proposed method can find KKT points for this class of bilevel prob- lems through a constrained optimization perspective, signif- icantly expanding the scope for solving two-level machine learning problems. Our major contribution lies in establish- ing the high probability descent lemma with dual error bound, enabling to quantify the boundedness of the dual variable and conclude constraint satisfaction. Our theoreti- cal analysis justifies that solving stochastic bilevel optimiza- tion problems can be as easy as solving single-level ones, measured by iteration complexity and KKT conditions.
Boyd, S. P. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.
Cao, J., Jiang, R., Abolfazli, N., Yazdandoost Hamedani, E., and Mokhtari, A. Projection-free methods for stochas- tic simple bilevel optimization with convex lower-level problem. In Advances in Neural Information Processing Systems (NeurIPS). 2024.
Chen, L., Xu, J., and Zhang, J. Bilevel optimization without lower-level strong convexity from the hyper-objective perspective. arXiv preprint arXiv:2301.00712, 2023.
Chen, T., Sun, Y., Xiao, Q., and Yin. W. A single-timescale method for stochastic bilevel optimization. In Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2466-2488, 2022.
Acknowledgment
This research is supported in part by project #MMT-8115077 of the Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong.
Chen, X., Xiao, T., and Balasubramanian, K. Optimal algo- rithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1-51, 20244
Impact Statement
The major goal of this work was to develop computationally efficient machine learning algorithms with rigorous theo- retical guarantees using optimization techniques, focusing on algorithm design and theoretical analysis in data sci- ence applications. Its main impact lies in deepening the understanding of learning algorithm dynamics, with broader implications for developing new theorem- prrovin methods for optimization algorithms. This research does not signifi- cantly involve ethical issues or social consequences.
Clarke, F. H. Generalized gradients and applications. Trans- actions of the American Mathematical Society, 205:247- 262, 1975.
Daskalakis, C., Skoulakis, S., and Zampetakis, M. The complexity of constrained min-max optimization. In ACM Symposium on Theory of Computing (STOC), pp. 1466-1478. 2021.
9

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Franceschi, L., Donini, M., Frasconi, P., and Pontil, M. Forward and reverse gradient-based hyperparameter opti- mization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1 1165-11777 2017.
Jiang, X., Zhu, L.., Zheng, T., and So, A. M.-C. Single-loop variance-reduced stochastic algorithm for nonconvex-coneave minimax optimization. arXiv preprint arXiv:2501.06677, 2025.
Gao, B., Yang, Y., and Yuan, Y.-.. LaneBiO: dynamic Lanczos-aide aided bilevel optimization via Krylov subspace. In International Conference on Learning Representations (ICLR), 2025.
Jin, L. and Wang, X. A stochastic primal-dual method for a class of nonconvex constrained optimization. Compu- tational Optimization and Applications, 83(1):143-180 2022.
Gao, I.. I.,, Ye, J. J., Yin, H., Zeng. S., and Zhang, J. Moreau werreenceoo-weaaly-ooooo reformula-
Jin, L. and Wang, X. Stochastic nested primal-dual method for nonconvex constrained composition optimization. Mathematics of Computation, 2024.
envelope based tion and algorithm for bilevel programs. arXiv preprint arXiv:2306. 16761, 2023.
Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv:/80..02246, 2018.
Kakutani, S. generalization of brouwer's fixed point theorem. Duke Math. J., 803):457-459, 1941.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning (ICML), pp. 18083-181 2023.
Grazzi, R., Franceschi, L.,, Pontil, M., and Salzo, S. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning (ICML), pp. 1748-3758 2020.
Kwon, J., Kwon, D., and Lyu, H. On the complexity of first-order methods in stochastic bilevel optimization. In International Conference on Machine Learning (ICML), 2024a.
Hao, J., Ji, K., and Liu, M. Bilevel coreset selection in continual learning: A new formulation and algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. On penalty methods for nonconvex bilevel optimization and first- order stochastic approximation. In International Confer- ence on Learning Representations (ICLR), 2024b.
Hardt, M. and Simchowitz, M. Course notes for EE227C (spring 2018): Convex optimization and approximation. 2018. http:://e222c.gghhbb.ooooeeeee/
pdf.
Hong, M., Wai, H.-I., Wang, Z., and Yang, Z. A two- timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-18)) 2023.
Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie, A. Convex and non-convex optimization under generalized smoothness. In Advances Neural Information Process- ing Systems (NeurIPS), 2024a.
Huang, F. Optimal Hessian/Jacooian-ffes nonconvex-PE bilevel optimization. In International Conference on Machine Learning (ICML), 2024.
Li, H., Rakhlin, A., and Jadbabaie, A. Convergence of Adam under relaxed assumptions. Advances Neural Information Processing Systems (NeurIPS), 2024b.
Huang, Y. and Lin, Q. Oracle complexity of single-loop switching subgradient methods for non-smooth weakly convex functional constrained optimization. In Advances in Neural Information P Processing Systems (NeurIPS), pp.
Li, Z., Chen, P.-Y., Liu, S., Lu, S., and Xu, Y. Stochas- tic inexact augmented lagrangian method for nonconvex expectation constrained optimization. Computational Optimization and Applications, 87(1):117-147, 2024c.
61327-6133 61340, 2023.
Ji, K., Yang. J.. and Liang. Y. Bilevel optimization: Conver- gence analysis and enhanced design. In International Conference Machine Learning (ICML), pp. 4882- 4892, 2021.
Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. BOME! bilevel optimization made easy: A simple first-order ap- proach. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 17248-17262, 2022.
Jiang, R., Abolfazli, N., Mokhtari, A., and Hamedani, E. Y. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), pp. 18305-10323, 2023.
Liu, R., Mu, P., Yuan, X., Zeng. S., and Zhang, J. A generic first-order algorithmic framework for bi-level program- ming beyond lower-level singleton. In International Con- ference on Machine Learning (ICML), pp. 6305-6311 2020.
10

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Liu, R., Gao, J., Zhang. J., Meng, D., and Lin, Z. Investigat- ing bi-level optimization for learning and vision from unified perspective: A survey and beyond. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 44 (12:)10055-106) 2021a.
Shen, H. and Chen, T. A single-timescale analysis for stochastic approximation with multiple coupled se- quences. In Advances in Neural Information Processing Systems (NeurIPS), pp. 17415-17429, 2022.
Shen, H. and Chen, T. On penalty- bilevel gradient descent method. In International Conference on Machine Learning (ICML), pp. 30992-31015, 2023.
Liu, R., Liu, X., Yuan, X., Zeng, S., and Zhang. J. A value- function- bbased interior-poine point method for non-convex bi- level optimization. In International Conference on Ma- chine Learning (ICML), pp. 6882-6892, 2021b.
Tyrrell, R. R. Convex Analysis. Princeton University Press Princeton, 1996.
Liu, R., Liu, Y., Yao, W., Zeng, S., and Zhang. J. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In International Conference on Machine Learning (ICMI.), pp. 21839-21 (166,21866, 2023.
Xiao, Q. Lu, S., and Chen, T. An alternating opti- mization method for bilevel problems under the Polyak- Lojasiewicz condition. In Advances in Neural Informa- lion Processing Systems (NeurIPS), 2024.
Liu, R., Liu, Z., Yao, W., Zeng, S., and Zhang, J. Moreau envelope for nonconvex bi-level optimization: A single- loop and Hessian-free solution strategy. In International Conference on Machine Learning (ICML), 2024a.
Yang, Y., Xiao, P., and Ji, K. Achieving D(e-1.5) complex- ity in Hessian/Jacobian free stochastic bilevel optimiza- tion. arXiv preprint arXiv:23 02.03007 2023.
Liu, Z.., Chen, C.,, Luo, L.., and Low, B. K. H. Zeroth-order methods for constrained nonconvex nonsmooth stochastic optimization. In International Conference on Machine Learning (ICML), 2024b.
Yao, W., Yu, C., Zeng, S., and Zhang, J. Constrained bi- level optimization: Proximal Lagrangian value function approach and Hessian-fres algorithm. In International Conference on Learning Representations (ICLR), 2024.
Liu, Z., Luo, L., and Low, B. K. H. Gradient-free methods for nonconvex nonsmooth stochastic compositional opti- mization. In Advances in Neural Information Processing Systems (NeurIPS), 2024c.
Yao, W., Yin, H., Zeng, S., and Zhang, J. Overcoming lower-level constraints in bilevel optimization: A novel approach with regularized gap functions. In International Conference on Learning Representations (ICLR), 2025.
Lu, S. Bilevel optimization with coupled decision- dependent distributions. In International Conference Machine Learning, pp. 227789. 2023.
Zeng, J., Yin, W., and Zhou, D.-X. Moreau envelope aug- mented Lagrangian method for nonconvex optimization with linear constraints. Journal of Scientific Computing. (1(2):61, 2022.
Lu, S. SLM: A smoothed first-order lagrangian method for structured constrained nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Zhang. J. and Luo, Z.-Q proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal Optimization, 30(3): 2272-2302 2020.
Lu, Z. and Mei, S. First-order penalty methods for bilevel optimization. SIAM Journal on 3etimiiaaatoo,344111993933 1969, 2024.
Zhang, J., Xiao, P., Sun, R., and Luo, Z. A single- loop smoothed gradient descent-ascent algorithm for Iinconvex-concavy min-max problems. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7377-7389, 2020.
Nesterov, Y. Smooth minimization of mon-h functions. Mathematical Programming, 103:127-152, 2005.
Raghu, A., Raghu, M., Bengio, S., and Vinyals, O. Rapid learning or feature reuse? towards understanding the effectiveness of MAMI. International Conference on Learning Representations (ICLR), 2020.
Zhang. J., Pu, W., and Luo, Z.-Q. On the iteration com- plexity of smoothed proximal ALM for nonconvex opti- mization problem with convex constraints. arXiv preprint arXiv:2207.06304 2022.
Rajeswaran, A., Finn, C. Kakade, S. M., and Levine, S. Meta-learning with implicit gradients. In Advances in
Zhao, R. A primal-dual smoothing framework for max- structured non-convex optimization. Mathematics of Op- erations Research,
Neural Information Processing Systems (NeurIPS), 2019.
2024.
Shaban, A., Cheng, C.-A., Hatch, N., and Boots, B. Trun- cated back lack-propagatton for bilevel optimization. In Inter- national Conference on Artificial Intelligence and Statis- ties (AISTATS), pp. 1723-1732, 2019.
Zheng, T., Zhu, L., So, A. M.-C., Blanchet, J., and Li, J. Universal gradient descent ascent method for nonconvex- nonconcave minimax optimization. In Advances in

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Neural Information Processing Systems (NeurIPS), pp- 54075-544 -4175--410, 2023.
Zhou, Pi, R.,, Zhang, W., Lin, Y., Chen, Z., and Zhang, T. Probabilistic bilevel coreset selection. In International Conference on Machine Learning (ICML), pp. 27287- 27302, 2022.
12

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
A. Preliminaries
In this section, we provide some technical preliminaries for the proofs of the lemmas and theorems claimed in the main body of this paper, including parameter definitions and supporting results.
A.1. Notations
The definitions of the parameters and assumptions are further listed in Table 2.
Table Summary of Definitions. ("Lips": Lipschitz: "grad.": gradient: "const": constant; "opt": optimal; "." represents the gradient
taken w.r.t. either z or y.)
A1
Definition
Annotation
V. V.f(x,, y)
V.f(x', v)ll $ Ly x'll
grad. Lips. const. of f(x y) w.r.t a grad. Lips. const. of (I.,y) w.r.t y
V V.r( y) v. S Lylly 1/1
L
V Vug(z, v) Vug(z, Lglly - v'll
grad. Lips. const. of g w.r.t y
Table Summary of Definitions. ("Lips.": Lipschitz; "grad.": gradient; "const.": constant: "opt.": optimal: "." represents the gradient taken w.r.t either or yi "[x; y)" denotes the concatenation of x and yi PEB: primal error bound; DEB: dual error bound.)
Const.
Definition
Annotation
E
If(z, v) f(z.8)) Eylly s
Lips. const. of f y) w.r.t
lg(x, v) - g(x,5/) s fylly y'll
Lips. const. of g(1, y) w.r.t. y
Eg
Ig(x, v) g(x'.v) S Gg11=- x'|
Lips. const. of g(x, y) w.r.t. x
by
197 v) $ s'll (ef. (32))
Lips. const. of 97() w.r.t y
[IV y; A) V/)
L
grad. Lips. const. of L() w.r.t. æ,
I L1{ (z':3/) (cf.
g
[V. V.g(=',u)] < Lggl1z - x'1
grad. Lips. const. of g(x, v)
[V,)) Vgg(2,/)]l s Ly1ly lly - v/l
Lips. const. of Vg (z, 3) w.r.t. y
L
(V, Vo9(2', s 111x r'll
Lips. const. of Vgg (Iz, y) w.r.t. Lips. const. of 2*() w.r.t. 2, y grad. Lips. const. K () w.r.t. x, const. of PEB w.r.t.
L
(I, =²xx',0") L,]l(r,)) - (a', ./0l (cf. (30))
LK
pcf. (22))
p(p L) -1 (cf. (24e))
01
(p+ L) - L)-1 (ef. (26))
const. of PEB w.r.t.
03
(p- L)- (cf. (27))
const. PEB w.r.t x" or y
((2r,2 + +2)02) (T(p -)) (ef. (233))
const. of DEB abbreviation of T.
v _ (2,
In Section C.2, we will demonstrate that the iterates (such as x", x", (5" "" (")" for which we need to evaluate the gradients or function values of g(z, y), (x, y), and fa, y) are bounded, which implies that the corresponding Lipschitz continuity holds. To be more precise, ly, Lags by are listed in the section of notation in Table 2.
A.2. Primal Error Bounds (PEBs)
Recall that the definition K K(x, y. 2, A)
K(x, y. R. D: X) - f(x + Mg(x,1) - (, 6) + -1l F112 +
P 2 211
01
(20)
Based on the assumptions listed in Table 2, we have that f()). are gradient Lipschitz continuous. For simplicity of the presentation, we assume that S I.g. Therefore, the Lagrangian C(x, y; X) is gradient Lipschitz continuous with parameter,
13

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
given boundedness of X,
I, I 1, + ((ig Tny) where L, denotes the gradient Lipschitz constant of 9n (2, y)-
(21)
Subsequently, function (ax, y, T. 75 X) is strongly convex of and y with parameter p- I. and gradient Lipschitz continuous with parameter
LK - L
(22)
The closed-fone formm expressions of the (deterministic) gradient of the smoothed Lagrangian based on are as follows.
V. V.
v) Vzg(s, =)) + p(l T),
(23a)
V,R(u,,,,, X) - V (z. A
Vug(z, y) - y +py 1)
(23b)
V.R( vg(2 v) + 2ー y
(23c)
?
Given these properties and the assumptions listed Table 2, we can obtain the following primal error bounds that have
been studied Lemma 5 in (Zhang et al., 2022), Lemma 3.5 and Lemma 3.10 in (Zhang Luo, 2020) and Lemma B.2 in (Zhang al., 2020). To be more specific, from Lemma B.2 in (Zhang et al., 2020) we have
(2, Tr A) 1/" (2,
< 0 || 77 ||,
(24a)
| (2, A) (0', A)
5 01 2| F'],, ||,
(24b)
(2, - ("(
< 01 11 7/,.
(24c)
|,* - ="(''
S a ã 5
(24d)
where
A
(24e)
p P-L
L
Similarly, following Lemma B.2 in (Zhang et al., 2020), we can also have
||v (G. T A) 1/ (2, X S 02 - X||,
(25a)
||0 (6, -) (2,0: X) S o2 A XI|,
x²
(25b)
where
02 4 p+ T
(26)
p L
Let
03 4 1
(27)
D-L L'
From Lemma 3.10 in (Zhang & Luo, 2020) Lemma 5 in (Zhang et al., 2022) we can directly get
03
11
++
11
y'll.
(28a)
3
[0"""" xr+1) x <
03
1x r+1 x=1 ||.
(28b)
a
(0" F ( --+1)--++1] < u r1 y"11 |a"" (F", --t))
(28c)
< ab 1|,0
x")
(28d)
where the primal error bounds (28b) and (28d) hold as K (which is used for updating X:) is also (p- - L)-strongly convex and (p + L)-Liscchitz smooth, and
1+ 3(p L)
0.
(29a)
8(p- L)
1 1+a(p L)
0g 4
(29b)
alp- L)
14

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
A.3. Lipschitz Continuity
Lemma 3. When & E (0, (2p)) and function g is gradient Lipschitz continuous with parameter Lig and weakly convex with parameter p. [I= y) ="<x', ,') is Lipschitz continuous, namely, there exist constant Lı such that
(x²)) (x', of M S L (1. y) (o'.8)))
(30)
where
max Lag +}
L A
(31)
(2. y) Lipschitz continuous with Further, when function g is Lipschitz continuous with parameters g functtin 9- parameter Eg., namely, there exists constant Eg. such that
197 (z 8/)1 S 60 lly 8'll
(32)
where fo L,(1 + Lggg). Also,
10 (2, v) (² s')l s lg (1,,, (0', v/ + T.gbo1 1/ x'11-
(33)
Proof. From the optimality condition, we have
Vglo, + (z. - y) 0,
(34)
7
1 Vgla, *,,,"")),,)))))) + (x 1/) - 1/) = O.
(35)
As function g(x,2) + 1 || y/12 is strongly convex with parameter 1/(27) 1/(2p) when y (0, 1/(pp)), have
Vg(x, 2* (x, (x, (x, Vg(x, 2zx,'00) y xxx 9) 2" (x'
} 7 -p) D) [1= () - 20',, 1//.
(36)
which gives
- || (z, (x, - 2'<''
(37)
Vgla', x" (x', v/1) 2* ./) - vf
2²(x,11) -y 2" "xx v) 2" 2= ,0))
Vg(0, (2' (a'.v')) v/1)
7
- 7
Lo 2' +
l1 2/(l] (|2" (a 2- 2²'2'
(38)
Therefore, we have
(x, - 2" ="(x', (''''''ll s L21l(z, v) - (a', 1')l
(39)
where T. defined in (31).
15

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Under assumption AI, we can have
(x, (2.10)
1
o(0,22 (z. u)) g( 2" (z, + ||2 vll - - (2,
(z. v/ - v/1²
(40)
27'
24
== < {=*"(a,)) x (z, v\1 27 (2" (x, v) - y - (x, - v/, =* (2, v) y + x" =² -n'>
L.lly 1/1l + 2z v)) Vg(z, (x.
(41)
< L.lly n11l + + (x,
(42)
(43)
Similarly,
(7 v) 97
c(z, 2 (x. g( (2'.g')))))))))))) + / (z,0) yl
27 12 2 ./) 8112
(44)
27
$ $1>"(,,9)) 9) 212',//1 27 (x, - (s'('', v²), 2" (x, y + 2' - -y²
S T. L121(<,,)) v) - -g Va(a', ,/)))
(45)
< -
|| ('d'//')))
(46)
$ L, =, (14 2'|l.
(47)
Lemma 4. Given (I, and generated by TSP, when Y E (0, 1/(2p) and function is gradient Lipschitz continuous with parameter by and weakly convex with parameter Ps namely, there exists a constant eg. such that
1
(x -9(,))))(x,))) 2)
_ || y112
< l. 11,222z,,, v) =||
(48)
27
Proof. Given any x; y. it implies that 2* (xx y) is bounded due to the strong convexity of the function when y E (0,1/(2p)).
From the update rule of z, it can be shown in (220) that sequence z" is also bounded.
(,(x", v²) 0('",z")
- =1=" v²
27
$ 1g(x", ,2 v²))
(11=(x",,0 ,,) 1f -122 - v/1
(49)
24
1
< sg(l", *x",,, v/)) g(d", .2')1 + ((="x",,)) w/) -0) (5" (²), - + (-" y²))
27
1
< 1g(x" (x" (( g(0", 2,2) )) +
(2* (x", w²) 2" -0) 1i
(
27
< Lagl=*(x" 5²) - z1'l + 27
[1 (x", ,3") - =" -/)
2 21 1|, (x", v²) z"1l
where (a) holds due to the boundedness of sequence {z").
For notational simplicity, we define e, == max(fy lg + L.ghg).
16

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
A.4. Stochasticity of Gradient Estimate Noise
Without loss of generality, we assume that max _ stochastic noise in the gradient estimate, establish the following relation between the iterates generated using the ground truth and their counterparts estimated with fixed mini-batch of data samples, where the difference is bounded by For example, for the update of the variable y, we have
g, gy, of / . 3 0². Based the assumption regarding
E
y gr v" + + xx+1 E
(Voy(t' ,y") + 2r V¹ +ly - -
-3 V v3) e%2 +X
(50)
7
yr+ yn
(51)
where the expectation is taken over the underlying data distribution, conditioned on the historical iterates up to the current iteration r. such way, we can have
y r+ 3¹ = 13 [B y'] + BE
(52)
where e - E', + +
Similarly, according to (23a), we also have
x1 = x- - a (1/f("", X++1 (1g(2".)) - 1g( 11((0"2 + p(xx - o)))
(53)
which gives
x r1 x²= = E [x x²] + oE
(54)
where ox A Eey +x#1 ( -
B. Convergence Analysis
We now present the proofs, related results, and technical details that establish the lemmas and theorems our convergence analysis.
B.1. Descent Lemmas and Dual Ascent
B.1.1. PRIMAL DESCENT LEMMA
Lemma 5. (Primal Descent Lemma) Under AI-A5, suppose that the sequence {x", V 2", "", V. X", Vr) is generated by TSP. When
0< 0, 4LK'
0<ws1, and
(55)
then the primal descent inequality holds, namely.
K K(x"
+1 +1; = - K(x", . 2 ,,,,,;;,' ;x) ",+
< 2a
| [1r 1=1 1 2/3 [ +1 y/ '1' P
||
3/
P
10
+1 T-1
2w
2n
(o(x".") ,.")) 97, 1000000 ./') - 8, ~+1 )²) + B
2
|1
2" (x", //
- ( 11)) - x= (x" (x",y"+1) y2
- (V<'K( o 0. y xx,1) + L
-[V" of . 7: x ),,)) + L 1
(56)
where Ex= A EE,, + e and o , + x
17

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
Proof. y-update: From (9), one step of gradient step gives
K(F", y T" 0", ; - K(x .V',"', ; 11
VK((", of " 7: x tr v²) + LK 110 1r - y
(57)
(VK("", y", F", ;7; x ) B 1y - 111) + Lx ||ا [y - -2" + e
(58)
1
E 5/] 1| + 3 11 ==xx,,
< 2/
3 v K (x", V. ,. T.; (7x k2) + Ix 11,31
(59)
where (a) holds due to the Lipschitz gradient continuity,
v VyR(et v. 2" 8" ;; ) E [y+ v'))
+ V Kx ,9', T 0 x - v Rx=", ('; -v1)
1
E [vrt] - 11
B
Rx'(''' V , ", : ||
1
+
V. K(x,, ,,, ; x
+
|
[v" [v 11
(60)
4/3
3
E [ y² w² +3
:'' - v.
x* (x", v²) y¹
(61)
43
7
7
3
S
E [
y²] 112
+
1| - 2" (x", 1²
(62)
43
72
and 3 S 1/(4Lx).
z-update: The update of x shown in (1I), which is the similar as the u-update, gives
K(x+t1 4r1 xr, 1- x-+1- K (x", / 1," ",,"""""""" "0" 1
(2) (VK("", y T x ), E [1r - x²}>> + LK
|EE [2 r+ - x=]1?
(63)
2
VR(x", v +1 ,", T 1 x E +1 +1 x²)) + I. [|[x - x0'
2
+ VK(2", 0 T x Va("", y ++| 1rt1 ".", gr+1;,rt1 E [x-+] -x")) =²))
a V v ,,
(64)
where (a) follows from the gradient Lipschitz continuity of K (2,, y, F. Tr A) with Lipschitz constant Lx. From the optimality condition of (11), we have
(2 +1 8r, g 1 1)t1), E [xrt1-x"]] - x²1)
1 [ [xrt1 - x=1l" S
(65)
Regarding the last term the right-hand side (RHS) of (64), we have
(VK(T", t 1 g (1:t))) - vi(a", t1 x0t1 , G +1 ; ( ) E [ - x²]]
S a V th " -. vî(x", t 2 x. g. x x + 1
E [xrtt_=="]]
x=]] 11
4a
where we apply Young's inequality with parameter 2.
For the first term at the RHS of the above inequality, we can further have VV x t1 3r, g - vk(x", (("",,"+1,, 22, grt1, ) (X (2+t)221VV " , (2", , Vg(a", 2²)
(66)
< L1)11 - z" (x +
(67)
18

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Substituting (65) and (67) back to (64) gives
(xx**² +1 y D", 1 ; - K(=", y ,", grtt:artt ;
B x go z²Ill ||2 + a(x + Lg )11|=" - (z' .f )1
2a
a V K (x", .v ,0" ) = + 1xa?11=11?
(68)
where we select S 1/(())))
G-update: From (12), we have
K( K( (( 1 grrt, ; - k(++1 , "x, : 1
(1la0*11 - 11++112 - ||--~ - x 1))
(69)
(I" -5+11, ,,+,,,,11_ +1+ + x²ト - }
(70)
(0) p 2w
| -3+- 11
(71)
where (a) holds due to
(x g1+1 , r1 gr+1 + r1 -8)
+x*+1_ r+1 - -3) = (1-3) 2
(f" g141 r+ F" + xx - z1+1 +
|
11
(72)
and (12) for 0 S 1.
--update: Similar to the t-update. From (10), we have
K(x,, of Fr, o x K(x", v 11,,,,, Fr, ;x++++
P
10 +1 7/ 12
2w
X-update: After the dual variable is updated, we have
"(x",v"" "";;, k( VF, ",,;,)') (0(00,0'' 02 6,, - X7)
(73)
1.2. DUAL ASCENT LEMMA
Lemma (Dual Ascent) Under AI-A5, suppose that the sequence (x" ,,, ,,,""" x" 30 T. N Vr) is generated by TSP.
When L, the dual ascent inequality holds, namely.
D( 17 1 -
D( :
1r1 1 X X N( (8 ; yf (8", (
(, (x", ;" x (8 x(11))
P (0TT) T. 7 + - " T +1 x (
+ (5rt) 3 xx- - 2x (3 +1 x+11)
(74)
Proof. Recall
K(g,y,0,6; 2) A ((x,)) -M)(2,)) ,, - 5) P 111 01 -1ll ~1
19

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
We have
D
D(E -((",
(F"'(F", 00 , (8' 8f ; ;,++)) )," 0 ; K(x (f", ;'
x H y :
(75)
(5) K(x (F', ,
F 8 1ht1)
K(a g
F. Di; 2
(76)
@ (11"(E", T ; 
: - 4 12)
(77)
2
20 200 T. 00 +1 + + - 2y (7) x
(78)
Similarly, we can obtain
D(1+1, , 1 - D(F",
g+++;++1))
-K(x (3++1, 1 x
g x 1iee tith
- K(x (T', 1 ; x
(79)
((+'("+)), x ;1,1x
1 ,r 0 (
)) ei 5. 1 (1tr! P (1== "itrtt,0tt,,,.. ; न ||2 x (0  ; ( 1T)3)
(F+ .
(80)
(81)
P (0 2
5r, 2r, + 5- 2x ( gT x )*))))-
(82)
Then, we can have
D(",T;X** - D(F Tix)
= =K(x'(T' ",
- -K(x T
(83)
(0)
2 (F "
K(x'(" T ; (8 ; ) x2)
(84)
= -N (T", T x ),y² (T" &( - (F", (F", ), (8 ("".0: ;(rr+))) 5)
(85)
where in (a) we use the definition of yy ( T.; x for p > L.
Combining all the above gives the desired result.
1.1.3. PROXIMAL DESCENT LEMMA
Lemma7 7. (Proximal Descent) Under AI-A5, suppose that the sequence {x", x², ,,, "I ,,,,,, Vr3 is generated by TSP. Assume that y (z" TT) is bounded and p >> L, then the proximal descent inequality holds, namely,
p( 10--Po P(2".77 55" (f", .y") + p(2 - -F(""
S p(0 "0"
p p
2 p- I +1) (110 5/ || - 37 112)
(86)
Proof. First, note that K(x, y, P, Ø; A) is strongly convex w.r.t. x and y jointly with parameter p - L. Under A1-A3 and the assumption that "" (()")") is bounded, we can obtain that VpP("" ,,') = p(ū' - " ("",0")) by applying the Danskin's 's theorem in the convex analysis (Tyrrell, 1996; Clarke, 1975). Then, using the primal error bound (24c), we can show that
20

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
V P(T",, .7) has a Lipschitz constant, i.e.,
( P
+1)
100
(87)
p- L
Therefore, it is straightforward that
P -(7 -
+ p P
2/2
2 p- + +1) 11 - -2
(88)
Similarly, we have
V2P 1/ - 3 x ||| s (_ (-- -
1
(89)
which gives
p( 1,0T,,11111 11) P( .1
+ P p 2 pp +1) -211
$ -p')+t1-2''(6 - x3 g
- -z')'(0'
(90)
B.2. Proof of Potential Function
Lemma 8. Assume that A AI-A5 are satisfied. Suppose that the sequence {x", Vf, ,,,,,"," ... Vr) is generated by ,
TSP, p > L, and y.,, T (3", (x",8') ) are bounded. When a, B,w respectively satisfy (55), then, there exists a constant Ç such that
Q(x-+1, -y+,1 22+1 ,0+11 ,0" g++1:110 ( - -Qxx" .V',""" ;
1
03
C2 222 + n1:
2 ))
1
Ch. 16 9 + L2)
|| 11"+1-a0 =x1112
|N, (8', V) X-12
2a
a²
8μT
1
Che
16u1(ez 1:2)
03
20(A+ 2T, C2
2T. + Th= ))
|| [1r -y']l"
2B
3
1
(1
1
)-,))))))
| 11 D
1
p T, o( |,5 5-11
4p
P
+ p
+
2w
2
+ 6pc (1|=* (3", :
(8" .0)) (("""")))"(""")))010((0- 1y (5" NN .²)) 1 (f", (0))))
(1 0) 2/
|| - VAK(a"
-11
(1 (1--1))-0)))))))))))111 00)==11"" 2x"" + nie (91)
where C2 is defined in (143), potential function
Q A Qxx ,²,,","""" x" ,,,""," x') & K(x", V. F. 2D("".0))) 2P((""''' M(N h²)
+ 211
| - VAK(<
x²)] C.11=" - =x" ,0)0
(92)
and
n/g 2 nā(a, (a, 3, T, 0, E/
S/ Ey E )
A a V K (x", 1
x f x )²²")) + Lxa?|le211 - 3(V, ,,, ; + Lx 11Eg11
?²
+ (1602p( + Cha))
max || = 1 CCn (n. (T
0
+ (E8, - S/. 1+ \²)
+ T (( - = (hh + 0g(("" .)))) + 02( -2
(93)
240
21

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
Proof. Recall that
F' K(x", ,0,
(94)
Merging (56), (74), and (86) gives
Ex E"
|
r+
2"11"
E 1 r+ - 0²111
20
23
P
2p
P
|| 1-1 ( P
2p p
110
711
2w
p L
221
p p-1 L
lo(x, 11) - (1' ,3¹) 6, 1, 1-+1-17 -77
Falle" 2² 20',, .0 )I + a0 (,, 311=" - =² (x", 121
B
+ 72
2(A N' (F'
(8 ;x ;)t1)
(1t))) 6)
a (V.K(e K(=K""",>>
(x",""" ,v 5
< + Lxa21lef11
3(V, K K(=',(('' 16" F²' - [)) + Lx 1EE2
- T + -y (
y (
1, )) 2p (fr+1 V (i 17 7"
3" x (x' .0 +1 x²) - p( F", , 8- 2x ( +1 T t1 : 2p -
(95)
where we use the fact that p/ (p-1p) L) > 1 so that there is a factor of 2p in front of terms
| - 12 and 17 - 87 112
First, we can get an upper bound for the term in the penultimate line of (95) as follows:
(T T, T - 2y (Tr+1 -V. - 57'
X - 5F
y" (F",
p (Tr+1 - -V',1' (3", - -'
(96)
= --100++1 8/ + -7 (F
( 3/ (F" (F'
- p (g - ,",'"" (f", T ;+ - (x", -"
(97)
For the last term of the above inequality, we can further have
p ( +1 T., V","" (T T x (x" ,T)
p 17 +1 111
PC
+
1ly (f", 0¹; ( 8 (x 1'12
(98)
2ç
2
For the second term of (97), we can get
T. . 11" (8" 10 x // (3 x
8 I'll (3" f
3/' (8", (2
(99)
P
| - 1
(100)
p L
where (a) is true by applying the Cauchy-Schward inequality, in (b) the primal error bound (24e).
Similarly, we can obtain an upper bound for the term in the last line of (95) as
p ( 3", 3- F' (x*(2 (ar+1 g +1 ( (f".7* ,(+1))
= -p (3 32, - - (arttr 11 x0 (3", th: (rt1)))
p (3r+1 - -,''"' (8", - 3F" "
(101)
=-plläri - - + 2p (5r+1 - ن ( ; x² (3" x
53 -, (
x (7"
(102)
22

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
For the last term of the above inequality, we can further have
p ( F,, (T", " +1+ ( - (x" 18".8""1 .f+
p pla +1 8' 112
PC
|| (x", ;0 x²) x²(2", 0
(103)
25
2
Similar as (100), we also have
(x 8r x² (3++1, , "0'"", "8""0""" ;
(2) |+ - x5" |||| (f g x x² "0" T7 - !
(104)
(2) p | F 1
(105)
p
where (a) is true by applying the Cauchy-Schwarr inequality, in (b) we use the primal error bound (24b).
Substituting (98), (100), (103), (105) into (95) yields
E E
1
B
[xx--
- x² [1 28
[v -
2a
4p
|| 8' -2 ( 2w [
(1
4p
))
110 100 1-1
+ p- L
2w
p
a (V,K((" (2", " 2 1
) );=,) Lxa2
B(V,K(E" (E", V
2 + LK 1EEg1
/ lee - =" ,y
-
17122" - (z', )1
- PC (1 , ;+++++++++++++++ - 7 )1 + 11 (8", Tf x - (F" 0')
- -2(N - X' N'
(8 """""""""""""""""""""""""""""""" 1² (2"("' T; ; (3 )) -6)
- Lola" v²) - "2 -,, X7)
(106)
Second, we will give upper bound of the last two terms of (106) follows.
Step 1.)
For any given h, the Moreau envelope of the dual update can be written as
- 11X ~112,
1
M(A. h) min X' - A)+
(107)
27
which directly yields
A = Projzo(A (A + Th).
(108)
obvious that the quadratic function MA, h) is smooth. Let Las denote the gradient Lipschitz parameter. From the optimality condition, we can have
1 (44 - X2,x Xx, 20.
h +
(109)
7
23

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
Let 0 cp and w' - g(x" ((" - -²x²==")==== - -1====1' y-1 6.
M( ,/+t) - MM
- 1 -17 - -,0, x²)
(
- -,), --x--))))-- -10)
1 LM
2 ) (11-+1--71 21 +
+
+11h/1111 - 13
(110)
24
(
1 X1 - X7 - - xr12 -712-0(12 ,') + O(T ,,,
1
LN)
(11 1112 + |1 - -1713))
(111)
27 2
114 - 1-112 - -014 - X", w²) + ( 1 27
LM +
(11-11- - +14 - 1171?)
(112)
2T
2
where (a) is true due the strong convexity when is small, (b) update rule of X and h**1, in (c) we apply the optimality
condition (109), i.e. (h, X5 X3 2 - | X and (X4 N,h h2*1) I 1 /2 + || 1/
Therefore, we can obtain
M(N, h²) ((x++1,h"*))
0
114 - 12112 + 0 ( (Bte" .v"' - ,²' 1
27 || -- 121
8, 8,14 )²)
Lm + 1
+ 2
(11+11- 121
- + 111 1 11)1)))
(113)
27
Divide on both sides gives
1 c
- ( ((x+t))(+t))
2T IN - -X'12 + p (OLE" (0(=".0)- - -g(x",2)
27 -1=0~ v011 - 8, -1'11
1
-x)
LM + 1
(11-11-00) + |11 - -1"113)
(114)
2c
200
Note that term (g(x", .4") - "7(2", ,y) 8, x -²' can be decomposed as follows.
(g(a", ,") 07 , )²) 8, 11, - Xx>>
(0(x" . - (, .y²) 6, xr1 - X²)
+ (olx", ..)' - g(0,,2) 1
1
112 1- - 8, 1 -X
((x,,8") - g(x",²") -
||2" - 8 - 5, 6,A -
27
27
+ O(x", .o'"."") - g00 21) 1
1
12"
1-
8, 8 - xr)
a(x", ,3²" 600 ,²)
||"" - y" 12 6, x- - 2²)
2y
27
< 2 (g(0", (1)) 0, - 6, A - 17)
(5 ..) g(0 (t
1
1|"
1/ 1,,
27
+ (0h c/1, x-11_ - X")
(gla", ,1"') - [00 ;-)
1
|:2 - 1/ 2- - 5, 11 X²)
(115)
27
24

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Subsequently, we can derive an upper bound for the sum of the last two terms in (106) follows.
2gg("", 07(0" " ,y); -7)
2 (9la (F", x
).9' y2 (3", . - -f("""")000""""
). (F", ;1;;))))) Nr11 - x²)
+ "7(0", .0' g(=",²") 2
||2" y 11112,1 xr) x
+ (E - - 1r x²)
(ole. (((a")") - ((c",2²) 27
1
||" 5' 1 6,2 -1r) 1r)
8/4 [100oT.0 ) - 02 ,1)
(0 (x0("0 F3; x ",y (t", :. - -
+ -uutl12" - (x",,, ,z" y²1 1 1 - 2112
24
+ +0% -G/. 1r+1_ - -2-- - (Blor.0)) (16".v" "0(",, ,²¹ 27
1 1|2" - 1²112 5, 5,1 2²)
(6)
S 16nlle + 1.2) (1x=0(0 ;0; ( - 1²112 + 11","(,,, ;0; - y²1l3)
+ &utBE1E" - (=",, v012 1x - 1
24
+ + -e/. - \r+1 -27- - (oler, .v"" -g (()=,2²))
1
|| 10112 - 6, - x²)
-
27
(0)
$ 16uule + -2)00
a 1111==11 -x"113
1
1 1l - -11
+ 8putt - 20" (0²22)))1
2/u || 2
32
+ (e% - xrt1 27) - (gl"r -0=00""" 27
1
||" y01 6,1711_ - xr)
where in (a) we use the Cauchy- Seuuhy-Schwarz inequality, (b) is true due to the Lipschitz continuity, i.e.,
1)1 < 269 (1|=7" x=" (3", 7. x-+)) + 11 - - T; (
19(x", - g(0*
100))(((((( (3", "(="((",
(116)
and
107 ,v²) 57 (x*("" (F", "0,,0;"'' ;xx
), 0² ",", Ti (
< 262 (1|=" x (a", T"; )1 + 110" - -3" 8.; \))))
(117)
in (c) we apply the primal error bounds (27) and (28b).
Let
= ,8 V., FF - 2D(""00")') + 2P 8 M hh")
(118)
25

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Step 2.) Substituting and back to (106) gives
F+1
FD
1
16u(l3+ + L.)
03
| [xtt] - z²]11²
(
1
(6 + L3) o3
|| [ - -
2a
a²
2/3
82
1
4p
1
4p ))
+
|8 - -1=
+
11 - T112
2
p 1,
2w
p
( ?2
+
+ Splla)
1|=" - - 20
, . )| + aeA 1 1.g) R1== - =""",, / ||
+
+P (1x0 (x", g+ : ) - x' (8 1 )| + 110 (F", (F"; x D' (3" 7")
a (V,((*') y [+] F² g+ x
( Lx 16 B K
,' " x + 1x531
1 | -2112 +
Las + +
+ 2/1
-
2T
2e
207
210
LM 6
+
|1r+1 - 101l2 + (=z, - 17).
(119)
2c
20y
When constant y is small, i.e., 27
1 2 Lss 2 we have
114 - 2 +
Las +
1
+
1
|
-
S - 47
-I 114 - 2
(120)
47
2c
20y
24
where we require < 1/2.
Step 3.) Applying the reverse triangle inequality, we can get
|44 00)
X ||
||* - 22 |||*+1 - (3" (8"
x112>
X (x", 00)1 (121)
Combining (121), (123) gives
14+1--X0 - | (T", 0T) - 2T11 - -
2
Applying the primal error bounds (27) and (28b), we can obtain
H1 124
1711== = 1
-
27
2417
S |1,,(0", 00 21122
118-
(122)
24
According to the definition of X_""",,,, ("" (cf. (234a)), we have
||- XI ( T 1| (a)
2 |X + + M x
< 1 - (o
(123)
Next, we need to derive the recursion for term ||
V K (w"; (x";
112 First, we decompose
26

---

TSP: A Two-Sided Smoothed Primal-Dusl Method for Nonconvex Bilevel Optimization
from the noise terms as follows.
1/ +2+ +2 - (A ),+")),) 2 (u* ;,tt),, w 112
< (1 (1-00)1t +0 g(x", ,/" 0(x", ;²) 1
1| - y 1/122 -6)
27
- VxK(x* (o((="("++) (u"t1; ; ) ) , 11,11 2
(124)
= 116 + 0[g("", ,v) g( = + 0 055 - S.S. (11 + 0(0(2', ,))) + Pog, -%2/²²
where
hn = (1- 0)h + 11 -1'1=--''1p--- -0)
- -0
,00 ,
(125)
Then, using the convexity of |1||2 we can obtain
[11 [1-o0)Tt +0 [0(x' 10 - x0)
1
- || --112-
2
-ViK(o* x
$ (1 - 0) VAK(I
+ 201 V K[ (c
+ 20 g(0", /' g(x",, ,²)
27 || - 8/ 2|2 8 TXKK
+2- 240(e) + e. [of|Ex" Ex" 2- of 0r 2
(1 - 0)|11 - V2K(2
- - - -x11))
+2 +2.30(c + +,)² J0 [Bx
-
- 2112 11
/ |
40 - =x113)
(126)
S - 1))
,1,),,)) + + +2) (1of - 0) +
|Ex 1+1 x=11
a²
+ +6(e, + +)) (40((10))- +) 050
|By |By 5/ - 6 + 6, EX++1 - 2712
where in (a) we apply
(1 +1 y :1 x
), x²( (x"t1 ,,(); (x',""""'''''"""""""""'>""""")"' (t (A)) + + (x y x
() 07 (o", (o". xx)'))
< 4(eg + Et)
g (2" (2''0"))))17))
(127)
< 24( + +1 -
- x111)
(128)
and
10(0", )² (g(x", ,²²) + 3 || yr(l²) - g(x (2" v/ N' (0 (()))) + (t (1 (2", w";
1
x
24
5 (eg + +2) (11=0" xx (x", ;-)" 11'* yy (x' ;,;;""") II)
(129)
< (gg + +4)) 03 |x 2"' +
03
||y +1 1''l + 20 |E -X1I)
(130)
3
27

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Let
0
Ch. = 6 (eg + Eg)
T
(o0 -0) + a²
(131a)
2p
40o(( 0) + 0
Chu
6
T
(Pg + (g)
(131b)
2p
Cha = 6 T L + 2003.
(131c)
2p
Finally, by observing the dual error bound, we need further quantify "","""";;""""" ("",7"") +
(0" , - x3"," 112 as follows. Note that
$ """
+ -1
(132)
(0)
2 2 - 77)
+ +,
+ +100 6o 7
(133)
(6)
2 2 (F' (1
(f,)0)) - (2"
+ 80 1
+ 60 1
(134)
where in (a) we use the primal error bounds (24e) and (24c). (b) holds as we first apply the primal error bounds (26) and (25b).
Let
=== F + Elhtt "1
(135)
24
As result, we can get
Gr+1 G
1
Ch.- 16p(( + 12) o3
+22)
[or - -
Ch, - -66 + 117) o/
|| [y r+ s/]
5
2/x
a.
2,3
1
(1
(1
4p
[11) )) | 1-
(1
4p ) - -OCof) 115 - 7/
P
+ ---z))
(
+ p-b L.
2w
(5
2w
+
SuL2
1| - -z ==" (x",1"))1 + a(x Lg) )11== - (x",
(x".1"" "./"t/+))) 2112
?2
+ Jpc (1|0" (x",
- +1
(8", .))) (0""
5 (3" (2))))
(1 - 1) 2/ 11 r1 Vx
T
a (V.K(1 (2", " r+ H 01 ),+) + L
B(V, (x", y. , F T x
+ Lx ||=
IINE - 11112 4μr
1
| (T", """' - 2112 + 803 || [ "") - Ex++112= + Cn, - -EX11
2T
+ (6% - -66. 1++1_ x²) + (0(5%) - (/6 0g(('' 5')) ( - -5% ())
(136)
Note that
- - 2 (F, x112 + 21| - 112
(137)
28

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
and
||- - 1 1²1r- -
(138)
Then, we can get
P |N x1==
1
1
|X, (F", (7) - x11 S03p< || p (3' 00) EN++Y12 + Chay |
2T
4U0
1
+ 1603xC)
|x"("""0" 121 + (~ 8T
1 + 1603pc + Cha) 1
8UUT
72 1
+ (1602pc + Cha)
max 1 - 11
(139)
1- r
where we use the fact that
72
- -
-
> - s
max | 5% 11
(140)
1 1-
Further, we have
||~- - 2x" (1t,1 =2 21k -
11=", 2- (x=, , )1²)
(141)
2 21 2, )12 + Ey +1 371
(142)
Let
3
C2 A 72
8yl + 20(A++1Lgg))
(143)
Let define the final potential function as
Q' G² C2ll" (1'" S.
(144)
Substituting (220), (143) to (136) gives the desired result.
Q"
- Ch - 16p((e + 12))
03
C.
22I2 + nT.z2)
2 ))
E [1r - -x']1²
1
(F" 00) - X212
2a
a
1
o3
22 + nL:
2 )) |B [b7 1- y''l
Chy 16p(l1 + 12,
2a
2 - C.
23
12
1
{
1
+
p -
4p
1 - 2
1
+ p p L ) 6{
4p
11 0'
2w
2
+ +pc (1 (3", :14 - -F
77)
(0,
-1 0) 2p
|1 V,K(x* (v'
x
0211 -2 (x" .9')
a (V,K(I') (x", 21 ,", g +1 x
Lka ", + LK 3 3
?²
+ (1602p< + Cha) ) 1- max 1,
c.h 12 + C.nt, (n, En Ey,
+ (=), - = : A+1 - \") + T
0(55) o (h5 + 0(( v\)) + ( - - (2)
(145)
24
where the terms in the last three lines are noise terms and defined n5 _ nb(a, 3 F, 11, 0,0% 0g, 6 (g
29

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
B.3. Descent of Potential Function
Lemma (Formal). Assume that AI-A5 are satisfied. Suppose that the sequence {x", y ,², F",,,, NY, X,,,,,r Vr) is generated by TSP, p L, and X < A, x', y", g "'.."" (3 : are bounded. When the step-sizes are chosen such that (149), (150), (151), hold, then, we have either
2 +++1=
O
1
|
x
r-
x² z²111-
1
LL [1r+1 v²111²
P 1 1-11
1 -1
8c
83
8w
8w
(1
x² z² 2²(x", )11
| (T", 87) 12222 + #n
(146)
16μT
or
L B 12
11
1
B [v
3 31]1?
p "w
|| 1-1 (1 - p)
|| 2" 0')1(}]
x=xx2,00)113
4a
43
$ =C
(147)
where C
2. 8 6²
22, C2 is defined in (143), and
||^
s 8ur 2 GpCo..A.
(148)
Proof. From (91), it is clear that if we select the step-sizes properly that the coefficients in front of ||Ex++ x" ||? [Byy++1 y² || - F 2| || 7 2 are strictly negative, then the potential function Q" will be decreasing. To be more specific, the step-sizes are chosen as follows.
1) Selection of a. Given the condition (55), we request
1
o30
16p((2 + [12) o3 a²
n2 )
1
18 (eg ( + E)) Ec) 24
[40f(1 -0+ a²
-c,
21 +
(149)
2a
2
4a
2) Selection of (3
oo
111
18 (e+ C.) (00((1 0) +
16 + +12)
-0 [1gg² 1.3 C. 21 +
>
0. (150)
23
2p
8²
B2
2
4
3) Selection of w.
1
1
4p
1
+
&Çoo
> 0.
(151)
2w
p
L
4w
i...,
1
w <
(152)
4
4p
6Ç
5
p-L
Then, consider the following two cases:
Case 1.
1
| 2 r+1 21 1
E +1 y 2']l
P -1art1-991 -
max
2
4a
43
4ww
P
| 8/1 (1 - C)
(x" 11
1
|| (3" . - x712]
4w
2
8pr
6pc
(11 (1"" ( X (8", 1)) (5
+ | ( T. XI (8T T)) =0000
30

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
In this case, have
@++1
O
1
E 22 2²]11==
1
L [y
v']11== -
1 -1 1-
11
-1
8a
83
8i
8w
(1 C2 z² (2 y'll
14", 7 - 122 + n
(153)
16μT
meaning that Q" is decreasing each step.
Case 2.
1
1
E [xx =²]11²_ 1
E [ v']
p || 1-112 P
10 g²1
max
2
4a
48
4w
(1 (1= ||2" ,"(x",""'1" "))
1 (x' - -x1p
2
S 6pp (x", 17; N1',
(*", - (1
Recall the weak error bound
1 WW -"
1awl1> - -1
(154)
where A(e) E arg maxx20 (1)
We can get
--)"
A0 (x", ,7),' ||
(155)
which gives
||^ - X, 8pr 2 6..
(156)
Then, we can have
P 4w
10
1/'1
< 2- 6pS (1ly* (3" - (0) xx" (8)))))
$ 2 20 - -x"(""
(157)
< 2- 8. 62 22 2o,
(158)
Similarly,
P 2 - 1,,,, (1 C) 4es
4 +1
x²
E y
1|" - 2 20",", (,","''² 1/)01
4a
43
2
< 2
62. 22
8
22 20 pZ
(159)
CC
These results imply that the iterates generated by TSP will converge to some point within a ball with a radius of O 2TT).
31

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
C. Boundedness of Dual Variable, LL Variables, and Potential Function
C.1. Boundedness of Dual Variable
Lemma 2 (Formal) Under AI-A5, suppose that the sequence fa" .V, ,,,"=", "", "',, .r, is generated by TSP. Assume that y" and hy and h2 are bounded. When > 0. p = ((A), 7 = ((1) = === = - 3 = = (/2), such that p > I. and a, B, satisfy (149), (150), (151), then, the sequence {X*} upper bounded, iee, X S for all r, given a sufficiently large T, where A is constant.
Proof. From the update rule of variable y, we can obtain
X+1 (gg(e" v²" z" -)))++=)))))) - [nf(e", [1](,";z")++( +ly - -7) 1 f( - -0')
7
Multiplying v" - z" on both sides gives
hittng(a' v²) ,²) - =z") ---MMee M/ x' + plu" 2²) + 1 -0) -z")
x+1 11y 2/112
v).
x²)
+
(160)
7
Note that when y < 1/p, the following function
1
((z,3,2) g(x, 2) + 3 -- y/1
(161)
2
is strongly convex w.r.t. 2, i.e.,
(0 v, 2 (l,, + (V.p(1, 2. v)-
(162)
Therefore, we have
1
H(*", + 2 -| - y- 2 7(x 50 + (1g(2" ,y",, 2-=--- - -15),
(163)
27
which is equivalent to by some simple algebra manipulations. Subsequently, we can get
(hg(("")))) - 2²) 2 20" ,2) g(x" ,2²)
27 ||"" - 112
(164)
x=+1 g(=".v")
1 v/) - -0(x",,")"
_ ||=" -1(13)
27
M1(00.000 v/) + ply" - =²) + 1( "²), -xr) 1=+1
7 111" =111
(165)
We assume that X" and h" are bounded. If "n = "(~", - 0(x", 2 - 1²1 - 6 < 0, it implies that h*+1 < max((1- 0)h + Ow", 03 bounded automatically, giving the boundedness X4 and * Otherwise, note that from (7a) have
-1 -1 + 5= Ø(x" v)) - [(x,,²" - 1
_ || 1/1
24
Substituting it back to (165) yields
1 1+1 S - ( (1 ./""'"')) + ply" =z") + 3 51 y²). v" -z²) + x+1
1
γ 11 27112)
11 r1 35" "1ll"" - =2"ll + x-+1
< 3/1 [1/((a", (2",""")111 "1ll""" - -z"1l + -111000 - =="lll"" - =I"ll || +
11 - 22 (166)
33
76
32

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
From (8), know that
-n(gge0 rh1 = ==--- -n (ng(er, ;²) + 7 (0- v))
(167)
which gives
Vf -2- >2( - =²) + 17711 (x) 27),
(168)
or equivalently
y" - 2- = (y 1)(2++1_ 2* (x'',"))++*0000"))0))) 25 + mmg((""
(169)
Applying the triangle inequality gives
11 - ==11
$ 1y 111| 2* (z", + 2* 2x",,, .²") 20 + mllhg(a"", 22'll
(170)
S 1y 1lle + 111|2" 2" (x", s'll m mm1hh 20) h 11 )
(171)
h 1lle + 112p(C vuT VC2
+ tm 2 + h 111
(172)
where in (a) we apply (159) that serves as an upper bound for the size of different iterates. Substituting (172) back to (166) yields
1-+1 - 8 (x", . "')lll>>" - 2"1l + 212111"* - 2" "11l" 11l""~~ - z"|l
1
Xr+1
+ 38 11 r1 "'lllla" 21 + 76 11y" =2111
(173)
8 1/ (a", , "lll"" =''l || + P
1
Ily" z" "Illy"" 2"|l + X"+1
76 11y" - =11
1
+ 38
--''l (1Ey +1="+ +
3||=,|1) 110 21
(174)
< (M"(","""") (h-11le+ 12 VHT
Ing ,"'00 + 17- 11115: (..0))
J.C_
+
(p+ A)
2pcC
PT VC,
+ mmllggaa 22)22 111
8 76
|| )
(2nCC VIT
+
VC. +m , + 11|n5
(175)
We choose
p (A), 0(1,, 8 O(),, ----=====--00-
or of the same small order,
(176)
then, it can be easily checked that the three terms in (175) can be upper bounded by
IUT v
Ap2
AVT / O(A).
x+1
So
+
+ +0
(177)
8
VB8
Thus, we have +++1 A = 0(1) when the step-sizes are sufficiently small. In turn, this implies the upper boundedness of +1 immediately.
33

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
C.2. Boundedness of Variables (v', ". (""""" ("""""""""""""""""""""""""""""""
x and x', 3' F Lemma 9. Under Al-A5, suppose that the sequence ,","","", "", D X", Vr, is generated by TSP. Assume that y' ("", "0)) are bounded and boundedness of the gradient estimate. 17
Then, we have
( + ). (x", .T ; ,,,,,,"+ are also bounded.
Proof. We prove these results by induction. First, we assume that y", """ (F" are bounded, which gives the (gradient) Lipschitz continuity of g(x,,) -) at these points.
Recall the bounded level set assumption that let
<xx, v)
(vlg(æ, y) -) 3) S 5.}.
(178)
Under the assumption that v² 17 (w",,") are bounded and a = B = T = O we can have either the monotonic decrease of the potential function up to a small error or convergence of the iterates. By the fact that (F*((11) +r+ y (#r+1, gr+))) S P( 1)+ for any (x'.y",at, : x²), there exists a constant such that t (T 1 ", (#rt), 1 , s ( S B(R(2) v ;,,,),,))),
(179)
which gives that x* (#*+1, ,7++1) and 1/* (#r+1, +1) bounded.
Applying the weak error bound result gives
Ilu ("", T7' XI () D" (7', 7 V /w/l\ X (T", "'I 77) X (T", T O(1)
where (a) holds due to the facts (234a), (140) and the boundedness of the dual variable. So, we can have that y² (2", 14 (#r, T*)) = (1) is bounded. Additionally, it can be checked that
l ( T x
A (7), D'II (26) + L p L
| - 1 (T (T,7)) @ 0(1)
where (a) holds due to the boundedness of the dual variable.
Note that K ,, Hr, T"; 1 is strongly convex with modulus p and gradient Lipschitz. continuous with parameter p + L. From (Hardt & Simchowitz, 2018), we have
< (1-P- P- p p
I - y* (F"
11 1100 y² ("" (Be)))
(180)
where ny denotes the random noise term. Given that the gradient estimates are bounded and (TT-1/)). conclude the boundedness of yr Similarly, the above boundedness properties also true for a1+1 x (x", "" x""), N (T" 1)) = 0(1).
C.3. Lower Boundedness of Q"
From (92), we know that
2 K('",'" ,2, ", T. X') - (' 8") 1 M(",
(181)
(P(F",0) D(F,0'')) - (A",
= P (P)"""")) + K(x", ,y", ""
2 P(F", 17) - - 1M( -h" 2
(182)
where (a) holds due to 1) K(x", y", ".
0 based on the definition of D ;;; X²) and 2) note and P( T D(" x -1
that P(T, 77) = mina,yy x20 (ar v)
2 ||
0, which is true because the minimax equality theorem (Kakutani, 1941; Bertsekas et al., 2003) holds when K (z, B, 2, ū; is strongly convex in x. y and linear (concave) in À when variables are within compact set. Also, as h = O, we have Q' & Q(x'.2/)= "2",""11_
21,,, 2t ..' : ) 2 0, and (b) holds due to the definition of P( and the lower boundedness of function
g(), where Q denotes the lower bound of Q".
34

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
D. Theoretical Convergence Results
D.I. Proof of Theorem
Proof. Stationarity. Recall
VaC(x' yf; ( VyL(e 11',,"",'''0 :
9(x", ((:tt1;2rt))
(183)
For the block-æ, we have
V Va 1 ; |
V f (x", .V" + x [V=9("", v²) - Vug(x', 20" (xxx,,²))))
WVS
EF 1x=+1 x²) || + V eg("" (a" (a", vag(=', 21)| + 1 |x" - -1
Ing
E x']l + | 4' || + ALgll= - 2x",,xx,""""" (x",v")) v''l + pall= +
where in (a) we apply the following optimality condition of the z-subproblem
Ex Ex++1 = Er - aa (V=](x", "V" ,0""""""""""))" + x ( V=g(<",,'' v"" V V=g(2", +p))) --(pp(()-))) -x))
and (b) results from the fact that || x- ET I'l S w/ w|| - Eattil| S awlle =/
For the block-y, we have
V x
V Vo .0") + x²1
(Vng("", (x"(""""))++- + - (="(x",,
(x" )²) - -3r) 7
(184)
3 E (t 1--1--1]] -y']ll + A |B=" - =*"x", w²) pl p|lBy* 1
(185)
(m0 1 ( +D) B
v²] + - || - (0", "² |||
|
+ P E
F]] + p311c
(186)
where in (a) we apply the following optimality condition of the y- y-subproblem
Vyf(o, (af(,,v')++* +)+ yg(2", ,'" Ryy"" y²+1
B x-11=- -1"
pB( 8r)
(187)
7
Therefore, the primal optimality gap can be quantified as follows:
[g
;1;x""";) 21
2
(
4p²
<
+
p
|
+ 1d'11=
B +D) || [ --
y²1 1/
wa
| [ - 2T]1?
4p²
E
1
87 112 + (Ig دي
A2 1|2" - 2"(x",
"x",,"")" ,2))1 4p (a² ||: + 39115]113
(188)
Note that we choose
1
7 0(1, O=)(A)= a a= -
- -=
(189)
and (176). It can be easily verified that these choices of parameters also satisfy (149), (150), and (151). If case 2 shown in (18) appears, then it is directly implied that ||Í(=", ""''",,"">>"" x + e. Otherwise, we need to analyze the noise term more carefully. From (17), we have the following inequalities.
35

---

TSP: A Two-Sided Smoothed Primal-Duse Method for Nonconvex Bilevel Optimization
The first one is
min
1 p
}
(|LB [
x²]l | [1 1 v'111=
|
3-1 + 11 07 0711²)
8a 8,3 &w
$ Q"
- + nqq
(190)
The second one is
(1 C)C²
(112" 2= s Q - -Q +ng.
(2113)
(191)
Then, let
1 p
min
(192a)
8cx
83"
8w
3p²
max
+
.3
+
w²
(192b)
Plugging (190), (191) into (188) along with (192a) and (192b), we can have
(Lg + +) A2 (Q" -Q" + n%²).
19(x", x';=""
+
(193)
P1 (1 -]
From the above analysis, it can be seen that the boundedness of the gradient estimate essential for ensuring the boundedness of iterates, especially for the dual variable. Equivalently, the gradient estimate error is bounded. Let denote any noise term, e.g., Ex- From the noise terms shown in (93), it is apparent that each noise term is either in linear form quadratic form, coupled with the corresponding step-sizes, meaning that it takes the form v'E, Φ) or v²||=]]?, where v represents the step-size and á denotes the coefficient vector, which either the iterates or the gradients of the loss functions. There are a total 10 linear terms and 6 quadratic terms. Let Emax denote the noise term with the largest magnitude among all noise terms the rth iteration, and let be the corresponding step-size and G the largest magnitude among all á (note that we have shown that the iterates generated by TSP bounded and that all loss functions are smooth).
Define
A min frlQ² Q> AT,t min (illleinss!
G
T, & min 12)
(194)
500
where a A b denotes min(a, a, b} for any a, b E, and the threshold Q = G2 For the quadratic term of the noise w.r.t. E", we can have
E
< E
||-1|
S SOT
(195)
rst
due to A4 and A5, after removing the constant factors.
So, this term is the sum of a martingale difference sequence. Since is a stopping time, we can apply the optimal stopping theorem and obtain
For the cross term, not that (
= s*)
E
f0r
et)
= -0.
(196)
rst
which gives
EE
Σ rc1
(0",
E²")
(196)
E
(6" en>]
(a)
GEI|=*1
<
< G
E
|E < GGVT+1 oGv2T
rST
36

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
where (a) holds due the definition of I.
Applying the telescoping sum over I,..., T yields
E
19 . ;11
rct
24 L + + 12
P2
E Σ (Q" - + m(2)
P1
[1-4]c
r<t
24 (Lg + 1 12
(195)
02 +
(Q' -2 Q- 20000TT++0000000
P1
(1 (1-4) (1-4)
which gives
EQ' - Q+ + Σ
19(2" 8f )1 s &Q' - Q + 100GV2T + 100
(197)
r<t
where
24 (I2 + 1-- A2
1
P2
+
=0(0) ((T
(198)
p
P1
(1-1))0z
The first bound P(22 < T) is
G
G
(b) 2500 2 (c)
P(22 < T) =P P
U r<T
|
max
PP
I |maxx
(199)
500
50
r<T
where in (a). we apply the union bound, in (b) we use Chebyshev's inequality, and (c) holds because we can choose
1 1/2- such that 0 < < < 1.
The second bound P(4 < T,12 T) can be obtained as follows. In this case, we have Q++ Q > Q and ||e"|| s G/(500).
-
Note that we always have Q" Q S Q, which implies that we have bounded gradient. From (193), we have
(e)
DG2
Q
Q - Q" 10 (DG'l= = |l + 00 I1 mmax 13)
10
(200)
50
2500
2
where (a) is true because we choose i = O for sufficiently large T, and (b) holds due to G2 & 2Q. Consequently, under the event (41 < T2 = T3. we have
Q' Q = Q' - Q+++++ + - -Q-+1-Q+>>>> Q
(201)
2
which gives
P(4 < <T,2= =) <T,12=7) SP SP
Q
(a) EQ¹ -Q 2(Q)
Q v2 /2/40) (197)
(202)
2
Q/2
Q
where in (a) we use Markov's incquality, (b) choose & < 1/(1GVVT) in (197), and (c) holds because choose
Q = 8(Q" Q v2 oz /40)/s. Therefore, we have
IP(L < T) S (12 < <) + P(4 <T,62 = 7) s 5
(203)
which gives that PP(L = 7) 2 1 5/2. Then, from (197) we have
(Q'' - -+ 1il-QQV2+0//00
> E
[x v²; )12
r<t
2 Pl = T)E
Σ |9 1'=
T
1 E
Σ
19 v" x )|2 T
2
(204)
37

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
Therefore, we can obtain
1 T
19(2", " 7| < 2/ -2 + v +2+00% -
-2+
(0) spQ (6)
5e2
E
Σ KKT
(205)
T
4T
4
where (a) holds due to the definition of Q and (b) is true since T 2 (/()))) Let & - E 19(("", yy; x E} denote the event that the generated iterate does not converge to an e-stationary point. Then, according to Markov's inequality, we have P(E) I 5/2, which gives P(t < TUE) s.
||2
Constraint Violation.
From (130), we can get
I|lg(2", ,y"" - - ) 8 +1?
1 -5'1 - 5- V2 (v;= (
s 2 o(05 5n) g(x" , 22) 24
+ +2 (v';''); x²), 3d (v"; ;²); 111+++111
(206)
(244))
S 6l1 + 2,) r- x 221 + B2
l - n² 112 + 1 -x1113
2
+ 72
- - ("",0"))1
(207)
S 6((l 566, 422 -
|| x" 211 1 r- 1/ + 400 -
2
+ 72 1 - 17)
(208)
Note that
|| 2/112 = -,, 2112
< 21 - -X (1"))
(209)
s
(210)
Then, we can get
Illa("",") - 27 ,") 11+
à 1 - x x11 + o%
o3
2 1 - + (Ble, - 2,)3
< 36le + 222
Bz
73
+ +1272 (4, + )² |1 - V (,"x)
(211)
From (190) and (191), we have
03
x²1
32 11
r
2 - - (F = o (maxfa, (Q" - Q + nz)) (212)
Similarly, we can get - (o;;'",, (v"; Xa), of; x)) -r((== -000-QQ10 -r++1 + +b)) according to (145).
X²)
Applying the telescoping and the same argument as (205), we can get
1
(04) S O
{
E
T
19(x" - g, - -
=
VT
(213)
r
Slackness. If X" = 0, then it is trivial that [g(x", ,y) - (x""xx")) - 8|2" is zero. So, we only need to consider the case
where X" > as follows.
38

---

TSP: A Two-Sided Smoothed Primal-Dua Method for Nonconvex Bilevel Optimization
Note that
19(x", v") - -'"""'"'""""")") 8/2
I "3 "F"
92 (x (0", (0",0" ;; " (0",0";X - 5|
+ +3 9
[ y 1)2
(214)
(0)
S 6 + e (1ly* - (0
| - x* ( T7 ))
1 11- - x T' ||01
+ 3 max
(215)
6169 + (g)
1l 8²1l
xz x2
(p 2)²
a2(p L
+ max
||^ x3 (8", 77 |1811
(216)
6 + (2)
1 - 110/ - -3n113)
(p-
max
a2 32
1
+ 3 max
||- | - XL", 77112,11011
(217)
where in (a) there are two cases: 1) g(x* ( T. x- ) yy (7' ("" ; (1,,"""",,,," ( > 0
and we apply (234a) or ((*"("", (F", ("=)) , (2), D x (x" """00" ","""""",,"""""""0""",,""""""" < 0, which gives the upper bound of !|
Applying (212) and the same argument as (205), we can get
1 max (nax B) !) A(Q' - Q 100G 100
Σ 11a("", 5r -
where (a) we choose the same parameters as before. Therefore, we can obtain
11a("", v²) -111 = 0(2)= = = - (1)
(218)
r
E. Additional Proofs
E.1. Proof of Contraction of LL Sequence
Lemma 10. Under Al-A5, suppose that the sequence {x" . 2", ,², ,,, is generated by TSP and 7 e (2p)). The difference between the iterates and their corresponding optimal solution satisfies the following stochastic contraction property:
|| 2- (x", yy" y²1 S 0||"" 2x", v2' (n, 5y,))
(219)
222 + n/41 | x²12
|| 2" (x"+1, +| s "0|=² 2" 2=",,,'"1 11?
2
+ 22 + np
2 1 r21 + n (n E
(220)
39

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
where the contraction constants and the random errors are
_ 1 7
- ---) ()-))
0) <1,
(221a)
2
7
(1- !7 ( -p))
0)) 1,
8 2 (1+ n1z)
(221b)
2
m=(n) _ nlEg, 2²" - -2 (x", v0) + 2n |1 11?
Eg )g.) _ 11(1 + n1: 2 - 2" (x', .y" + (2 - -2 VV 2 (F", (7))
(221c)
+ (2 - 1z (x", ./)) n, // (3', ()) + 20 + n2 , 112
(221d)
Proof.
1 2="x".00 )22
= |1 =² + - 2² (x" 11
= -| =111|2 + 21/ (zr+1 - =²² - x² (x", ,))) + || - =x",,, ,²))
(222)
(2) (11 17 (1 1 7
1
o) ||2- - 20" .112 + 10 2- 2* (x", ,r)) + 2n 11c, 11?
(223)
where (a) is true due to the strong convexity of the loss function when E (22p)
| - (1===t,,=++111
< || - =x" v²) + 2² (x" ,/)) - (x ( )²
(224)
< || [="","")
+ 2(2 - == (x"","",== - 2xxtt1 ,0x"t1,,"t))
|| ="("",,"]
- 2T ar+1-="")
+
- -2(==t2=2"00" (z"""",),,,,,"""""""") - -"" (x*+1 y r1))
(225)
Then, by the mean value theorem, we have that (5r+1, 1 (axr+1 + (1 a)x", aay' + (1 -a)y") where 0 <<<i 1 such that
(x - 2021-2(x²'' 2² v²), (x",8") - 2" 1x"+1,
, +1
(2r 2²"x", vv",," Vz (5", ( - i²))
(226)
(0)
11211= 11= r+ - =x",,, 3²
11+1)) - ""","")l + (1-+1-1220 ==" "",",, 2 "0" (F".7))
+ (2rt1 - =="x",
(7" 7 (7
(227)
(9)
nT11llrrt1 - =1("", of
x' + 11 - II) + (2 -2= 2x'
+ + ==""", ) V , (
(228)
y-(13) -==+41==''',,, ((o""''') //12 + The (1x5 2-12 + 1 + (2--1 2 2 , ,²) v7 02 (8", DEl
S /n - 20(,",
+ + - 2" (x" 5n v 2 (3 ()5E()
(229)
where (a) follows from the continuity of =^, and (b) holds due to the convex combination of the two points.
40

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
Combining both terms yields
|| - =x (x , 1 )/
$ (1+ nT, )12 2" (x'. g² 222 + n/2²
2 1| - x²1 2L + 712
11 11 y012
2
+ ( (x", ,2' )/) - ( + (2 - 20" ./)) n y² (#", :g))g)
/
(230)
(223)
S (1 + nn2z)) 1 1 (; - )) || 1e"- ,0) + 20 + 1
2 ||x- x²11 + 222 + 1/11
110 - yr1
2 7
2
+ t1 + n1(1s) (5
g., x² (2", 1/) + 21 + *1,)1l 11?
+ (2 2" 23 v²) 17 V 2 (7", -. + (2 (="x"= V y2 20 ())))))))
(231)
E.2. Proof of Dual Error Bound
Lemma 11. Under A -A5, suppose that X, 5/ (7. 37 are bounded and p > L., then the dual error bound holds, namely,
11y* (I, D: A+ (7, 7) 3" (a. 12 (2, (4, x² (2,
< ow A X (T. () (T,
(232)
where
1 1 7(8 + t2)02 2T(p- L)
and 02 - p L
Ow
(233)
p- L
Proof. First, let
(+) = Proizo ( + ( (u; 2; A)],
(234a)
X(v) E arg max K (v), (0), (v),
(234b)
X20
Based on the strong convexity of , and K,,,,,5 D: A), we have
KETTO//TOSSSALOOOKKKKEEEAAAAAAA0 -100))))))0000000000000000000)01 -10
PーL 1 KettoAAA000T000kkk000---AAAAAAA0 (x)),
(235a)
p- 11v
(1))
(235b)
p I
(10 K(< (v), (v))
'11
(x))
(235c)
2
K( -o) (F))))))))))))))))))))))) -- L
|
-
(235d)
Note that A4 (v) is the maximizer of the following proble..
max ((srK(((((()N(())))))oo4))))))) o/ta
(236)
A20
where
= ( 44M00000000000000000000000000000
-(A+TV (1) v),
(237)

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
According to the Lipschitz continuity of V, we have
|0(; A, (+))
$ S4N00--AAAHHairrrr00000000000010
(238)
(4)
(1+ + 4222 -
(239)
where in (a) we use the primal error bounds (26), (25b), and apply the Lipschitz continuity of g(,) ) and 97
Based on the definition of X (v) (cf. (234a)), we have
<K(="(;; XKC <<< SHKCC(AAAAMMMMAAAAA00A00000A0000
(240)
Subsequently, we can obtain
(r 10 $ (A(b) ((0)))A,,
(241)
x [A(0)) - (1)) (00))
(242)
According to the definition of X(v) (ef. (234b)), we have
K(ī" (u), (v), e; A()) 2 (0
(243)
Combing (235a) to (235d), and (243) yields
2r(p L) 11) < [[A(v)) - +22 + I 11
(244)
Therefore, we have
I1v' 1 (f', - D' [F',"""" " A (T"
S <owlli S X+ (8 "" (+',
(245)
where ow 1 1 + (2)02/22((p L)).
42

---

TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization
F. More Discussion on KKT Solutions and Additional Numerical Results
E.. Interpretation of the Solution
UL loss function
loss function
(a) Distribution alignment
UL loss function
LL loss function
(b) Distribution shift
Figure Illustration of the Importance of Finding the KKT Solutions.
We consider a one-dimensional simple bilevel problem, formulated as min, fu (æ) subject to I E arg ming (x)),,, as illustrated in Figure 5, to emphasize the importance of achieving KKT solutions, particularly concerning the slackness condition. Due to the nonconvexity of the LL problem, there may exist multiple stationary points. Assuming that a lies within the optimal set of the LL solution, then further needs find the stationary (or optimal) point of the UL loss function. When there is overlap between the two loss functions, depicted in Figure 5()), the optimal point of the UL loss function coincides with the best solution. However, if there is shift between the UL and LL optimal sets, the slackness condition ensures that the solution must be attained the boundary. In contrast, penalty-based methods only guarantee convergence to some stationary points, without ensuring this level of optimality. As illustrated in Figure 5(a), the obtained solution corresponds to the minimum point of the UL given that æ belongs to the LL. optimal set at least this case. This underscores the importance of finding KKT points rather than stationary points in terms generalization performance.
F.2. Additional Numerical Results
The algorithms are further tested representation learning for multi-task sinusoid regression problem (Rajeswaran et al., 2019), where the UL. loss is K- Σ f(x. yk. Deat) and the lower-level loss is f(x, Vk. Drr), vk. Here, K = 10 denotes the number of tasks, 2() is the mean square loss, Dval denotes the validation data samples (with amplitudes varying within [0.1, 5.0], phase varying within [0, v], and frequencies varying within [0.1, 3)), and Drr denotes the training data samples. In the numerical experiments, the selected learning rates for all algorithms are 0.01 for æ, 0.05 for y, and 0.06 for z. The dual variable learning rate for TSP 0.5, selected from 0.5, 0.1, 0.013. The neural network includes 2 hidden layers of
BOME
PBGD
10a
MEHA
train error
TSP
test error
BOME PBGD
МЕНА
TSP
1012
10"
100
130
200
300
350
400
500
number of iterations
number of iterations
(a) Train Erors
(b) Test Errors
Figure 4. Training and Test Errors vs. Number of Iterations.
43

---

TSP: A Two-Sided Smoothed Primal-Dus Method for Nonconvex Bilevel Optimization
10
BOME PBGD MEHA TSP
10P
train error
test error
10"
BOME
PBGD
MEHA
TSP
10
50
100
150
200
250
runtime (s)
runtime (S)
(a) Train Errors
(b) Test Errors
Figure 5. Training and Test Errors vs. Computational Time.
size 40 with ReLU nonlinearities (the weights represented by x) and K perception layers heads for each task (each represented by Via). There total of 10 training tasks, each with 10 data samples, and 5 test tasks. The training and test errors are averaged over these tasks. The experiments are conducted over 10 independent trials.
In Figure 5(a), it can be seen that the proposed TSP and MEHA, being single-loop algorithms, exhibit a faster convergence rate terms of runtime compared to the double-loop algorithms BOME and PBGD. Figure 5(b) TSP demonstrates a lower test error compared to the other algorithms. Specifically, TSP designed to find KKT points rather than stationary points. The figure shows that the solutions achieved by TSP provide lower test errors than those obtained by the other algorithms.
44


Reviews:
[{"review_id": "HxR3BhvoYS", "reviewer": "Reviewer_Dp7u", "summary": "This paper introduces SPD (Smoothed Primal-Dual), a first-order gradient-based primal-dual method for solving bilevel optimization problems, potentially with a nonconvex lower-level problem. SPD is based on a Moreau envelope-based reformulation of the bilevel problem and employs a proximal primal-dual Lagrangian updating framework, eliminating the need for Hessian computations. Theoretical results on iteration complexity are provided, and numerical experiments are conducted to demonstrate the efficiency of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer Dp7u for your helpful comments and questions.\n\n**Claims And Evidence:**\n*This statement about equilibrium constraints and bilevel optimization*\n\n> Will remove that statement.\n\n*On lines 69-71*\n\n> Will remove the statement.\n\n*contributions section (lines 167-169)*\n\n> Will add  \"approximate''.\n\n*Additionally, the reformulation (3) is incorrect.*\n\n> The reformulation (3) should be:\n$$\n\\min_{x,y}   f(x,y):=\\mathbb{E}_{\\xi\\sim D\\_{UL}} F(x,y;\\xi)\n\\\\\\\\\n\\\\quad \\textrm{s.t.} g(x,y)- g^{\\\\star}\\_{\\gamma} (x,y)\\le 0, \\quad g^{\\\\star}\\_{\\gamma} (x,y):=\\min_z \\mathbb{E}\\_{\\xi\\sim D\\_{LL}}   G(x,z;\\xi)+\\frac{1}{2\\gamma}\\\\|z-y\\\\|^2.\n$$\n \n**Methods And Evaluation Criteria:**\n\nResponse:\n> - Once the two quadratic proximal terms, $\\frac{p}{2}\\\\|x - \\hat{x}\\\\|^2$ and $\\frac{p}{2}\\\\|y - \\hat{y}\\\\|^2$, are introduced with auxiliary variables $\\hat{x}$ and $\\hat{y}$, the function $K(x, y, \\hat{x}, \\hat{y}, \\lambda)$ becomes strongly convex. This strong convexity ensures the existence of a unique optimal solution for $x$, $y$, and $\\lambda$, given any fixed $\\hat{x}$ and $\\hat{y}$. These optimal solutions are denoted as $x^{\\star}(\\hat{x}, \\hat{y}; \\lambda)$ or $\\bar{x}^{\\star}(\\hat{x}, \\hat{y})$, and similarly for $y$ (see equations (14) and (15) for details).\n\n> - Based on this setup, we can quantify the convergence process of the iterates $(x^r, y^r, \\lambda^r)$ by measuring the distance between $x^r$ and $x^{\\star}(\\hat{x}^r, \\hat{y}^r; \\lambda^{r+1})$, and similarly between $y^r$ and $y^{\\star}(\\hat{x}^r, \\hat{y}^r; \\lambda^{r+1})$. These distances can be further upper bounded by the successive differences of the iterates, i.e., $\\\\|x^{r+1} - x^r\\\\|^2$ and $\\\\|y^{r+1} - y^r\\\\|^2$, using the standard primal error bound (Zhang & Luo, 2020).\n\n> - Therefore, the proximal terms are critical. In particular, the distances to the proximal mappings automatically shrink to zero, ensuring that the algorithm converges to the solution of the optimization problem. As such, the auxiliary variables $\\hat{x}$ and $\\hat{y}$ play a key role in the algorithm design and in quantifying its convergence to the KKT points of the original problem.\n\n**Experimental Designs Or Analyses:**\n*The representation learning task in this paper lacks a clear problem ... the details of how the bilevel structure is formulated and applied remain vague. *\n\n> The representation learning task can be **formulated as a bilevel optimization problem**, as shown below:\n$$\n\\min_{x,\\{y_i\\}} \\quad  f(x, \\{y_i\\}) := \\mathbb{E}\\_{\\xi \\sim \\mathcal{D}^{\\text{val}}} \\left[\\frac{1}{K} \\sum_{i=1}^K \\ell(x, y_i; \\xi)\\right] \n\\\\\\\\\n\\text{s.t.} \\quad   y_i \\in \\arg\\min_{y'_i} \\mathbb{E}\\_{\\xi_i \\sim D^{\\text{tr}}_i} \\ell(x, y'_i; \\xi_i), \\quad \\text{for } i \\in [K].\n$$\n\n> - $x$ represents the **shared model parameters**, typically corresponding to the **common feature encoder** or backbone network shared across all tasks.\n> - $y_i$ denotes the **task-specific head parameters**, i.e., the final classification layer for task $i$, which is optimized using the task-specific training data $\\mathcal{D}^{\\text{tr}}_i$.\n\n> - This formulation captures the core idea of our approach: learning a shared feature representation ($x$) that enables effective adaptation to multiple downstream tasks through task-specific parameters ($y\\_i$).  \n\n\n*The dataset split and the specific role of SPD in optimizing meta-learning objectives are not thoroughly explained.*\n\n> We use a custom split of the MNIST dataset, where we create eight sub-datasets, each corresponding to a single digit class. Each sub-dataset contains 2,500 training samples and 1,500 validation samples.\n> - We use five sub-datasets for pretraining the model.\n> - The remaining three sub-datasets are used for meta-learning, which includes both meta-training and meta-testing.\n\n> The key role of SPD in this framework is to adjust the dual variables individually for each task-specific head. This flexibility helps to balance the optimization dynamics between the shared and task-specific components, which in turn improves the generalization capability of the learned representation across unseen tasks.\n \n*Furthermore, the experimental discussion is limited.*\n\n> For bilevel optimization problems, our experimental discussion is centered on evaluating the performance of the algorithms at both the upper and lower levels. We also include addtional results w.r.t training accuracy, convergence behavior, and runtime efficiency in the appendix, showing that the proposed SPD algorithm consistently achieves superior performance across these metrics.\n\n**Weakness 1** \n> - In the dual update, $h$ is an iterative variable that serves as a stochastic estimate of the gradient of the function $K(x, y, \\hat{x}, \\hat{y}; \\lambda)$  . \n> - While the symbol $h$ also appears in the primal update, each instance is clearly distinguished by different superscripts (e.g., $f$ or $g$) and subscripts.\n\n**Weakness 2** \n> Will remove unnecessary numbers.", "claims_and_evidence": "This paper contains several inappropriate and incorrect claims:\n\nAt the beginning of the introduction, the authors state, \"The mathematical programs with equilibrium constraints (Luo et al., 1996), also known as the bilevel optimization problem.\" This statement is incorrect, as mathematical programs with equilibrium constraints and bilevel optimization problems are distinct classes of problems.\n\nOn lines 69-71, the authors claim, \"This property is advantageous from an optimization perspective, as the Slater condition holds automatically.\" This is incorrect because the Slater condition applies only to convex optimization problems, whereas (2) is clearly a nonconvex optimization problem.\n\nIn the contributions section (lines 167-169), the authors state that \"this is the first time a stochastic first-order method has successfully achieved the KKT points of the bilevel optimization problem.\" However, in this work, they only demonstrate that their proposed method achieves an approximate KKT point, making this claim misleading.\n\nAdditionally, the reformulation (3) is incorrect.", "methods_and_evaluation_criteria": "The derivation of the proposed SPD algorithm in Section 2 lacks clarity. The authors claim that it is based on stochastic gradient-based updates to find the equilibrium points of $$\\min_{x,y,\\hat{x},\\hat{y}}\\max_{\\lambda\\geq 0}K(x,y,\\hat{x},\\hat{y},\\lambda).$$ However, by the definition of  $K(x,y,\\hat{x},\\hat{y},\\lambda),$ the equilibrium points of this formulation must satisfy $\\hat{x}=x, \\hat{y}=y$. This raises concerns about the necessity of introducing the additional variables $\\hat{x},\\hat{y}$, as their inclusion may not contribute meaningfully to the optimization process. A clearer explanation should be provided to justify their role and the necessity of their updates.", "theoretical_claims": "I have checked parts of the proof, and they appear to be sound.", "experimental_designs_or_analyses": "The representation learning task in this paper lacks a clear problem setting and sufficient discussion. While the authors mention the use of a multi-head neural network structure, where the upper-level problem optimizes a shared model parameter layer and the lower-level problem consists of multiple task-specific heads, the details of how the bilevel structure is formulated and applied remain vague. The dataset split and the specific role of SPD in optimizing meta-learning objectives are not thoroughly explained. Furthermore, the experimental discussion is limited, with only a comparison of test accuracy and generalization performance across different methods.", "relation_to_broader_scientific_literature": "The proposed SPD is designed based on a Moreau envelope-based reformulation of the bilevel optimization problem (Gao et al., 2023; Yao\net al., 2024b; Liu et al., 2024a) and a moving average technique (Chen et al., 2023b).", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strength:\n\nthe experimental results demonstrate the practical advantages of the proposed method, showing improvements in test accuracy and generalization performance over other methods\n\nWeaknesses:\n1. The notation is quite confusing. For example, the variable **h** in the dual update is not properly explained, and the same symbol is used in the primal update to represent a different concept, which can cause confusion and make it difficult to follow the derivations.\n2. There are an excessive number of equations, with a total of 244 equation labels. This creates a cluttered presentation and detracts from the clarity of the paper. It would be helpful to streamline the number of equations and provide better organization or referencing to make the paper more readable.", "other_comments_or_suggestions": "In line 193, on the right hand side,  \"$\\lambda^r+,\\text{Proj}\\geq 0$\" should be $\\lambda^r_{+},\\text{Proj}_{\\geq 0}$; in line 291,  “beta” should be \"$\\beta$\"; in line 685, \"w.r.t. $x,y$” should be \"w.r.t. $y$\".", "questions_for_authors": "no", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TyVdFn2HAh", "reviewer": "Reviewer_85Pr", "summary": "This paper presents a smoothed primal-dual algorithm for solving stochastic bilevel optimization problems where the lower level problem is possibly nonconvex.\nThe authors first use Moreau envelope reformulation for the lower level problem and then use the smoothed primal-dual method to solve the resulting constrained optimization problem.\nThey establish the optimal convergence rate of the algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 85Pr for your positive feedback, thoughtful comments, and constructive questions.\n\nQuestions:\n*Is $p$ changing for different? Could the authors specify the value of $p$ we should take in the algorithm and main theorem?*\n\n> In theory, $p$ is a constant and should be chosen to be on the same order as the dual variable, which is upper bounded by a constant. In practice, we can initialize it as a small value and increase it if the algorithm does not sufficiently decrease the loss, following a similar philosophy to tuning the learning rate.\n\n\n*How does the algorithm in this paper compare to ``SLM: A smoothed Lagrangian method for structured nonconvex constrained optimization''? Could the authors provide details?*\n\n> In comparison to the referenced work, the main differences are as follows:\n\n> - (**Different class of lower-level problems**) The algorithms are designed for different bilevel optimization formulations. Our work focuses on a Moreau envelope-based reformulation, where the lower-level problem is weakly convex. In contrast, the referenced work assumes that the lower-level objective satisfies the PL condition.  \n\n\n> - (**Stochastic vs. deterministic setting**) Our algorithm is designed for the stochastic setting, whereas the referenced method addresses only the deterministic case. This distinction introduces significant challenges, particularly in designing the update rule for the dual variable under stochastic noise.\n\n> - (**Single-loop vs. double-loop structure**) Our algorithm adopts a single-loop structure, which is more suitable for stochastic optimization. The referenced method, on the other hand, uses a double-loop approach.\n\n> - (**New high-probability error bounds**): Our theoretical analysis explicitly quantifies stochastic errors arising from the updates of the upper-level variable, lower-level variable, and auxiliary variables. This includes handling the non-negativity constraint on the dual variable. As a result, the analysis framework is significantly different from that of the referenced work.\n\n*The Moreau envelope reformulation is proposed in previous papers. Could the authors provide more details about the novelty compared to these papers?*\n\n> The main novelties of this work, compared to previous papers that also study the Moreau envelope reformulation, are as follows:\n\n> -(**Primal-Dual Update Strategy**): To the best of our knowledge, this is the first work that applies a primal-dual algorithm to solve the Moreau envelope-based bilevel optimization problem. It is well-established in the optimization community that primal-dual methods often achieve better convergence properties than penalty-based methods. This is largely due to the dynamic update of the dual variable, whereas penalty methods require either a sufficiently large penalty parameter or a monotonically increasing schedule, which can force the learning rate to be very small. This would be particularly problematic when handling multiple lower-level problems.\n\n> -(**Stochastic Problem Formulation and Algorithm Design**) The proposed SPD method tackles a stochastic version of the Moreau envelope reformulation, which significantly broadens its applicability to real-world machine learning problems. In contrast, prior works have largely focused on deterministic settings. The stochastic nature of our formulation introduces substantial challenges in both algorithm design and theoretical analysis, particularly in achieving convergence guarantees. This further differentiates our approach from existing literature.", "claims_and_evidence": "Yes, no major issue.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proof sketch and did not find major issues.", "experimental_designs_or_analyses": "I briefly checked them and did not find any major issues.", "relation_to_broader_scientific_literature": "Nonconvex bilevel optimization is important in machine learning, AI, engineering and economics.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength:\n1.The algorithm can solve bilevel optimization with nonconvex lower level problem and achieve the optimal rate for stochastic problem with mild assumptions.\n2. For the convergence analysis of primal-dual algorithm, they prove the boundedness of the dual variable instead of making bounded dual assumption.\nWeakness:\nSee the questions below.", "other_comments_or_suggestions": "See questions below.", "questions_for_authors": "Questions:\n1. Is $p$ changing for different $r$? Could the authors specify the value of $p$ we should take in the algorithm and main theorem?\n2. How does the algorithm in this paper compare to ``SLM: A smoothed Lagrangian method for structured nonconvex constrained optimization''? Could the authors provide details?\n3. The Moreau envelope reformulation is proposed in previous papers.  Could the authors provide more details about the novelty compared to these papers?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sgQw350Nta", "reviewer": "Reviewer_bXuu", "summary": "This paper proposed a single-loop method for solving the stochastic bilevel optimization problem with weakly convex lower-level problem. The proposed method is proved to achieve a convergence rate of $O(\\epsilon^{-4})$ in terms of a smoothed reformulation. Some experimental results on data hyper-cleaning task and representation learning task are presented to show that the proposed method outperfumes some existing methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer bXuu for your helpful comments and questions.\n\n**Claims And Evidence:**\n*My main concern is the gap between the penalty reformulation and the original bilevel problem. It seems that both of the proposed method and the convergence analysis are based on the reformulation. *\n\n> Correct. The proposed method addresses a Moreau envelope-based reformulation of the original bilevel optimization problem. The relationship and equivalence between the original and reformulated problems are discussed between lines 194 and 199 of the paper, summarizing the findings of existing works [Gao et al., 2023] and [Liu et al., 2024a].\n>\n> The equivalence presented in [Theorem A.2, Liu et al., 2024a] for the simplified case where the lower-level problem is unconstrained is further clarified below.\n\n\n>\n> **Original Problem:**\n> $$\n> \\min_{x, y} f(x, y), \\quad \\text{s.t.} \\quad y \\in \\mathcal{S}(x)\n> $$\n> where $\\mathcal{S}(x) := \\arg\\min_y g(x, y)$.\n>\n> **Moreau Envelope-based Reformulation:**\n> $$\n> \\min_{x, y} f(x, y), \\quad \\text{s.t.} \\quad g(x, y) - g^\\star_\\gamma(x) \\le 0\n> $$\n>\n> - When the lower-level function $g(x, y)$ is convex or satisfies the Polyak-Łojasiewicz (PL) condition, these two formulations are equivalent.\n> - When $g(x, y)$ is weakly convex and $\\gamma \\in (1, 1/\\rho)$, the Moreau envelope-based reformulation becomes equivalent to a relaxed version of the original problem:\n> $$\n> \\min_{x, y} f(x, y), \\quad \\text{s.t.} \\quad y \\in \\mathcal{S}'(x)\n> $$\n> where $\\mathcal{S}'(x) := \\\\{ y \\mid \\\\|\\nabla_y g(x, y)\\\\| = 0 \\\\}$\n\n> Given the weak convexity of $g$, it is reasonable to aim for a stationary point, as opposed to requiring a global optimum for the lower-level problem.\n\n\n**Methods And Evaluation Criteria:**\nThe main idea of the method design is to reformulate the original bilevel optimization problem into a min-max optimization problem with more feasible conditions using moreau envelope and penalty technique. This makes sense as the reformulated problem is a convex-linear min-max problem is well-studied and easier to solve.\n\n> Yes, this approach is conceptually related to the primal-dual or Lagrangian methods. However, the reformulated problem is **not** a convex-linear min-max problem due to the weak convexity of both the upper- and lower-level objective functions. Therefore, standard techniques for solving convex-linear min-max problems are not directly applicable in this case.\n> The main reasons are as follows:\n> 1. The upper-level objective function $f(x, y)$ are nonconvex rather than convex.\n> 2. The lower-level function $g(x, y)$, even after applying the Moreau envelope, does not necessarily yield a convex constraint.\n \n\n**Experimental Designs Or Analyses:**\n*Regarding the data hyper-cleaning task, as described in section 4, the lower-level objective is the cross-entropy loss function, which is convex. This problem can be solved by methods designed for bilevel problems with convex lower-level problems. This application seems not suitable. *\n\n>  As noted on line 382, the lower-level objective includes a nonconvex regularization term. While the cross-entropy loss $\\ell_{\\text{tr}}$ is convex, the presence of the nonconvex regularizer makes the overall lower-level function **weakly convex**. Therefore, this data hyper-cleaning task remains a suitable example for evaluating methods designed for bilevel problems with weakly convex lower-level objectives.\n\n\n*All the baselines compared in the experiments are in deterministic setting, which makes the experimental results not very convincing. Moreover, it is well known that stochastic methods generalize better than deterministic methods in general. Thus, the claim 'This example further highlights ... optimization' in the representation learning task part may not necessarily hold.*\n\n> Please kindly note that the numerical experiments on the representation learning task are conducted in a **stochastic setting**. As mentioned on line 418, a batch size of 32 is used. This setting is applied to all compared algorithms, indicating that they are all implemented stochastically. We will clarify this more explicitly in the revised version to ensure it is clear that **all methods are evaluated in a stochastic manner** for a fair comparison.\n\n\n**Other Comments Or Suggestions:**\n\n*In Assumption 3.1, the weak-convexity assumption A2 is unnecessary as it is implied by the smoothness assumption A1.*\n\n> Thank you for your comment. We will remove Assumption A2 in the revised version.\n\n\n*Using $G(x,y;\\xi_i)$ for single sample stochastic estimator, and $\\hat{g}(x,y)$ for mini batch stochastic estimator is rather confusing. It would help the readers to understand more easily if such notations are more consistent.*\n\n> Thank you for the helpful suggestion. We will use $\\nabla \\hat{G}(x, y)$ to denote the mini-batch stochastic gradient estimator, so that the notation is more consistent throughout the paper.", "claims_and_evidence": "This paper claims that the proposed method better solves the stochastic bilevel optimization problem in terms of both convergence rate and experimental performance. For the theoretical analysis part, my main concern is the gap between the penalty reformulation and the original bilevel problem. It seems that both of the proposed method and the convergence analysis are based on the reformulation. It is unclear that how the convergence guarantee relates to the original problems.", "methods_and_evaluation_criteria": "The main idea of the method design is to reformulate the original bilevel optimization problem into a min-max optimization problem with more feasible conditions using moreau envelope and penalty technique. This makes sense as the reformulated problem is a convex-linear min-max problem is well-studied and easier to solve.", "theoretical_claims": "Please see the Claims And Evidence section.", "experimental_designs_or_analyses": "Regarding the baselines in the experiments, I have the following concerns/questions.\n\n1. Regarding the data hyper-cleaning task, as described in section 4, the lower-level objective is the cross-entropy loss function, which is convex. This problem can be solved by methods designed for bilevel problems with convex lower-level problems. This application seems not suitable. The authors need to either compare SPD with the convex LL methods or choose a 'merely' weakly convex LL problem as the application.\n2. All the baselines compared in the experiments are in deterministic setting, which makes the experimental results not very convincing. Moreover, it is well known that stochastic methods generalize better than deterministic methods in general. Thus, the claim 'This example further highlights the advantage of solving bilevel learning problem through the lens of equilibrium constrained optimization' in the representation learning task part may not necessarily hold.", "relation_to_broader_scientific_literature": "The main contribution of this work is that it is trying to weaken the convexity assumption on the lower-level objective of bilevel optimization, which is essential as it covers a larger family of problems.", "essential_references_not_discussed": "All essential references that I'm aware of are discussed.", "other_strengths_and_weaknesses": "I do not see other strengths and weaknesses.", "other_comments_or_suggestions": "1. In Assumption 3.1, the weak-convexity assumption A2 is unnecessary as it is implied by the smoothness assumption A1.\n2. Using $G(x,y;\\xi_i)$ for single sample stochastic estimator, and $\\hat{g}(x,y)$ for mini batch stochastic estimator is rather confusing. It would help the readers to understand more easily if such notations are more consistent.", "questions_for_authors": "I do not have any other questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZJkDCisnME", "reviewer": "Reviewer_fDFn", "summary": "This paper investigates a bilevel optimization problem where both the upper and lower levels are nonconvex, making it a challenging problem. The author proposes a smoothed-type single-loop algorithm and provides a theoretical complexity guarantee for convergence to a KKT-type stationary point. Numerical experiments are conducted to demonstrate the performance of the proposed algorithm.\n\n## update after rebuttal: I appreciate the authors’ response. I agree that the existing hardness results, while closely related, do not contradict the findings presented in the paper. If the results are indeed correct, this would be a strong and impactful contribution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer fDFn for your helpful comments and questions.\n\n**Theoretical Claims:**\n*I find the key contribution of this paper to be its ability to handle nonconvexity in the lower-level problem, which, to my knowledge, has been a significant challenge in bilevel optimization. As claimed by the authors, the proposed algorithm reaches a stationary point satisfying the KKT conditions for both the upper and lower levels under only a weakly convex assumption. This result appears quite strong. Given that lower bound results exist for related problems (such as in minimax optimization, which is a special case considered in this paper), [1] shows that such problems are PPAD-hard (though with additional constraints). Could the authors provide insights into why their approach successfully achieves this result despite these known hardness barriers? Understanding this aspect would further clarify the theoretical significance of the proposed method.*\n\n> Thank you for your insightful comment. The main source of hardness in solving min-max problems (a special case of bilevel optimization) to the type of stationary points defined in [1] lies in the presence of constraints. In our setting, there are **no explicit constraints** at either the upper or lower level.\n\n> Additionally, we assume that the objective functions are **coercive**, which helps ensure that the iterates generated by our SPD algorithm remain within a bounded region without requiring additional projection. As a result, this assumption—together with the algorithm design—implicitly guarantees the boundedness of the loss values over the unconstrained domain.\n\n> These conditions align exactly with the discussion following Theorem 4.1 in [1], which argues that in such unconstrained settings with bounded loss value, approximate stationary points **do** exist and can be found in **polynomial time**. Therefore, our theoretical results do not contradict known hardness barriers; rather, they fall within a subclass of problems where efficient solutions remain tractable.\n\n \n\n\n*[1] Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. \"The complexity of constrained min-max optimization.\" Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.*\n\n\n**Experimental Designs Or Analyses:**\n*The experimental design makes sense to me. However, it would be helpful if the authors could explain how the chosen parameters in the experiments align with the theoretical claims. Providing this clarification would strengthen the connection between the theoretical guarantees and empirical results.*\n\n>Thank you for the helpful comment. The parameter choices (primarily the learning rates) were selected via grid search, following standard practice in the literature. For the stochastic case, we applied a learning rate decay of $ 1/\\sqrt{r}$, which is guided by our theoretical results. The initial learning rates were determined through grid search.\n\n> We also apologize for the typo in line 418 of the paper: the learning rate decay was incorrectly written as $1/r$; it should be $1/\\sqrt{r}$. We will correct this in the revised version.\n\n\n**Other Comments Or Suggestions:**\n\n*line 195: formulations (1) and (1)*\n\n> Typo: the second reference to equation (1) should be (3).\n> \n*line 215: forgotten period at the end.*\n\n> Thank you for your careful reading. We will add the missing period in the revised version.\n\n*line 255 & 256: should the UL and LL get exchanged?*\n\n> The terms \"UL'' and \"LL'' are indeed confusing in this context. We will remove them in the revised version.", "claims_and_evidence": "Yes, it is clear.", "methods_and_evaluation_criteria": "Yes, the algorithm is tested on standard machine learning tasks.", "theoretical_claims": "I find the key contribution of this paper to be its ability to handle nonconvexity in the lower-level problem, which, to my knowledge, has been a significant challenge in bilevel optimization. As claimed by the authors, the proposed algorithm reaches a stationary point satisfying the KKT conditions for both the upper and lower levels under only a weakly convex assumption. This result appears quite strong. Given that lower bound results exist for related problems (such as in minimax optimization, which is a special case considered in this paper), [1] shows that such problems are PPAD-hard (though with additional constraints). Could the authors provide insights into why their approach successfully achieves this result despite these known hardness barriers? Understanding this aspect would further clarify the theoretical significance of the proposed method.\n\n[1] Daskalakis, Constantinos, Stratis Skoulakis, and Manolis Zampetakis. \"The complexity of constrained min-max optimization.\" Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.", "experimental_designs_or_analyses": "The experimental design makes sense to me. However, it would be helpful if the authors could explain how the chosen parameters in the experiments align with the theoretical claims. Providing this clarification would strengthen the connection between the theoretical guarantees and empirical results.", "relation_to_broader_scientific_literature": "This work makes significant progress in bilevel optimization by removing the convexity assumption, which is a notable advancement in the literature.", "essential_references_not_discussed": "Not found.", "other_strengths_and_weaknesses": "If the results are correct, the problem studied in this paper could be highly significant.", "other_comments_or_suggestions": "- line 195: formulations (1) and (1)\n- line 215: forgotten period at the end.\n- line 255 & 256: should the UL and LL get exchanged?", "questions_for_authors": "Please review the theoretical sections. I will definitely increase my score if I can confirm the correctness of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a smoothed primal-dual algorithm (SPD) for stochastic bilevel optimization with potentially nonconvex lower-level problems. The method is based on a Moreau envelope reformulation and avoids Hessian computations. Theoretical guarantees and empirical results demonstrate its effectiveness over existing approaches.

All reviewers recommend acceptance after the rebuttal, and I agree. For the final version, the authors are encouraged to improve notation clarity, better explain the experimental setup, and ensure theoretical claims are well supported. Clarifying parameter choices, comparing more thoroughly with related methods like SLM, highlighting the novelty over prior Moreau envelope approaches, and discussing the gap between the reformulation and the original problem would further strengthen the paper.
Decision: Accept (poster)