Enhanced Bilevel Optimization via Bregman Distance
Authors: Feihu Huang
Junyi Li
Shangqian Gao
Heng Huang
Venue: NeurIPS 2022 Accept (2022)

Abstract: Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Although many bilevel optimization methods have been proposed, they still suffer from the high computational complexities and do not consider the more general bilevel problems with nonsmooth regularization. In the paper, thus, we propose a class of enhanced bilevel optimization methods with using Bregman distance to solve bilevel optimization problems, where the outer subproblem is nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex. Specifically, we propose a bilevel optimization method based on Bregman distance (BiO-BreD) to solve deterministic bilevel problems, which achieves a lower computational complexity than the best known results. Meanwhile, we also propose a stochastic bilevel optimization method (SBiO-BreD) to solve stochastic bilevel problems based on stochastic approximated gradients and Bregman distance. Moreover, we further propose an accelerated version of SBiO-BreD method (ASBiO-BreD) using the variance-reduced technique, which can achieve a lower computational complexity than the best known computational complexities with respect to condition number $\kappa$ and target accuracy $\epsilon$ for finding an $\epsilon$-stationary point. We conduct data hyper-cleaning task and hyper-representation learning task to demonstrate that our new algorithms outperform related bilevel optimization approaches.

Enhanced Bilevel Optimization via Bregman Distance
Feihu Huang Junyi Shangqian Gao', Heng Huang'
Electrical & Computer Engineering, University of Pittsburgh, Pittsburgh, PA, United States College of Computer Science & Technology, Nanjing University Aeronautics & Astronautics, Nanjing, China
huangfeihu20180gman com, junyili aunyili.ai@gaalii www.maii..m.........m..a.......a com, shg848pitt. heng. wwngg.uanggpitt.oo
Abstract
Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Al- though many bilevel optimization methods have been proposed, they still suffer from the high computational complexities and do not consider the more general bilevel problems with nonsmooth regularization. In the paper, thus, we propose a class of enhanced bilevel optimization methods with using Bregman distance solve bilevel optimization problems, where the outer subproblem is nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex. Specifically, we propose a bilevel optimization method based on Bregman distance (BiO-Brel) solve deterministic bilevel problems, which achieves a lower computational complexity than the best known results. Meanwhile, we also propose stochastic bilevel optimization method (SBiO-BreD) solve stochastic bilevel problems based on stochastic approximated gradients and Bregman distance. Moreover, we further propose an accelerated version of SBiO-BreD) method (ASBiO-BreD) using the variance-reduced technique, which can achieve a lower computational com- plexity than the best known computational complexities with respect to condition number and target accuracy for finding an e-stationary point. We conduct data hyper-cleaning task and lyper-representation learning task to demonstrate that our new algorithms outperform related bilevel optimization approaches.
1 Introduction
Bilevel optimization can effectively solve the problems with a hierarchical structure, thus it recently has been widely used in many machine learning tasks such as hyper-parameter optimization [37 20
9, 38), meta learning (9, 31 22), neural network architecture search [30], reinforcement learning
[5], and image processing 31 In the paper, we consider solving the following nonconvex-stronge
convex bilevel optimization problem:
f(x,v(())) h(x), =EX'CR41
min
(Outer)
(1)
s.t. (z) E arg min g(x,v),
(Inner)
yERd2
where function F(z) f(x,)"z)) X + R is smooth and possibly nonconvex, and function Mxx)) is convex and possibly nonsmooth, and function g(x,y) : X x RR + R is j-stroogly convex in y E RRd2 The constraint set X' Rdi is compact and convex. Problem TT] covers rich class of nonconvex objective functions with nonsmooth regularization, and is more general than the existing nonconvex bilevel optimization formulation in [1] 22 that does not consider any nonsmooth regularization. Here the function l((x) can be the nonsmooth regularization term such as 1((x) = A||=|||
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table I: Comparisons of the representative bilevel optimization algorithms for finding an e-stationary
point of the deterministic nonconvex nonconvex-strongly convex Problem (I) with h(z) or without h(z). i.e. [VF(=)]] I E or its equivalent variants. Golf. e) and Gc(g. é) denote the number of gradient evaluations w.r.t f(z,y) y) and g(z, y): (V E) denotes the number of lacobian-vector products; (g. c) is the number of Hessian-
products; K = J/ is the conditional number. v means that the algorithms solve both the smooth and nonsmooth bilevel optimizations.
Algorithm
Reference
Ge(J.
Gdlg.)) JV(g.c)
HV(g.c)
Nonsmooth
AID-BiO
11
O(ntee))
6(1"(
O
AID-BiO
22
O(n+e=t)
O(N+6-1)
O
((m
ITD-BiO
[22
O(
1(
OlRte
((x46-1)
BiO-BreD
Ours
O(NFc-t)
((19ctt)
Table 2: Comparisons of the representative bilevel optimization algorithms for finding an e-stationary
point of the stochastic
problem ( with h(x) or without h(r), i.e.
F)))2(2>)12 < 6 or its equivalent variants. Since some algorithms do not provide the explicit
dependence on KG we use p(K).
Algorithm Reference
Gc(F.c)
Gclg.c)
[Vig.c)
Nonsmooth
TTSA
[SS
O(p(x)c 2.))
O'p(nte 2.0)
O(p(i)c 2.0
O(p(k)c 24
STABLE
O(p(k)e
O(p(n)e
O(p(k)e
O(p(x)e
SMB
13
O(p(k)e ")
O(p(k)e
O(p(k)e +
O(p(n)e -)
VRBO
41
O(p(x)e-11. 1.9)
O(p(N)e 1.0)
O(p(N)e 1.))
O(p(n)e
SUSTAIN
23
Olp(k)e 1.))
O(p(xee 1.5)
O(p(Kje 155
O(p(n)e
VR-saBiAddm
Olp(k)e
O[p(x)e 1.0)
O(p(N)e 1.)
O(p(n)e
BSA
11
O(n"c-3)
O(n"c-8)
O(k" 2)
O(N" 3)
stocBiO
22
(
SBiO-BreD
Ours
ASBiO-BreD
Ours
O
O
Olk
OiK"E-10
Many recent machine learning research problems utilize the stochastic loss functions. Thus, also consider the following stochastic bilevel optimization problem:
min =EX'CR"1
BE-D [1 y" (x)): + M(x))
(Outer)
s.t. (z) E arg min BE-D (9(x, ()], VER
(Inner)
where function F(x) = Be [x( = Ee ( is smooth and possibly nonconvex, and function h(r) is convex and possibly nonsmooth, and function g(æ, y) [g[ ys [)] x'x R is u-strongly convex in y E Rd E and Ç are random variables following unknown distributions D and D', respectively. Both Problem (I) and Problem (2) have been used in many machine learning tasks with a hierarchical structure, such as hyper-parameter meta-learning 22 and neural network architecture search 30
Many bilevel optimization methods recently have been developed to solve these problems. For example, [ [22) introduced a class of effective methods to solve the above deterministic Problem (I) and stochastic Problem (2) with hzz)) 0. However, these methods suffer from high computational complexity issue. More recently, multiple accelerated methods were designed for stochastic Problem
2 14 41 proposed accelerated bilevel optimization algorithms via using the variance reduced techniques of HARAAAHSSIIE/SSNNA
(2) with h(x)= = O. Specifically,
[36] 8 40, (3) and STORM 6 However, these accelerated methods obtain a lower computational complexity without considering the condition number, which also accounts for an important part of the computational complexity (please see Tables and Meanwhile, these accelerated methods only focus on the special case of the stochastic bilevel optimization Problem (2) with h(x) O.
To fill in the gaps, in the paper, we propose a class of efficient bilevel optimization methods with lower computational complexity to solve the bilevel optimization Problems (I) and (2). where the outer subproblem is nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex. Specifically, we use the mirror decent iteration to update the variable z based on the Bregman distance. Our main contributions are summarized as follows:
(i) We propose class of enhanced bilevel optimization methods based on Bregman distance to solve the nonconvex- www.ree-sssoooooooooeee bilevel optimization problems. Moreover, we provide comprehensive convergence analysis framework for our proposed methods.
2

---

(ii) An efficient bilevel optimization method based on Bregman distances (BiO-Breh) is pro- posed solve the deterministic bilevel Problem (I. We prove that our BiO-BreD achieves a lower sample complexity than the best known results (please see Ta.
(iii We introduce an efficient bilevel optimization method based on adaptive Bregman distances (SBiO-BreD) to solve the stochastic bilevel Problem (2). Moreover, we design an accelerated version of SBiO-BreD Bree-BrrDD algorithm
AASBiO-BreD) via using the variance reduced technique, which achieves a lower sample complexity than the best known results (please see Table 2
Note that our methods can solve the constrained bilevel optimization with nonsmooth regularization but not rely any form of constraint set and nonsmooth regularization. In the other words, our methods can solve the unconstrained bilevel optimization without nonsmooth regularization studied in I 22]. Naturally, our convergence analysis can be applied to both the constrained bilevel optimization with nonsmooth regularization and the unconstrained bilevel optimization without nonsmooth regularization.
Related Works
In this section, we will revisit the existing bilevel optimization algorithms and Bregman distance based methods.
2.1 Bilevel Optimization Methods
Bilevel optimization recently has attracted increasing interest in many machine learning applications such model-agnostic meta-learning, neural network architecture search, and policy optimization. Thus, recently many algorithms 9 [5 35 22 28 have been proposed to solve the bilevel optimization problems. Specifically, ||| proposed a class of approximation methods for bilevel optimization and studied convergence properties of the proposed methods under convexity assumption. developed the gradient-basee descent aggregation methods for convex bilevel optimization. presented a nonlinear primal duall algorithm for nonsmooth convex bilevel optimization in parameter learning problems.
34
35
37
In parallel, 15 introduced a two-timescale stochastic algorithm framework for nonconvex stochastic bilevel optimization in reinforcement learning. Multiple accelerated bilevel approximation methods were developed later. Specifically, [22 proposed faster bilevel optimization methods based on the approximated implicit differentiation (AID) and iterative differentiation (ITD), respectively.
23 [4 41] presented several accelerated bilevel methods for the stochastic bilevel problems using variance-reduced techniques. More recently, [18] proposed a class of efficient adaptive methods for emnconve--strongly-e
bilevel optimization problems. At the same time, the lower bound of bilevel optimization methods has been studied in 21 for these nonconvex seroonve--stooglyy.ooo convex bilevel based and gradient- muddient-based bilevel methods for nonconvex bilevel optimization problems and studied asymptotic convergence properties of these methods. [8] analyzed a class of special nonconvex nonsmooth bilevel optimization methods for selecting the best hyperparameter value for the nonsmooth &p regularization with 0 < <
optimization problems. In addition, (34] [2] 33 designed a class of
2.2 Bregman Distance-Based Methods
Bregman distance-based method (a.ka, mirror descent method) 4 is powerful optimization tool because it uses the Bregman distance to fit the geometry optimization problems. Bregman distance was first proposed in 2] and later extended in (3]. 4 introduced the first proximal minimization al- gorithm with Bregman function. [ studied the mirror descent for convex optimization. (7] presented an effective variant of mirror descent, í.e. composite objective mirror descent, for regularized convex optimization. Subsequently, [42] studied the convergence properties of mirror descent algorithm for solving nonsmooth nonconvex problems.
[26] integrated the variance reduced technique to the mirror descent algorithm for stochastic convex optimization. The variance-reducee adaptive stochastic mirror descent algorithm [29] was proposed to solve the nonsmooth nonconvex finite-sum
optimization. More recently. [16] studied Bregman gradient methods for policy optimization.
3 Preliminaries
3.1 Notations
Let La denote d-dimensional identity matrix. 211,2, K} denotes uniform distribution over discrete set 21, ...
k.).1 .K).
denotes the b --rmm for vectors and spectral norm for matrices,
3

---

respectively. For two vectors and y, (2. denotes their inner product. Vzf(z, v) and V fzf(z,v) are the partial derivatives w.t. variables I and y. Given the mini-batch samples B = { Ji=1 we define V (I(;
Ei= vf(x; For two sequences {an, on M= On Obb,) denotes that an S Cb, for some constant C' > O. The notation Ō(-) hides logarithmic terms. Given a convex closed set X, we define a projection operation Px(xu) arg mingex || zoll?. ah(x)) is the subgradient set of function h(x).
3.2 Some Mild Assumptions
Assumption 1. Function F(x)= f(x (x)) is possibly nonconvex w.I.t. I, and function g(x, v) j-strongly convex w.r.t. y. For stochastic case, the same assumptions hold for f(z y (z); E) and g( y; respectively.
Assumption 2. Functions f(x, y) and g(x, y) satisfy
1) (V,((, v)ll S Cfu and II w)ll S Jory any x E X and E IR:;;
2) The partial derivatives (zf y). Vyf(z,y) v), Vzg(z, v) and Vug(z, v) are L-Lisschitz, e.g. for I, 22 E X and y. M1, y22 12d
[ v) - (12. Ml _ L| - æ2l1. of v1) Vaf(o, v2)1 S L1 - Vell-
For stochastic case, the same assumptions hold [ax 3) and g(a, Wi () for any & and Ç. Assumption 3. The partial derivatives V2 y) and V gg y) are Lgzy Lipschitz and Love Lipschitz, e.g., for all x. 322 E X and y. yn, 322 Rdda [[V (y2g((11))) Peyg(12, w)ll S Legy|l= - s2l1, ll V2zg(z,
V 2 (2)1 S Lavally) - y22l-
For stochastic case, the same assumptions hold Vayg(r, y: () and Vig(z, y for any S. Assumption 4. Function h(x) for any x E X is convex but possibly nonsmooth.
Assumption 5. Function (z) = F(x) + h(x) is bounded below, i.e., 4- = iinfrex (z) > -00.
Assumptions 1-3 are commonly used in bilevel optimization methods
23 According to
Assumption 1, (x, y1) - fa, 8/2 = v y- Vy) y2)ll < V ffr V+ I1lyn y2 S
Cfylly1 32ll. where V/ Tyı (1 r)g2 and 7 E [0, 1]. Thus (
Cfy is similar to the assumption that the function f is M-Lipschitz in [22] From the proofs in [22], we can find
that they still use the norm bounded partial derivative V y fx,, [2r, S M. Similarrl, according to Assumption 1, we have [V
- Vug((z,v) v) S L|| - 22/l. Since [V
- x2l I Cganylaa - -22ll where Ir = = + (1 T 2a2 and r' E [0, 1]. we can let Cgzy= = as in (22). From the proofs [22], we can find that they still use the norm bounded partial derivative V yay S L for all x, y- Throughout the paper, we let Cany L. Assumption 4 is generally used for regularization such as (xx) = ||-/|| 1. Assumption ensures the feasibility of Problems 1 and (2).
Vyg(22, y)ll = V2 (Zrr, (1 - x2)ll 1 S (2
When we use the first-order methods to solve the above bilevel optimization Problems and 22, we can easily obtain the partial (stochastic) derivative Vz9(1, 3) or V V2g(E, yr () update variable y. However, it is hard to get the (stochastic) gradient F=(x) ff(x,yy" or F [z; E) af(a, (x)))) dr
dr
when there is no closed form solution for the inner problem of Problems point of solving the Problems ( and (2) is to estimate the gradient V (F()). The following lemma
and (2). Thus, a key
provides one gradient estimator of V F()).
Lemma 1. (Lemma 2.1 in (Tl)) Under the above Assumptions 4
we have, for any x X
F((x) = Va (z)) (z)) (x,,,""" (z))
Vuf((, (x) (x)) y V (V))
(3)
Lemma 1 provides a natural estimator of Vz)), defined as, for all æ X Rd
Vf v) V.f( v2 Vnyl(,, w) V2n v)) - ' f, v). Next, we show some properties of VF (x) and V fzz y) in the following lemma:
(4)

---

Algorithm Deterministic BiO-BreD Algorithm
1: Input: T, K 2 1, learning rates 7 0, A 0;
2: initialize: 2a E X' and y = yo E R2:;
3: fort =0: -0,1,.. 1... T do
4: Let vt yr
5: for = 1,.., do
6:
Update y = y A V y)=
7:
end for
Compute partial derivative wi 2f(x..) via backpropagation w.r.t Tzi dip.
8:
9:
Given p-strongly convex mirror function vhy;
10: Update T++1 = arg minrex { (wr,, x) + lu()) + Dec x2)]:
11:
end for
Output: Uniformly and randomly choose from {at, ye 1
Lemma 2. (Lemma 2.2 in ITV) Under the Assumptions i 2 39. for all 21,11 E X and y E Rdd
have [V, V (x) < Lnylyy" yll
(x1) - 1/" (22)) S K||æa1 - x22l, [VF((1)) VF(x2)] S LF||x1 x211.
where by = L + 1a Crykure + CrupCrul, K = 4. and LF = + 2L 2L
Lapy I + Low
Bilevel Optimization via Bregman Distance Methods
In this section, we propose a class of enhanced bilevel optimization methods based on Bregman distance to solve the deterministic Problem
① and the stochastic Problem 2 respectively.
4.1 Deterministic BiO-BreD Algorithm
In this subsection, we propose an efficient deterministic bilevel optimization method via Bregman distances (BiO-BreD) to solve the deterministic Problem Algorithm Sum the algorithmic framework of our BiO-BreD method.
Given p-strongly convex and continuously woroouusl--diffeettibbeeee function (xxx, i.e (01- 22, Veb(z)) Vvb(xa)) ق|| 22 we define a Bregman distance 3 for any 21, X:
Do x2) = (z1) - vxx2) -
- 22).
In Algorithm I we use the mirror descent iteration to update the variable x at t + 1-th step:
{ (w,, + h(x)) + - De, (x,, ZE
Ft+1 arg min
(5)
where 7 0 is stepsize, and wA is an estimator of (F(z.). Here the mirror function t/ can be dynamic as the algorithm is running. Let (z) = 1 || we have Do, (x, = l| - 2, 1|2
When X = Rdd the above subproblem (5) is equivalent to the proximal gradient descent. When X Rd and h(x)) O. the above subproblem 5 is equivalent the projection gradient descent. - xz, ( He xT). When H, is an approximated Hessian matrix, the above subproblem (5) is equivalent to the proximal quasi-Newton decent. When
Let (x)x) = _x2 HGr. we have (x, v.))
H, is an adaptive matrix as used in [19], the above subproblem (5) is equivalent to the proximal adaptive gradient decent.
In Algorithm we use gradient estimator 0f( derivative wy
8x to estimate VF(xx), where the partial
af(a.e/) 1 is obtained by the backpropagation w.r.f. Zi--
di
4.2 SBiO-BreD Algorithm
In this subsection, we introduce an efficient stochastic bilevel optimization method via Bregman distance (SBiO-BreD) solve the stochastic bilevel optimization Problem (2). Algorithm describes the algorithmic framework of our SBiO-BreD method.
5

---

Algorithm 2 Stochastic ( Algorithm
1: Input: T.K 2 1, stepsizes y > 0, À > 0, Mm:
2: initialize: 2ig E X' and y/o E IR:;;
3: for 1- 0, 1,..... , do
4: Draw randomly b independent samples B, = {(t) and compute stochastic partial deriva-
tives E (Tt, yti B;);
5: Update Mc+11 = Y/ A1pp
6: Draw randomly 6( K + 1) independent samples B, (5e, Gh. ,... - "i and compute
stochastic partial derivatives Wy = V fzt, Me: B;);
7: Given p-strongly convex mirror function t/::
8: Update I++1 arg min { (ww,, x) + h(x) + Dev (x.
9: end for Output: Uniformly and randomly choose from {at; yo yo
Given K 2 1 and draw K + independent samples = -5, 15. (K-1),,, as in 15 definite stochastic gradient estimator:
23
we
II [I2 1 va V V Vuf()) (6)
-
ff Vf 1lz ys "
y:
where ~ ~,,0,1, K- is uniform random variable independent on E. It is easy to verify that fxx y, is biased estimator of ff(z, v). i.e. [
[V, { * V fz, y). For the gradient
estimator 66. thus define bias R(x, v) V v) Eg [ y: E) X x Rd2 R.
Lemma 3. ( Lemma 2.1 in (23) Under the about Assumptions
3). for any K 2 1, the gradient
estimator in 6 satisfies
LCjN (1 4
14 D
|R(E,))|
Lemma 5 shows that the bias R(x, y) decays exponentially fast with number K, and with choosing
K 1 log //TT//) ()) we have [[R(,, w) S 4. Let LCsy ()=4)*² S t. we have log( - 4)= S log( IC,yT T ). Due to < L, we have K 2 log( CruLiT) )/ log( ( Further due to $ S log z
let K log Log(LCCyyT/o) we have ||(( v)ll I T. Note that here we use Cory L.
To simplify notations, let E: = (Er, G2.
K-17. }. In Algorithm 2 we use mini-batch stochastic E f yei Ei), where Vf (ri
S2.5
gradient estimator w. V fz Mes B:)
K
1 1 Venoeen wi ((.))
= Vel(Na Mii Ec,e)
Veyg(xn yoi (..))
(Jdz
j=1
with & ~ 21,01111
1). Let R(a yc) = we Va v.) VS(2,, ye: B,)
f vc). it is easy to
we have [ yti B.)] RR( v1) ff vt). According to the above Lemma verify that |[ 301 < LC
K
4.3 ASBiO-BreD Algorithm
In this subsection, we propose an accelerated version of SBiO-BreD method (ASBiO-BreD) to solve the stochastic bilevel optimization Problem
via using variance reduced technique of Algorithm shows the algorithmic framework of the
SARAHHSPIDER/NWVRG [36 g 40 43
ASBiO-BreD method.
In Algorithm we use the variance reduced technique SPIDER accelerate SBiO-BreD algorithm. When mod (f, g) 0, we draw relative large batch samples B, = {(t) and B, = ( to estimate our stochastic partial derivatives it and wis respectively. When mod (t, # we draw a mini-batch samples I, = ( and Z, = / (b > by) to estimate 2 and ut, respectively. Let R(xt, yt) (x(,,, I,) Vf(x, 11) when mod (1, * O, we have B (xx, I+)] = R(xe, M.) + v [xx, wr) and [| w.)ll LC (1 -))

---

Algorithm 3 Accelerated Stochastic BiO-BreD (ASBiO-BreD) Algorithm
1: Input: T,K 2 1, q. stepsizes 7 0, A 0, (m 1 mini-batch sizes and bj;
2: initialize: Zig E and y/o E IR:;;
3: for 1.= 1, 1......................... 7 - do
4: if' mod (t. q) = 0 then
5: Draw randomly independent samples B, {(/ (G:)m1 and compute stochastic partial derivative 2 Vyg(Zz, Ve: Bi);
6:
Draw randomly b( + 1) independent samples B, (Er,,, Sh. ..
St. Ji=1 and compute
KK-11 11-11 11b
stochastic partial derivative w, fz ye: Bj):
7:
else
8:
Generate randomly b, independent samples I, = ( 1=1 and compute stochastic partial derivative v/ Vig( ye: Tt) Vyg(E,-1 1, 1: 14] + 1/-1:
9:
Generate randomly (ı(K + 1) independent samples In (Er, Sh ,., 1==1 and
compute stochastic partial derivative wi (r,,, Ie) (f( 11-1,,1111 Ix) ) w
10:
end if
11:
Update Mt+1 = Yt - Arp
12:
Given p-strongly convex mirror function ehy:
13:
Update T++1 = arg mingex { (w,, x) + h(x)) + 1 Dv. (x, xz)};
14:
end for
15:
Output: Uniformly and randomly choose from {are, yt We)ez
5 Convergence Analysis
In this section, study the convergence properties of new algorithms (i.e., BiO-BreD, SBiO- BreD, and ASBiO- ASBiO-BreD) under mild conditions. All proofs are provided in the Appendix B.
We begin with introducing a useful convergence metric || or El 2 to measure convergence properties of our algorithms. Given the generated parameter vector di at the 1-th iteration in our algorithms, as in 10 29).
we define the generalized gradient at the 1-th iteration as:
G. (xt 2(4)),
- = arg min (VVF(z;),)) h(x) + D x1) ZEx
where F(x) = f(x, (x)))(x)) or F(x) [e y ()): When (x(x)) = 1 ? X Rd and M(x) = c is a constant, we have || 2 (x,)) which is common convergence metric used in [11, 22). When (xx)= || 2X C Rd and h(x) is constant, our convergence metric is | = [ (x FVF(x.)) which was also used in [15].
Next, we provide some useful lemmas and some mild assumptions.
Lemma 4. (Lemma 3.1 in (23)) Under the above Assumptions 7
2
stochastic gradient estimator Rd,
(5(, is Lipsschct continuous, e.g., for $1,32 E X and
Egl Vf(21, Vf(22, E)1 L ||
x2l
where T.3- = 2T? + 6TA K 2ut-wz 6C7 12 K 9zy p + 6T,1 (L- (b-n)=Quu--=))) u=
Lemma 5. Suppose the sequence {x,, We generated from Algorithms and 3 1
Under the
above assumptions, given O < <m I for all t and 0 > 5 62. we have
31/
11 30 (1++1)113 $
llve -y- (xx)))
||
4
4
25m
25k²
V Vyg(
- - -vel12
||
12.1?.
6/
The above 5 follows the Lemma 28 of [17 used for minimax optimization.
Assumption 6. The stochastic partial derivative V Vog(a, v) satisfies E o9(2, ()) V Vyg(x,1) v) and B|| V (x( () Vyg(n, 12 < o². The estimated stochastic partial derivative ff v:
defined in (6) satisfies l (((z.v = &f(x. v) + R(x, v) and E. V E) fz
R(z, 2 < o²

---

Assumption 7. The mirror functions {vx(x)][ are p-strongly convex, where p >>> 0.
Assumption 6 is commonly used in stochastic bilevel optimization methods [3] 23 Assumption
7shows that the constant p can be seen as a lower bound of the strong convexity of all the mirror
functions (x) for all 2 0, which is widely used in mirror descent algorithms (29] and adaptive gradient algorithms [9]]
5.1 Convergence Analysis of BiO-BreD Algorithm
In this subsection, we provide the convergence properties of our BiO-BreD algorithm.
Theorem 1. Suppose the sequence {Ie, Mr Viz1 be generated from Algorithm Let 0 < Y S 33p
O<>< < t. K = log(T)) log((=>>)) + and 11./ - 11- (xx))] - A for all 2 0, we have
|1 16(4(20)- Φ+)
22
22
22L3
T
3Tpp
pTT
pT
p
where K. = L, L1 = LL+H)) L2 = 2Crylub LLauul and L3 = LCJx
F
n²a
to verify that our BiO-BreD algorithm has a convergence rate of ( Let =² G = e, we have Remark 1. Without loss of generality, ler L 2 1 A= = 2L. 7 = ALF
3p
and p = ([.). is easy
x T
T = =t Due to K = log(T)/ log( log(T~ma) + 1, we choose K
log( () for finding
stationary point of the problem ① we need the gradient complexity: Gelf,c) = 2T (12(-1) and Gelg,e) = KT ( ) and the Jucobian-vector and Hessian-vector product complexities
(V = KT = 0 and (V. = KT = 0112c
5.2 Convergence Analysis of SBiO-BreD Algorithm
In this subsection, we provide the convergence properties of our SBiO-BreD algorithm.
Theorem 2. Suppose the sequence {z,, Ve ) 1 be generated from Algorithm
2 Let A = 11300
y" (2.) K = 4 log( LC 0 <<< n
n I 1.0 1 min
3p
Iypud nund and 0 < X S
a
4LF
800 + 17
6L we have
1 S
32( - )h))
32A
752
400mA02
752
(8)
T
3Т
yp
3p²b
9yppub
Tp"
Remark 2. Without loss of generality, let L 2 1. X
Tt. 7 min (LF
AnonA nad and
B00K
4717
p= -L)), we have 7ip = 0
x² It is easily verified that our SBiO-BreD algorithm has a convergence
3 T _ and x² 5. we have T = 2x and b- 2x26-1, Due to K L log( LC,,T,, we have K OK log( (²) Ö(k). For finding e-stationary point of the problem ②). we need the gradient complexity: Gc(f,<) = 2hT = c² and Gelg, c) bT = c2) and the Jacobian-vector and Hessian-vector product complexities: (V e) bT O(K5E and
rate of 0
Let
HV(g.e) c) = KRT = Ö(xBe-2)
5.3 Convergence Analysis of ASBiO-BreD Algorithm
In this subsection, we provide the convergence properties of our ASBiO-BreD algorithm.
Theorem 3. Suppose the sequence
{Ee, 21
)
t=1 be generated from Algorithm
3
Let
A
llvo y² (2 b1 g. K L log( LC1xT 3p min
" 0 r
T)t S
< ?
S
(382 n ALF?
3p 2pnuA en 9puud) and 0 < X S min 1923 8
6L
100 L2 ). we have
9p
T-1
Σ 2 < 32(4(zo)= x*)
32A
152
4
+
TTpp
3Tp2
37
np7
LR
Remark 3. Without loss of generality, let L 2 1. A
min 6L:
9y
7
min
3p 3p 2pmnd en (pmu)) and p O(L), we have 7p ( It is easily verified that
38 n' 4L. 1913 8
our ASBiO-Bree BreD algorithum has convergence rate of 0 ( + ) Let _ and or2 S. we have
8

---

T 2x-c-= and b = 2x Due to K = log( LOSyTT, ), we have K = Ox (( (KK).
Let =q =q= k. 0.5 For finding c-stationary point of the problem (2) we need the gradient complex-
1. and the ity: Gc(J,e) 2( tr + 2b, T) - - and Golg,e) = bT 2b,T O(x²E (
Jacobian-vector and Hessian-vector product complexities: (g, = bT + 2b, = (xx0c-1.6)
and HV (g, E) = [ II + 2b,1) = Õ1= -.15).
reversenTD-B10
MIBO
211
Bi--BreD
90-90
211
stocciO Salo BreD
FSLA
SUSTAIN
Validation LOSS
Validation Loss
1.7
Validation LOss
1.
VR safiAAam
VIBO
ASBIO-BreD
1.3
1.3
13
0.9
0.
09
0.
05-
05-
0.1
01
01
10
Running Time (s)
Running Time (s)
Running Time (s)
ITversetDD 50
BSA
MABO
AD- B10
stecBlO
SUSTAIN
BIO BreD
BiioBBroD
FSLA
Validation Loss
Validation Loss
VRIO
ASBiD-BreD
Validation
WWNW www.
0.4
0.4
0.4
25 20
30 25 20
10 15
Running Time (s)
Running Time (s)
Running Time (s)
Figure 1: Validation Loss us. Running Time for different methods. We compare our BiO-Brel) with deterministic baselines (the first column), SBiO-BreD with stochastic haselines (the second column); ASBiO-BreD with momentum- bbasd or SPIDER/SARAH based baselines (the last column). We test two values of g: large noise setting @ = 0.8 (top row) and small noise setting @ = 0.4 (bottom row).
Numerical Experiments
In this section, we perform two tasks to demonstrate the efficiency of our algorithms: 1) data hyper- cleaning task [39] over the MNIST dataset [25): 2) hyper-representation learning task [9] over the Omniglot dataset 224] In the experiment, we compare our algorithms (i.e., BiO-BreD, SBiO-Bred
and ASBiO- BreeD) with the following bilevel optimization algorithms: reverse / BiO [1 22
AID-CG 12 AID-FP [2], stocBiO (22), MRBO (21), VRBO [21], FSLA 28 SUSTAIN 23
and VR- TR--aBiAAdam [18]. All experiments are averaged over 5 runs and we use a server with AMD
EPYC 7763 64- Core CPU and NVIDIA RTX A5000.
We use Bregman function (1)(x) 1 H, to generate the Bregman distance in our algorithms, where H, is the adaptive matrix as used in (19, i.e. the exponential moving average of the square of the gradient and we use coefficient 0.99 in all experiments.
6.1 Data Hyper-cleaning
The formulation of In this subsection, we perform data hyper-cleaning over the MNIST dataset 225 this problem as follows:
min Loat (A, w" (A)) Drvl
Σ
Ux w" (A),
s.t. w²(A)= = arg min len (), = DT
Σ
(Ai) w.)) v:) + C|
where 2(-) denotes the cross entropy loss DJ and Dy are training and validation datasets, respectively. Here (Ac)iED, are hyper-parameters and C is a tuning parameter, a--) denotes the sigmoid function. In experiment, we set C. 0.001. The dataset includes training set and validation set

---

Table 3:
Validation accuracy
Running Time (5-way-1-shot) for different methods (with L1
regularization)
Time
AID_ BiO
ITD_BiO
MRBO
FSLA
VRBO
VR-saBiAdam
ASBiO-BreD
20s
0,6509
0.6411
0.6103
0.6539
0.5951
0.6812
0,6653
40s
0.7365
0.7210
0.6971
0.7399
0.6805
0.7141
0.7403
60s
0.7762
0.7721
0.7519
0.7661
0.7429
0.7523
0.7830
Table 4:
Validation accuracy us. Running Time (5-way-5-shon for different methods (with Lj
regularization)
Time
AID AID_BiO BiO
ITD ITD_BiO BiO
MRBO
FSLA
VRBO
VR-saBiAdam
ASBiO-BreD
20s
0.8316
0.8131
0.8174
0.7993
0.7730
0.7753
0.8529
40s
0.8779
0.8621
0.8634
0.8485
0,8305
0.8188
0,8967
60s
0.9032
0.8968
0.8819
0.8824
0.8745
0.8640
0.9313
where each contains 5000 images. A portion of the training data are corrupted by randomly changing their labels, and we denote the portion of corrupted images g.
The detailed experimental setup described the Appendix A.1. For hyper-paramesee we perform grid search for our algorithms and other baselines to choose the best setting. The experimental results are summarized in Figure [ As shown by the figure, BiO-BreD outperforms the reverse algorithm; SBiO-Brel> outperforms ATD-FP/stooBiO and AID-CG methods, and ASBiO-BreD outperforms the other SPIDER based algorithm MRBO and several momentum -based variance reduction methods: MRBO, SUSTAIN, FSLA, and VR-saBiAdam
6.2 -ypee--eprrssnntation Learning
In this subsection, we perform the hyper-representation learning task over the Omniglot dataset 24 The formulation of this problem is as follows:
min Lual (A, wx (A)) == E Dv.el
Σ
(wE(A)) p(2;; A), v1) + +allAlla
(e..))DD.e
s.t. (A) arg min (A, wi
1
Σ
(wf ol;;; A). W|
|Dr,sl
where ((-) denotes the cross entropy loss, DT.E and Dv.s are training and validation datasets for randomly sampled meta task Here ((;-)) is four-layers convolutional neural network with max- pooling and 32 filters per layer (9. which denotes a representation mapping. À denotes the parameter vector of the representation mapping o(, -). and > 0 a tuning parameter guarantee the inner problem to be strongly convex. The term a Alll imposes the sparsity of hyper-representation.. In the experiment, set 0.001 and C = 0.01.
The detailed experimental setup is described in the Appendix A.2. The results of validation accuracy (test accuracy) summarized in Table and From these results, ASBiO-BreD algorithm outperforms other baselines in the non-smooth case. We also consider the smooth case, where the upper level problem is not added the Lı regularization. The results without Lı regularization given in the Appendix A.2.
7 Conclusions
In the paper, proposed class of enhanced bilevel optimization methods based on the Bregman distance to solve the serconnex-stroonly-ccooo convexx bilevel optimization problems possibly with nons- mooth regularization. Moreover, provided comprehensive theoretical analysis framework to analyze our methods. The theoretical results show that our methods outperform the best known computational complexities with respect to the condition number and the target accuracy for finding an e-stationary point.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1838627, 1837956, 1956002, 221 1492, CNS 2213701, CCF 221 2217003, DBI 2225775. FH was a postdoctoral researcher at the University of Pittsburgh. FH and HH are the corresponding authors.
10

---

References
[1] A. Beck and M. Tehoulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31()):677-775 2003.
[2] L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
[3] Y. Censor and A. Lent. An iterative row-action method for interval convex programming. Journal of Optimization theory and Applicattons, 34(3):321333,, 1981.
[4] Y. Censor and S. A. Zenios. Proximal minimization algorithm withd-functions. Journal of Optimization Theory and Applications, 73(3):451 -444. 1992.
[5] т. Chen, Y. Sun, and W. Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671 2021.
[6] A. Cutkosky and F. Orabona. Momentum-basee variance reduction in non-convex sgd. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 15236-15245, 2019.
[7] J. C. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. In COLT; pages 14-26. Citeseer, 2010.
[8] C. Fang. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
[9] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[10] S. Ghadimi, Lan. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267-355 2016.
[11] S. Ghadimi and M. Wang. Approximation methods arXiv:1802.008. 1802.0226,, 2018.
bilevel programming.
arXiv preprint
[12] R. Grazzi, L. Franceschi, M. Pontil, and Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748-3758. PMLR, 2020.
[13] Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2104.1483 14840, 2021.
[14] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2105.00 022.0020.6...... 2021.
[15] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor actor-critic. arXiv preprint MxXi:22007005170, 2020.
[16] F. Huang. S. Gao. and H. Huang. Bregman gradient policy optimization. In International Conference on Learning Representations, 2022.
[17] F. Huang, S. Gao, J. Pei, and H. Huang, Accelerated zeroth order and first-order momentum methods from mini to minimax optimization. Journal of Machine Learning Research, 23(36):1-70, 2022.
arXiv preprint [18] F. Huang and H. Huang. Biadam: Fast adaptive bilevel optimization methods. arXiv:2106. 11396, 2021.
[19] F. Huang, J. Li, and H. Huang. Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 11.9074-9088. 2021.
[20] S. Jenni and P. Favaro. Deep bilevel learning. In Proceedings of the European conference on computer vision (ECCV), pages 618 633, 2018.
[21] K. Ji and Y. Liang, Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint 202.::100200392
2021.
[22] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference Machine Learning, pages 4882 4892. PMLR, 2021.

---

[23] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances Neural Information Processing Systems, 34:30271- 30283, 2021.
[24] B. M. Lake, R. Salakhutdinov, and B. Tenenbaum. Human- concept learning through probabilistic program induction. Science. 350(6266):1332 2015.
[25] Y. LeCun, L. Bottou, Y. Bengio, and Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
[26] L. Lei and M. I. Jordan. On the adaptivity of stochastic gradient-based optimization. SIAM Journal on Optimization, 3002)1473-1100, 2020.
[27] J. Li, Gu, and H. Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint XXiv:2009.00690 2020.
[28] J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint arXiv:21 2021.
[29] W. Li, Z. Wang. Y. Zhang, and G. Cheng. Variance reduction on adaptive stochastic mirror descent. arXiv preprint arXiv:2012.13770 2020.
[30] H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations, 2018.
[31] R. Liu, Gao, Zhang, D. Meng, and Z. Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint urXivv2101.11517. 2021.
[32] R. Liu, X. Liu, X. Yuan, S. Zeng, and Zhang. A value-function--bssd interior-point method for non-convex bi-level optimization. arXiv preprint arXiv:2106.0799) 2021.
[33] R. Liu, Liu, S. Zeng, and J. Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances Neural Information Processing Systems, 34, 2021.
[34] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generie first-order algorithmic framework for hi-level programming beyond lower-level singleton. International Conference on Machine Learning, pages 6305-6315. PMLR, 2020.
[35] R. Liu, P. Mu, X. Yuan, S. Zeng, and Zhang. A general descent aggregation framework for gradient-based bi-level optimization. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[36] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. PMLR, 2017.
[37] P. Ochs, R. Ranftl, T. Brox, and T. Pock. Bilevel optimization with nonsmooth lower level problems. In International Conference on Scale Space and Variational Methods in Computer Vision, pages 654-665. Springer, 2015.
[38] T. Okuno, A. Takeda, A. Kawana, and M. Watanabe. On Iphyperpaaraeee learning via bilevel nonsmooth optimization. Journal of Machine Learning Research, 22(245):1-47, 2021.
[391 A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated mack-propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1732.1732. PMLR, 2019.
[40] 7. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pages 2403-2413, 2019.
[41] J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13677-,,38,, 2021.
[42] S. Zhang and N. Hc. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint
Neee:.0066048888 2018
[43] D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of machine learning research, 2020.
12


Reviews:
[{"review_id": "smplBqKfVVX", "reviewer": "Reviewer_rq9V", "summary": "This paper proposes a new class of bilevel optimization (BO) problems both in deterministic and stochastic forms. Compared to the classic BO problem, their outer function has an additional nonsmooth term, which makes their model more general, e.g. it contains the case when we use $L_1$ regularization.\n\nThen three algorithms are proposed. The first two are used to solve deterministic/stochastic BO problems (in the new form) respectively. And the last one is an accelerated version of the second algorithm.", "questions": "1) It is not very clear how to compute the partial derivative $\\omega_t$ in Algorithm 1 line 8. Maybe more explanation is needed.\n\n2) In Algorithm 2, the usage of $\\eta_t$ may need more explanations. Why the step size is $\\lambda \\eta_t$ however in Algorithm 1 $\\lambda$ is used?\n\n3) It is nice that in both the theoretical and experiment parts, the performance of proposed algorithms is better than baseline algorithms. But where does this improvement come from? When compared with baseline algorithms, I guess $h(x) = 0$, then the major difference is the usage of Bregman distance. Does it account for the improvement? If the authors can find more explanations, this work may have more theoretical value.", "limitations": "The efficiency of proposed algorithms depends on the choice of $\\psi$, which is used to define Bregman distance.  In the experiment part, it is chosen such that the updating of $x$ is very easy, i.e. a closed-form solution exists when $h(x) = 0$.  But when other $\\psi$ is chosen or $h(x) \\neq 0$, how to efficiently solve the problem to update $x$? The complexity of solving this subproblem seems does not appear in the comparison with other algorithms. Maybe the authors can make it more clear how to solve this subproblem for general $h(x)$.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: 1) this paper broadens the class of BO problems that appeared in previous literature which leads to the demand for new algorithms (because previous algorithms can not deal with non-smooth outer function); 2) under similar assumptions compared with related works, the algorithms proposed in this paper achieve the best convergence rate with known condition number\n\nWeaknesses: 1) This paper only mentions one circumstance where we need to consider a non-smooth outer function (when we use $L_1$ regularization).  That may narrow the unique field of application of this work, i.e. this work can do but the previous works can not. It is good to mention more examples/applications of using non-smooth objectives. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eOgVesah4x3", "reviewer": "Reviewer_Ra8S", "summary": "The paper studies the nonconvex outer-objective and strongly convex inner-objective bilevel optimization problem through the lens of Bregmen distance. The paper covers the deterministic optimizaton and stochastic optimization. in both situation, the authors provide the algorithm and its convergence analysis. The theoretical results shows the proposed algorithm with the aid of Bregman distance improve the performance with respect to the condition number $\\kappa$ and utilizing the variance reduction technique could further improve the dependency on $\\epsilon$ with a order of $\\frac{1}{2}$. The numerical experiment further prove the efficiency of the proposed algorithm.", "questions": "Q1: On the algorithmic design side, is there any extra effort that we need to make rather than directly replace the exact gradient with the gradient estimations? If it need some specific design, I would like to increase my score.\n\nQ2: On the theoretical side, is there any extra effort other than incorporating the biases introduced by the gradient estimation? I would like to increase my score of rating if so.", "limitations": "The numerical verifications of the problem is limited, for each algorithm, we only have one experiment. The experiment shows the proposed algortihms have lower losses. It would be better if the authors provide more experiments. I would like increase my score if the author could provide more experimental results during rebuttal.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper is obvious that it proposes the algorithms that could improve the theoretical upper-bound of previous state-of-the-art results, the presentation is clear, and the numerical experiment is sound.\n\nThe weaknesses mainly because the improvement is predictable. It is well-known that the variance-reduction technique could improve the oder w.r.t. the accuracy $\\epsilon$, and the Bregman disctance helps with the condition number $\\kappa$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NfOFi13e2Ws", "reviewer": "Reviewer_FFsk", "summary": "This paper incorporate the Bregman distance into bilevel optimization and propose three methods (BiO-BreD, SBiO-BredD, ASBiO-BreD) which targets at addressing deterministic and stochastic bilevel problem. Such proposed algorithms have matched best target accuracy $\\epsilon$ and improved the condition number $\\kappa$ compared with other benchmarks. Meanwhile, such analysis is adaptable for nonsmooth outer function. The experiments also demonstrate the superior performance of proposed algorithms.", "questions": "1. It will be better to include explanations for different Lemmas which can help reader to know what is the meaning behind each lemma in main body.\n\n2. It will be better to discuss the technical innovations compared with previous work [21].  Note that [21] refers to different works in main body and supplementary.\n\n3. It will be better to include a short ablation studies to compare current algorithms performances in different settings. (e.g. different batch sizes). \n\n4. The algorithm is analyzed in non-smooth function space while the experiments are based on smooth function. It will be better to try non smooth experiment. ", "limitations": "Non negative societal impact. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In terms of strengths, the proposed work shows the condition number improvement in terms of convergence analysis. Meanwhile, in different experimental settings, the proposed algorithms have demonstrated its superior performance individually. Both assumptions and convergence analysis are standard and easy to follow.\n\nIn terms of weakness, several Lemmas (Lemma2, Lemma4) in main body lack explanations. The theoretical analysis is very standard while it will be better to point out the technical innovations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept