Hessian Free Efficient Single Loop Iterative Differentiation Methods for Bi-Level Optimization Problems
Authors: Peiran Yu
Junyi Li
Heng Huang
Venue: Accepted by TMLR ()

Abstract: Bilevel optimization problems have been actively studied in recent machine learning research due to their broad applications. In this work, we investigate single-loop methods with iterative differentiation (ITD) for nonconvex bilevel optimization problems. For deterministic bilevel problems, we propose an efficient single-loop ITD-type method (ES-ITDM). Our method employs historical updates to approximate the hypergradient. More importantly, based on ES-ITDM, we propose a new method that avoids computing Hessians. This Hessian-free method requires fewer backpropagations and thus has a lower computational cost. We analyze the convergence properties of the proposed methods in two aspects. We provide the convergence rates of the sequences generated by ES-ITD based on the Kurdyka-\L ojasiewicz (KL) property. We also show that the Hessian-free stochastic ES-ITDM has the best-known complexity while has cheaper computation. The empirical studies show that our Hessian-free stochastic variant is more efficient than existing Hessian-free methods and other state-of-the-art bilevel optimization approaches.

Published in Transactions on Machine Learning Research (ottober/202)
Hessian Free Efficient Single Loop Iterative Differentiation Methods for Bi-Level Optimization Problems
Peiran Yu
peiran. grrrann.u@@tta..m edu
Deportment of Computer Science and Engineering University of Teras Arlington
Junyi
jumpiil as @gmmail com
Department Computer Science
University of Moryland, College Park
Heng Huang
heng edu
Department of Computer Science
University of Moryland, College Park
Reviewed on OpenReview: / net/ forum? X69U5CHMff
Abstract
Bilevel optimization problems have been actively studied in recent machine learning re- search due their broad applications. In this work, we investigate single-loop methods with iterative differentiation (ITD) for nonconvex bilevel optimization problems. For deter- ministic bilevel problems, propose an efficient single-loop ITD-type method (ES-ITDM). Our method employs historical updates to approximate the hypergradient. More impor- tantly, based on ES-ITDM, we propose a new method that avoids computing Hessians. This Hessian-free method requires fewer backpropagations and thus has lower computational cost. We analyze the convergence properties of the proposed methods two aspects. We provide the convergence rates of the sequences generated by ES-ITD based on the Kurdyka- Lojasiewicz (KL) property. We also show that the Hessian-free stochastic ES-ITDM has the best-known complexity while has cheaper computation. The empirical studies show that our Hessian-free stochastic variant is more efficient than existing Hessian-free methods and other state-of-the-an bilevel optimization approaches.
1 Introduction
Bilevel optimization problems arise in various machine learning scenarios, including game theory Stackelberg
(1952
meta-learning (Franceschi al. 2018 Zügner & Günnemann, 2019 Finn et al.) 2017a Snell al.
2017).
dyperparameter optimization [Franceschi et al. 2017 Pedregosa 2016 Grazzi et al. 2020 Mehra. &
Hamm
2021
Maclaurin et al.) 2015), and reinforcement learning (Hong et al. 2020). Please refer to [Liu
ct al.)
2022bp. A bilevel optimization problem involves two optimization problems, wherein one problem
(the upper-level problem) includes the solution of another optimization problem (the lower-level problem).
A typical formulation of this problem takes the following form:
min f(x) F(z, v(z)). ZER
(1)
s.t. y(1) E arg min G(x, y), vERm
where F: T + R and G 12 X m
R are continuuusy differentiable functions.
Gradient-basse based methods are popular for solving ! due their ease of implementation and efficiency. A key issue in gradient-based methods is how to approximate the hypergradient Vf. There two prevailing

---

Published in Transactions on Machine Learning Research (october/202))
approaches in the current literature: iterative differentiation (ITD)
that aims at approximating the Jacobian
of y(z) when caleulating the hypergradient (Franceschi et. al.
2017
2018 Finn et al. 2017a] Liu et al. 2020;
Ghadimi & Wang 2018 Ji et al., 2021 Rajeswaran et al.
2019 and approximate implicit differentiation
(AID) (Chen et al. 2022b Ji et al. 2021 Li et al. 2022
Gould et al., 2016; Lorraine et al., 2020 The
Tramework of ITD-based met hods are easier to understand. Also, compared with AlD-based methods, ITD-
basod methods dose not require solving an additional linear equation, which may have better accuracy in computation. In this paper, we focus on the ITD approach.
In general, if we view y(x) as function of x, ITD methods are designed based on the chain rule of the gradient of F(z, v())), which has the following form:
vf(z) V V,F(2,
(2)
How to approximate the J(((x)) is the key concern of ITD methods. In Ghadimi & Wang (2018), the closed form of (y(()) was considered. Ghadimi & Wang (2018) showed that
[v(x)) == V xy G(z, ((x)) yy yn G(z, G(z,)(=))-
The method proposed in Ghadimi & Wang 20188)
replaced (æ, (())) in the above formula with (a', g(t),, where I is the iteration. Franceschi ct al. (2017) provided forward and backward ways to approximate J (((x²)) directly. Ji et al. (2021) also used the backward way to approximate J(v(x'). To reduce the time and space complexity of estimating fz((z') [hhaban et al. (2019) proposed a truncated back-propagaal to approximate (y((²)). However, all above mentioned methods are double loop methods, which can be sophisticated and computationally expensive.
To enhance the efficiency of ITD-based methods, single-loop techniques have been proposed in prior work
(Yang et al. 2021 Guo et al.) 2021 Khanduri et al. 2021 Li et al. 2022 Chen et al. 2022a Hong et al. 2020 L. Guo et al. [2021 introduced SVRB, which updates y using a single gradient descent step. Chen
et al. 2022a) proposed STABLE, which updates x and y based on continuous-lime dynamics. One chal- lenge faced by SVRB and STABLE is the need to compute a matrix inverse in each iteration, which is computational expensive. An alternative approach is to use the Neumann series, as seen in Khanduri et al.] Yang et al. 2202)); Hong et al. (020).. In particular, the inverse G(),(z))) is approximated by Ex - Gx, v))' with some E N.. The greater b is, the less error this approximation has. However, if y not a good approximation of y(z), which is likely the case for most existing single-loop methods that only possess one inner loop to update y, the Neumann series approach to approximate J [(((x)) can still result in significant errors. In this study, we introduce a novel approach for approximating the Jacobian J(y(=)).
(2021b: hs
Another limitation in many existing ITD-type methods relies heavily on the calculation of the Hessian, its inverse, or the multiplication of the Hessian with a vector. These computations incur high computational costs. Additionally, scenarios may arise where computing the Hcssian of G is challenging or where G lacks second-order differenntiability For instance, cases where the lower-level problem involves robust regression, G can take the form of the Huber loss, which is not twice differentiable (Huber) 1964 Hastie ct al. 2009). Consequently, there has been a pursuit of methods that avoid Hessian computation. Gu et al. [2021) applied Gaussian smoothing (GS) techniques (Nesterov & Spokoiny 2017), enabling their method to bypass the computation of gradients of G. However, Gu et al. (2021) does not leverage any first-order information from F' and G, potentially leading to a larger discrepancy between the approximation and the true hypergradient. Similarly, SSo et al. (022)) employed GS techniques to estimate the Jacobian of y(z). Nevertheless, their resulting method needs to compute the full gradient of G, which is often impractical in real-world applications. Additionally, the methods introduced in Gu et al. (2021); (Sow et al. (2022) involve a double-loop structure, which can be inefficient. Thus, in this work, we propose a stochastic single loop method that avoids calculating the Hessian of G.
Another aspect that is overlooked in singlc-loop bilevel methods is the convergence analysis of the generated sequences, specifically the convergence of (a', v/) Sequential convergence holds significance as it illustrates the method's behavior in the long run. For example, it helps determine whether the accumulated point of the generated sequence stationary point of (I), whether the generated soquence achieves global convergence, and the its convergence rate. The third goal of this work is to provide sequential convergence guarantees for the songle-loop bilevel method.
2

---

Published in Transactions on Machine Learning Research (October/ 2202)
1.1 Main Contributions of Our Paper
In this paper, we propose elficient single loop ITDD-type (ES-ITD) methods for the deterministic and stochasticc bilevel optimization problem ([) and 7 Our contributions are three fold:
The proposed ES-ITD method makes use of much information about lower level updates the double loop method has but retains the single loop computation cost.
We propose a computationally efficient Hessian free method for the stochastic bilevel optimization problem 7 Based on a natural extension of ES-ITDM using the stochastic gradients or Hcssians of F and G, we use the Gaussian smoothing techniques to approximale the stochastic ic Hessian of G. The resulting method called Hessian free stochastic ES-ITD method (HF-SES-ITD), Compared to current single loop method, HF-SES-ITD method only uses the first order information to approx- imate the Jacobian of (z). Compared with Hessian vector multiplication, our method is much cheaper because it only needs computing gradient vector inner product.
We provide convergence analysis of the proposed methods. For the deterministic method, we analyze the convergence of the sequences {-²), {u/} and (J'} generated by ES-ITDM, where J' is the approximation of the Jacobian of y(z'). To this end, we propose new potential function. We show that the itcrative value of the potential function is nonincrcasing. After that, we show that the successive changes of the generated sequence converge to zero. We show that any accumulation point of {ar) } is a stationary point of (T). Furthermore, under the Kurdyka--.ojasieviez (KI.) property, we derive the convergence rates of {(a ,y", J').. Especially, when the potential function is KL function with exponent 2. we show that {(x', .V", J")} converges linearly. As far as we know, this is the first work that provides the convergence rate of the sequences generated by single loop methods. Compared with sequential convergence analysis for mothods solving general nonconvex optimization problems, the nested formula for updating JL+1 in our method makes a technical challenge in our sequential convergence analysis nontrivial. We also give convergence guarantees of the stochastic variant of ES-ITDM. We show the resulted method has complexity of O(c-2) to reach e-stationary point under mild assumptions.
We evaluate our methods via the hyper-parameters learning task. We first compare our methods with the current Hessian-free methods (Gu et al. 2021 Sow et al. 2022). Then we compare our
methods with other popular single loop bilevel optimization methods in Franceschi et al. (017):
Grazzi et al. (2020); Ji et al. (2021): Grazzi al. (2020); Sow et al. (2022); Guo et al. [2021] ; Chen
ct al. (2022a). In both comparisons, our stochastic Hessian froe fully single loop method has better performance in both time and accuracy.
Table 1: Comparisons between our method and ESJ. BA, ITD-Bio, FMM = Forward Mode Method, TTSA, SUSTAIN, MRBO, SVRB, STABLE. HVM Hessian Vector Multiplication; ds= diminishing stepsize; cs=
constant stepszise; denotes an (e + variance (aroors--cccracc; for / V max.ter) [||
Methods
Loops Use Matrix inverse
Use HVM
Sequential Convergence
Complexity
PSJ Suy al.
2222
No
O O] with de
No
HA Ghadimi & Wang 2018
Yes
Oie ") with
Deterministic Methods
Double
1- Ji es nl.
Oie with es
FMM Franorachi et Al
FSS
DTK
Single
O "] with es
TTSA Hong, al. 2020
No
O(c-25) with ds
SUSTAIN
Khhandur
Yes
O with de
MRBO Yaug et al
O/e ") with da
Scochastic
Methods
SVRB Cno ot al.
2021
Single
Yes
O/e "] with dis
STABLE
Chen et al.
A722a
0 with
SES-TTDM with (S)
Ole with
No
SES TTDM with (HP)
No
O with
2 Related Work
Comparisons between our methods and current ITD methods are summarized in Table 1
3

---

Published in Transactions on Machine Learning Research (october/202))
Bilevel Optimization Methods. When F and G in ①I) are deterministic functions, Franceschi et al. (2017); Ji et al. (2021) proposed double loop ITD methods for (1). Ji et al. (2021) used the backward way to approximate (()(z))) For stochastic problem 77. Ghadimi & Wang (2018) introduced a double loop method that solves the lower level subproblem with multiple stochastic gradient steps and replaces cach element in 2 with the stochastic gradients and Hessian. Besides double loop methods, single loop methods
were proposed in Yang et al. (2021): Guo et 2021 Khanduri et al. (2021 ; Li al. (2022) Chen et al. p:
(2022a); Hong et al. (2020g; Li & Huang 2024). Guo al. (2021) presented SVRB which updates y 41 using
one stochastic gradient descent step. SVRB employs the variance reduction on each element in the right- hand side of Cheh et al. (2022a) proposed STABLE that updates and y based on the contimouss-time dynamics. Also using Neumann series, Yang et al. [021]) designed a momentum-basee stochastic single loop method. Yu et al. (2024) considers adding dropout to address the overfituing problems in bilevel training tasks.
Sequential Convergence Analysis. The soquential convergence analysis a fundamental problem of first- order methods. Tt has been investigated for nonconvex mininization problems (Bolte et al. 2014 Attouch
et al. 2010: Yu et al. 2021 Li & Pong] 2016). However, the sequential analysis of bilevel optimization methods is still in its carly stages. Chen et al. (2023) used the KL assumption to analyze the sequential convergence of an AID-type method. However, they assume that the linear equation in their AID method is solved exactly, which creates a gap between theory and practice. Additionally, the method they analyze is a double-loop method, whereas ours is single-looped. Liu et al. (2022a) demonstrated that the sequence generated by their proposed method accumulates at a stationary point. In our analysis, we further provide the convergence rate of the generated sequence. Under the KT, assumption, show that it can converge lincarly, sublincarly, finitely.
3 Notation and Preliminaries
In this paper, we denote IR" the n-dimensional Euclidean space with inner product (5-) and Euclidean norm || |l. We denote the spectrum norm a matrix _g as ||A|]] and the Frobenius norm A as ||A|e For ramdom variable & defined on a probability space (E, P), we denote its expectation as E. Given an event A, the conditional expectation of & is denoted as (A(E).
R" + I-,0, oo] is proper if domf {o E R" : f(x) oo} is not empty and ʃ never equals -o. We say proper function ʃ is closed if it is lower semicontinuous. A proper closed function is said to be gevel-bounder if for any a E R, the set {x f(z) I a} is bounded. For a function F Ru+m + R we denote the function F(x, y) with respect to y for a fixed x as F(x,)) and denote the function F(z, v) with respect to x for a fixed as F(-y). Following Rockafellar
We say an extended-reall
function
Wets 1998), the regular subdifferential of a proper function I at x E domf is defined as 0f(x) = (5 E R" 0}. The subdifferential of f
lim inf [(=)- a, 282 [x==||
domf is defined by 0f(z) {E R"
t with xt + and f(x*) - fx). 5* E with 5o E 0f(a*), Vk). For x & domf, we define 0f(x) = (z)) 0. We denole dom&f = fa af(x) 0}- We say I is a sationary point of f i 0f(x). For twice differential function F Rm R" I. we denote V.F(x, y) and vyF(z, y) the partial gradients aF(e.) and @F(x.)) 8x
correspondingly. We denote F(z, v) = Ffr and V Fyg v) = Ff For a 8y
Budy
Bg0y
function g(x) ;= [g {) with distribution P, let S = |/1 be mini-batch of samples drawn from P. We denote g(I; [S| 1 {();
Now, we first present the basic assumptions for
Assumption 1. Consider Suppose the following assumptions hold:
(1) Suppose F is Lipschitz continuous with modulus Lpp
(ii For any fixed T, ((..)) and V ((,,)) are Lipschitz continuous with modulus L > 0 and LPg > 0 respectively, i..., for any V1 and y2, it holds that F[,,F(2.))) Fz S Lf2 and |/ F(F. v1) V. F(F y2)ll & Thg-
4

---

Published in Transactions on Machine Learning Research (ottober/202)
(ii) There erists Cy 0 such that , & Cg for any x and y-
(tv) For ony fized y, VyP(, is Lipschitz continuous with modulus L > Assumption 2. Consider
Suppose the following assumptions hold:
(1) Denote (x, G is twice continuously differentiable in In addition, suppose V,G(z,,)) is Lipschitz continuous with modulus LG > 0 for any x.
(6)) For ony n, G(a,)) )) is strongly conner with modulus PAG-
(ia) For any x, V (a., and V (ax, are Lipschitz continuous with modulus Loy and Log.
(tv) For any y, G(-s)) v) and V J G(.,)) are Lipschitz continuous with modulus Log and Lay
G(, v)ll S Cany and IV G(a, w)ll S Cayy for (v) There erist Caay 0 and CGyy such that V 2 ony and y.
4 Efficient Single Loop ITD Method for Deterministic Problem
To develop the fully single loop method, we investigate a basic double loop ITD algorithm. At each iteration 1, let //11 = x (a'), where y (x²) the output of Algorithm Note that y (x*) a function of a!
Algorithm A gradient descent method for min, G(r', v)
Input y¹ 7 0. For ls O...., K Let 1 (2)))))))))))))---))))))))))))))
Output y/+1 = K (z²).
The double loop ITD method approximates the Jacobian of v(x:) with the Jacobian of yi (xt).. Using the chain rule, have the following formula for the Jacobian of y (a.).B
K-1
K-1
J(gl'(xx)) = - GN, / / (x')) ))x
(
(I Vo +(("))
(3)
k=0
Then, at the outer loop, we lot JL+1 = ((y (x!)) and update al+1 with
1 = -od--VVFFu
BV F(. g + "V
K1 we get a single loop bilevel method. However, the resulting Jacobian approximation becomes (xy) - G(z', y'0). VzyG(z', ( does not make use of previous information about the y coordinate. Even if choose y/0 in Algorithm 1 to be the last update y² "Jy" still does not make use of the previous information such (V,y G 3 h (VzyG(z', .v)).. Thus, simply changing the double loop method to single loop method by letting K will lose information in the previous iterates. However, we notice that
3 implies
Jy N G (K())) v. L (k()))
(4)
Inspired by this, we update
Je+1 = -I- -V
(5)
We denote K- 2mbi (1- V Gla (/-1)) when by convention

---

Published in Transactions on Machine Learning Research (ottober/202)
and propose Algorithm mation of the Jacobian.
2
In this way, we make full use of the previous information to update the approxi- implies that
5
J V G( (T G(r
(6)
s=k+1
Comparing 6 with 3 there are the following differences:
1/t based on (3) needs O(K²) Hessian-vector mul- tiplications (HVM), where K is the iterations of the inner loop. The cost of each HVM is (mmxx m)) using the technic in Pearlmutter (1994). Here, We have two equivalent ways to update Jz+ V F''',, y either by using (5) and making use of J or by using (6) without involv- ing Js. When applying deduction (5) in the algorithm, we need n + HVM computations. However, when using (5) update J(+1, we must compute J = J' (1 - >V yy G(x', y)) - - Ga'' y²), which involves an R=xm x R matrix operation. When calculating J V uy G(a',, v²), it requires n HVM computations. Therefore, in each iteration, actually need + HVM computations, which is less than ((k2). Thus, our method is advantageous when + S k.2. On the other hand, when using (6), we require 12 HVM computations. In summary, our method outperforms the classical ITD method when either n +1+1 k2 or k?
At iteration I, computing (
The formula in 6 makes of historical updates {.",...,,')) x') and fv....., s'). depends on {x'}. Although making use of historical updates requires more storage, 6 makes use of more information to approximate the Jacobian of y(x²).
while 13 only
Algorithm Efficient Single ITD Method (ES-ITDM) for
Input: a, 8, > 0, x0 R", y R", Jo R= and N e N+. for / = O,...,N N do
Let g = y a G( y²)
4:
Compute
vf(z)) (/ F(1',ttt))
with J/=1 be defined as in 6
Let rl+1 xt - BV (xx). end for Output (y N.
5 Efficient Single Loop ITD Method for Stochastic Problem
7
In many applications that involve bilevel optimization problems, we need to consider a stochastic bilevel problem:
min ((x) = F (()) EERt
(7)
s.t. y(œ) arg E G vERm
where and p' are distributions.
One natural idea is to replace the gradient/ Hessian in Algorithm 2 with the mini-batch gradients/ Hessiann of F and G. At iteration 1, we draw sample batch S Then using
J
(8)
k=0
s=4+1

---

Published in Transactions on Machine Learning Research (October/2D) 2024)
to approximate J!+1 in
Now, based on the bati-batch Hessian of G, we propose Hessian-free approach to estimate the Hessian of G. We present this approach as (HF) in Algorithm
Algorithm Hessian Free Stochastic efficient single loop stochastic ITD method (HF-SEE-ITDM) for (7)
Input: a, a, N.V. 0, x R", 50 E Rm, "Rm, N do Draw sample batch I' change the notation in the proofs. Let y/+! s - aV -VVG((t.
N+
for 1= 0,1,,,
Draw sample batch B and St. Compute
vf(z')= +t + (J'tI ,1')),
with Ji-1 defined in 11
5: Let xl+1 x' (z)) end for
The idea of Algorithmm is as follows. We aim to approximate V zz G(z y; 8') and G(, y; St) with the first- order information of G. Giy y; S') and V G y: S consist of the gradients of {V,, G(x', S') with respect æ and y. Inspired by Nesterov & Spokoiny (2017), we use Gaussian smoothing technique follows. Pick Q N, 1 > O and v 0. For j . Q, generate ud I) E R and of NN I) R". For 1,..., m, let.
Q Vi, G(al +
v,, Gl G(a
V G( ~
Q 1=1
and
Q
Vy G( + vefj - G(ali
1
G. s =
Q
Notice that the Tractions in the above equalities are scalers of dimension GzyG(a ys 8') and G(z S') as follows:
Now, we approximate
(V.V yı G(a S'
(VG(' + s')) vo(s', (u))²
pQ
(9)
(V.V Vm C(ai./::')
=: C(r'()
and
V. Gle,
2 Σ
(VG('
o +rojss) VG(o', (0))²
vQ
(10)
V.V. G(s.
1=1
Now, we use
j++ Gen , DI (I- A De g(a)))))))
(11)
e=k+1
to approximate JL+ in Remark Now we compore the computation cost of SES-ITDM and HF-SES-ITDM. The main cost is computing
F(r +1:

---

Published in Transactions on Machine Learning Research (October/200)
05035
200
275 11.
60
JoguglRunning Time (s)1
RoguolRunning Time (si)
65
P0000
10703
10000
SPGFTOM
Test Acc
Test Acc
(egua(Running Time (sl)
logut/unnnig Time (6))
Figure 1: Test Accuracy w.r.t. Jogro(Training Time) for the hyper-representation task. The top two plots are 5-way- 1-shot (left) and 5-way-5-shot (right), and the bottom plots 20-way-1-shol (left) and 20-way-5-shol (right). Postfix of ESJ and HOZOJ methods is the number of queried noise vectors (Q).
When jt+1 is chosen as 8 compuling D' needs compute the HVM. this end, we need to compate the gradient N,G first and then compute the HVM, which requires backpropagation in implementation. However, when ju+1 is chosen as [1 computing D' only needs to compute the gradient V,G and one ventor inner product using the formulas and 10). Thus, compuling D' only need 1 backpropagation implementation. When the dimension of porameters is large, this can save time compared methods that need to compute the gradients and HVM. However, computing Di with ji+1 in [11b needs to calculate Q times of gradients and inner products. Thus, there is tradeoff between using and
6
Convergence Analysis
6.1 Convergence Analysis for Algorithm
Now analyze Algorithm We first give the following theorem that will be used in proving main convergence properties.
Theorem 1. Consider and let Assumptions and 2 hold. Let ((a', V, J))3 be generated by Algorithm
2
Suppose F is bounded from below. Suppose (0, Then there exist B > O and E (0, ) A >>0 0
and 8 (0,1) such that
H11 < H Aliz - 1 -ollu(z)) - +2211 (()(((()))) - -
where H' = ((), 1-1 1, 1 J(+1] with
H H x' y, = f(x) + A|Ix 1'12 [1v(x) - v112 +1J(v(x))) - -1B..
Furthermore, {1t') is nonincreasing and there exists H" such that (1'-1) is convergent H
Thanks Theorem we now have the following observation indicating the limiting point of the generated sequence satisfies the first order optimality condition of

---

Published in Transactions on Machine Learning Research (october/202))
Corollary 1. Let assunptions in Theorem | hold and suppose F is level-bourded. Then any accumalation point x² of { salisfies [x(²)) =0. 0. In addition, any accumaaaatio point y² of {y'} is an optimal solution of the lower level problem in 1 defined with x².
Now, show the global convergence properties of the sequences generated by Algorithm To this end, we introduce the Kurdyka-foojssiewivz (KT.) property.
Definition
satisfies the KKurdyka-Kojasievitnn Function). We say a proper closed function f IR" + (-00, oo) (KL) property at E domdf with exponent 0 [0,1) there are E (0, 0o), neighborhood V of and do >0 such that dist(0, (z)))) 2 ao(f(x)) f()))* for any E V with (() < f(x) < f() + a. A proper closed function f satisfying the KL property with exponent & E [0, at every point in dom f is called KL function with exponent 0.
Many functions KL functions. It is known that proper closed semi-algebraic functions (ie.. functions whose graphs are unions and intersections of polynomial functions) satisfy the KL property, Attouch et al. (2100); Li & Pong (018);; Attouch et al. (2013); Boltc et al.] (2017). Semi-algebraic functions include widely used losses such as quadratic loss, L2 loss, Huber loss, hinge loss, and 0-1 loss. KL property is a general property in convergence analysis when the considered function is not smoothness.
Under the KL assumption, we have the following convergence rate of ((z', ((al.y, J+I)} generated by 2
Theorem 2. Consider [ Let H be defined as in Theorem 1 Suppose assumptions in Theorem hold and F is level-bounded. Suppose H is KL function with exponent 0, then
(1) when = 0, {(x', y }(+)} converges finitely;
(1) when 9 E (0, ((+) vi, }( converges linearly;
(ml) when e (2, 1), ((r, J[+]]] converges sublinearly.
Remark 2. Note that, together with Corollary Theorem shows that the limiting point x", to which the sequence z! converges, is stationary point of In addition, the limiting point v", to which the sequence y' converges, is the optimal solution of the lower-leved problem in ① defined with x².
Remark 3. Since the lower-level problem is strongly conver, the lower-level minimizer is unique. When the lower-level problem is semi-algebraic, and since y(x) is the infomum projection of a semi cemi-algebraic function, its graph is also the intersection of polynomial functions, making y(x) semi-algebraic, well as its Jacobian J (y(z)). If the upper-level objective is also semi-algebraiie then the potentiol function H is KL function, satisfying the assumption in Theorem
6.2 Convergence Analysis for Algorithm 3
In this section, we make the following assumption. Assumption 3. Consider
Suppose for any fized y,
EV, VV,,(rr = ((, - Szz.
Suppose
E
V GG V,G(E, S cg.
E 2 G(z, y) G,, (2) < 2zy
E V by G(r.y:) - G( 1 2
Now, we present the short version of the convergence result. of Algorithm
9

---

Published in Transactions on Machine Learning Research (October/ 2024)
0.7
66
04
63
300
400
Figure 2: Test Accuracy w.r.t. (Trainnggg Time) for the neper-repressentaion task. Ablation study HF-SES- ITDM behave when choosing different Q, and μ. As we can see, the greater Q is, the slower the algorithm is. But when I, the accuracy is still competitive with the accuracy with greater Q's
Theorem 3. Suppose Assumptions 1 222 and hold. Suppose < t.2 Let {x'} be generated by Algorithm
with JL+1 in Step & being generated by [1] based on Gaussian sampling. Suppose the optimal value for is f 20. Then there erists small enough such that
1 E E((
En Ez,
N+1
N+1
where
E )i(o + AI([(=)) 1*) + A1llo(=)) 1012 + Aill((((e)) VayG(=",
for some A1 > 0, Eg = Ag max A zy + Ayg. oc) for some A with Aay and Any being the upper
bound of E V G(* v²) V ay Gi , w/1l and ,,,s s G(x v²) - V Gy s²)2 respectively.
7 Experiments
In this section, we test the efficacy of the proposed algorithms: Algorithm 2 and Algorithm 3 on the hyper- representation learning task Franceschi et al. (0018) Hyper-representation refers to a shared representation (or shared deep neural network) across multiple tasks in a meta-learning framework. The parameters hyperparameters. Let o(= denote the hyper-ropresennation
the shared representation are referred mapping, parameterized by When applying this to solve specific classification task, linear layer is added top of the bypen-ropresentation, and only the parameters À in the shared 'nyper-representationn remain fixed. To train the parameters in the hyper-representation. Franceschi et al. (2018)) formulated it as the bilevel programming problem [ where the upper-level objective minimizes a validation loss, and the lower-level objective minimizes a task-specific training loss. Specifically, we have the following problem:
trained, while the parameters
Σ (((=*())) (2)) A),
min Dv.e De
s.l. w" w²(A)= arg min ler (A, w),
where
4rr w)
Σ
10w (0o +.))))+Cll +|
DT.E (F.g))EDT
2Qur code available htw.aa/wwwiiire///ggttoo.oeeerra http:///gttthh.cmmmppssea////sss
10

---

Published in Transactions on Machine Learning Research (october/202))
with 1(-) denoting the cross entropy loss, Dr,g and Dv. being training and validation dataset for a randomly
sampled meta task. Here À = (Ai)iED, are hyper-representatoons and C 2 0 is tuning parameter to
gaurantee the inner problem to be strongly convex. In experiment, we set C = 0.01. All experiments are run over a machine with Intel Xcon Gold 6248 CPU and 4 Nvidia Tesla V100 GPUs. The code is written with Pytorch.
In the task, we perform the reperrrepresentationn learning task over the Omniglot dataset Lake al. (2015) the details of the ominiglot dataset and the formulation of our typer-representation task are inchuded in the supplementary. In general the target of our task is to learn useful typer-representation such that we learn lincar classifier on top of it with small number of samples and training cost.
We first compare our algorithms with two existing Hessian free methods, i.e. the HOZOJ Gu et al. (2021 ESJ Sow et al. (002) and F2SA in Kwon et al. 2023). HOZOJ is a syper-parameter optimization method which applics the evolution strategy over the hyper-gradien directly. ESJ applics the evolution strategy over the Jacobian matrix. [won et al. (2023) view the bilevel problem as a constrained optimization problem and use penalty-type method that only requires the first-order information. As comparison, ITDM instead approximates the second order derivatives Vay and y. The experimental results are summarized in Fig. ! We search dyper-parameters for all methods, and we find setting the outer learning rate 3 = 0.1 and the inner learning rate a = 0.4 can get good performance for all methods. For F2SA, A, we set the additional Lagrange multiplier as We find the scale of the noise (μ and v in HF-SES-ITDM and μ in ESJ and HOZOJ) and the number of Gaussian vectors (Q) are very important for the model performance.
HF-SES-
We also test HF-SES-ITDM with 11 being replaced by (8, which is named SES-ITDM. As shown by Fig. 1 HF-SES-ITDM greatly accelcrates the SES-ITDM by avoiding computing the sccond derivatives explicitly. Furthermore, the ESJ and HOZOJ methods need to query a relatively large amount of noise vectors to get good performance. For example, in the 5 way 1 shot case, ESJ needs to query 50 noise vectors to reach the same test accuracy as HF-SES-ITDM with Q = 1, and has longer running time cost. For HOZOJ, we need to query at least 50 noise vector to get converged training, while for 100 and 500 noise vectors, we still observe a great performance margin compared our method. The need of many noise vectors for ESJ and HOZOJ might come from the evolution strategy used in both methods to approximate higher level propertics, and thus lead to more noise.
Figure shows how HF-SES-ITDM behave when choosing different Q, and μ.. As we can see, the greater Q is, the slower the algorithm is. But when Q = 1, the accuracy is still competitive with the accuracy with greater Q's.
8 Conclusions
In this paper, we focused on studying the bilevel optimization problem and proposed a new single-loop ITD method that more efficient approximating the Jacobian of the lower-level solution with respect to the upper-level variable. We proposed Hessian-free stochastic bilevel optimization. Based on a natural stochastic extension of ES-ITDM, we first proposed Hessian-free stochastic ES-ITDM. This Hessian-free variant eliminates the need to compute the Hessian vector multiplication, thus potentially leading to faster implementation. We theoretically analyze the proposed methods. For the deterministic method, we investi- gate the global convergence rates of the generated sequences. As for the stochastic method, we conducted an analysis its complexity. Our methods were validated using the hyper- representation learning task. In experiments, our Hessian-free stochastic ES-ITDM demonstrated greater efficiency compared to existing Fessian-frce mothods.
Acknowledgment
This work was partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBI 2405416, CCF 2348306, and CNS 2347617.
11

---

Published in Transactions on Machine Learning Research (October/ /202)
References
Hédy Attouch and Jéröme Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program., 116((-2):5-16, 2009.
Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the lurdyka--ojasiewicz inequality. Math. Oper. Res., 35(2):438 457, 2010.
Hédy Attouch, Jéróme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods. Math. Program., (17())))911 129, 2013.
Amir Beck. Chapter 10: The proximal gradient method. pp. 269 269-329, 2017.
Jérôme Bolte, Shoham Sabach, and Mare Teboulle. Proximal alternating linearized minimization for non- convex and nonsmooth problems. Math. Program., 146(1-2):459 -94,, 2014.
Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W. Suter. From error bounds to the
complexity of first-order descent methods for convex functions. Math. Program., 165(4):471 507, 2017.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A singlettimescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30
March, 2022a.
Ziyi Chen, Bhavya Kailkhura, and Yi Zhou. A fast and convergent proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization. 2022b. URL sittps://dof: http:///oo...o//..//// 48550/.85555ra... aarivv. 2203.
16615
Ziyi Chen, Bhavya Kailkhura, and Yi Zhou. An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimizationn.n..omommmoo Mach. Learn., 112(5):1443 1463, 2023. doi: 1L1007/s109944022-00000 0632966.
URL httl:/tpss///o..oo///0000///////
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 94th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August, 2017a.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic mela-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August, 2017b.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel pro- gramming for hyperparameter optimization and meta-learning, In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10- 15-15, 2018.
Saced Ghadimi and Mengdi Wang. Approximation mothods for bilevel programming. 2018.
URL https:
//arxiv.org/aate wwwpoogg//////oooeeeeeee 120.100020000 02246
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo.
On differentiating parameterized argmin and argmax problems with application to bi-level optimization. 2016. URL httt:://axxiiii http:://arrii.oorr/b//10100/ 05447
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the itcration complexity of hypergradient computation. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 18 July, 2020.
12

---

Published in Transactions on Machine Learning Research (october/202))
Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyperparameters via automated learning algorithm. 2021.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochasicc variancee-edduced meth- ods for multi-task stochastic bilevel optimization. 2021. URL httpps///aarrr..orr////////..../
Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition. Springer Series in Statistics. Springer, 2009.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. 2020. URL attps://arxiv.org/ /bs//
Peter Huber. Robust estimation of location parameter. Ann. Math. Statist., 35(1):73-1011 1964.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near- optimal algorithm for stochastic bilevel optimization via double-momentumm. In Advances in Newral In- formation Processing Systems 34: Annual Conference on Newral Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. A fully first-order method for stochastic bilevel optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engel- hardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, 1CML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 18083 18113. PMLR, 2023. URT. luttps://proced::
mlr press//2022/kxon2222 html
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332 1338, 2015.
Guoyin Li and Ting Kei Pong. Douglas-rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program., 159(1-2):3711400) 401, 2016.
Guoyin Li and Ting Kei Pong. Calculus of the exponent of kurdyka--lojssiwwicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math., 18(5):1199- 2018.
Junyi Li and Heng Huang. Provably faster algorithms for bilevel optimization via withoutt-replaemment sampling, Xix preprint drXiv:2411.05868, 2024.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Thirty-Sizth AAAI Conference on Artificial Intelligence, AAAT 2022, Thirth-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 1, 2022.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Confer- ence on Newral Information Processing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, Novem- ber 28- December 9, 2022, 2022a. URL http://papers.rt nips. httpppscccpppprrreeee fiaaper_iileeppppr///000 hhahh/ Abw.eer---tsttttt-Caooteeee Conect--oooofeeenn html
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithric framework for bi-level programming beyond lower-level singleton. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July, 2020.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-lovel optimization for learning and vision from unified perspective: A survey and beyond. IEEE Trans. Pattern Anal. Mach. Intell., 14(12):1004551000 10067, 2022b.
13

---

Published in Transactions on Machine Learning Research (october/202))
Tianxiang Liu, Ting Kei Pong, and Akiko Takeda. A refined convergence analysis of pdcae with applications to simultaneous sparse recovery and outlier detection. Comput. Optim. Appl., -3(1)691-,00, 2019.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In The 23rd International Conference on Artificial Intelligence and Statistics, ATSTATS 2020, 26-28 August, Online (Palermo, Sicily, Italy). 2020.
Dougal Maclaurin, David Duvenaud, and Ryan P. Adams. Gradient-based hyperparameter optimization through reversible learning. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July, 2013.
Akshay Mehra and Jihun Hamm. Penalty method for inversion-free deep bilevel optimization. In Asian Conference on Machine Learning, ACML 2021, 17-19 November, 2021.
Yurii E. Nesterov and Vladimir G. Spokoiny. Random gradient-free minimization of convex functions. Found. Compal. Malh., 17(2):527 566, 2017.
Barak A. Pearlmutter. Fast exact multiplication by the hessian. Nearal Comput., 6(1):147-160, 1994. doi: URL https://ddoi.rr///0 wwwp:/..11nn/no..oo 1994. 6.1.....
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Newral Information Processing Systems 32: Annuual Conference on Newral Information Processing Systems 2019, NewrIPS 2019, December 8-14, Vancouver, BC, Canada, 2019.
R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis, volume 317 of Grundlchren der mothe- matischen Wissenschaften. Springer, 1998.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back paok-propngntion for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April, Naha, Okinawa, Japan, 2019.
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In Advances in Newral Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, Long Beach, CA, USA, 2017.
Daouda Sow, Kaiyi Ji, and Yingbin Liang. A novel hessian-free bilevel optimizer via evolution strategies. 2022. URL htRLsttps://eee https://arxivi org/ 20t.://211.00000
H. Von Stackelberg. The Theory of Market Economy. Oxford University Press, 1952.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In Advonces in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, Barcelona, Spain, 2016.
Bo Wen, Xiaojun Chen, and Ting Kei Pong. A proximal differeence-o--convexx algorithm with extrapolation. Comput. Optim. Appl., (9(2):297-32 324, 2018.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. In Advances in Neural Information Processing Systems 94: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 6-14, 2021.
Peiran Yu, Ting Kei Pong, and Zhaosong Lu. Convergence rate analysis of a sequential convex programming method with line search for class of constrained differenco-of-coonvex optimization problems. SIAM J. Optim., 313:220024 2054, 2021.
Peiran Yu, Junyi Li, and Heng Huang. Dropout enhanced bilevel training. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.ner net, 2024. URL httt:s://opereviiiiii httpp://gggaaeeeeee..eeee//rttop http:/oorrmm.///01111110
14

---

Published in Transactions on Machine Learning Research (ottober/202)
Daniel Zügner and Stephan Günnemann. Adversarial attacks graph neural networks via meta learning. In 7th International Conference on Learning Regresentations, TCLR 2019, New Orleans, LA, USA, May 6-9, 2019.
15

---

Published in Transactions on Machine Learning Research (October/ 2004)
A
Additional Preliminaries
For any matrices A and B, we denote trace(A" B) := (A, B). Given independent random variables E......,p and function f(5 Ep), we denote the conditional expectation of g with respect to & as [g. Ep).
Under Assumptions and we have the following properties (Lemma 2.1 and Lemma 2.2 Ghadimi Wang (2018) about in
Lemma 1. Consider and suppose Assumptions and hold. Then y(z) is Lipschitz continuous with Tng Cazy In addition, V is Lipschitz continuous with modulus L,f = (1)+C)aam + 1 + Ma
PG
OF [hay05
LagCan
where C == I.f2 + Le + +, ("eyce Lay
+
Lemma 2. Consider
and suppose Assumption holds.
Then for any I, it holds that
[(((z)) =- by y(x))) B G(z,y(()) Lipschitz continuous with modulus Ls Lag th
pG
(bag oly Car P2
Also, for any n, it holds that [J(y(z))l S My = Casx
Proof. By Lemma 2.1 of Ghadimi & Wang 2018 we have that
J(((x)) (V) G(x,,(a)))) ' G(x,())))
Thank to Lemma I and Assumption 2 it easy to see that 22 Glz y(x)) is Lipschitz continuous with modulus Loz + Lag Also, thanks to Lemma | and Assumption we know that V 2 G(r,(()))) is Lipschitz continuous with Lag + Ly Thus, for any 21 and T2, holds that
- -
<1 G(z1, G(E1,
-1 22 G(T,, G(a,, "2, ((2.222)))22)
+ (V G(xi, (((1),,((1)))))) V G(1z,
(V G(z2, (x2)) V2 ((22)
= Il (V G(z1, v(x))) G(,,,
V G(z2.((12)))
((V G(1,, (V
1/
V G(I2, ((22))((22))
= (V v(.1. ( G( (()))) (V
V2 Glzz. (
+ 2TV ((2))
< PG (Tog Log Iny) ||| x2هl प²²² Ta + Tuy (ny) Cazy |>| xz2l-
where ::= ( wy G(z v(r))) ( G(zy, (( G(z), (V2 Gla2. 8(x2))) -1 These together
with Assumption (ii) and (iii) gives the Lipschitz continuity of (y(x)).
On the other hand, using Assumption 2 and (ii), we have
[V((()))l (V G(r, " G(2, Caay
PG
B Proofs for results in Section Convergence Analysis for Algorithm 2
B.1 Proofs for Theorem
To prove Theorem D we give the following lemmas first.
Lemma 3. Consider and let Assumptions and hold. Let ((xt, v J')} be generated by Algorithm
Then, it holds that
[V - + < (2(1F)) + 4M3(LE)) (lv(x') - 4(CF5911(((())) 11+1
(12)
16

---

Published in Transactions on Machine Learning Research (October/ 2204)
Proof. First, using the chain rule, we have that
Vf(x') = V v()))( ((()) (,
This together with the definition of fx(")) in Algorithm
we have that
[V - ()(E))
+ = (J((())) (FF - v=F(r',(/t1) ( ,
(13)
< (2 11
For the first term in the above relation, have that
(vF( V.F(e' ( (1 y(2')11 ))
For the second term in 13 it holds that
Fld
V J(u(=)))
F(r. F(ad,
+ +211Ww())) |1) V 11
(14)
= (V ,(())) ( 12
+ - F(''', )/1
s
where the last inequality is thanks to Lemma and Assumptions and Combining the above incquality with 14 and 13
obtain that
|V/(x') - (
- s <1(4,2)911/11 - 022"))1 11 - 1 $ (2(1112) +4M3(12223) (1v(aa) - + ((C 11
Thus, the conclusion follows from the fact that |||||| S ||||| for any matrix A.
Lemma Consider 11 and let Assumptions and 2 hold. Let s > O. Let {( JJ)} be generated by
Algorithm 2 Then, it holds that
((J(((=))) - - s 6(1 Voy (Log + M33 (lu(60-1) - 8/12
+ +3(1 - v/ (22> Lāgg 27 Log Lig + >/a) 3 ||r1 - 112
(15)
+ +1 +1+ 5) - 7/6)) (6 - J3.
17

---

Published in Transactions on Machine Learning Research (ottober/202)
Proof. Using Step 4 of Algorithm 2 and the fact that J(y(z') J(y(z)))( VV G(x y Gy (()))))) we have that
((J(v(z))) - 11
S <1)](1(<))) -1 G(d -.t
(4)
1
3(1 + 5
+ 3311 2
+ 331 + 2
J( (T - vV Vv +1 x (J(((>!))) 1)) J4) (T ,V 1111
( 1
1 3(1+ + 8²
>>> (l(((()) w1p + 3(1+ )n² Mille - v(x)))2²
+ 33 + 2
1
13l1e - 1 - Vo 12
+ (1 + 8 I| (J((('-))) - J') ,v
))1??
where (a) uses the fact that ||a] + + +
+ass+aaa + aull < (1+ 1/2 Mla + a2 +
3(1+ } a1ll 12+
||a2|| + |aa| + (1 + x²) ||aa|l for any matrices {a), 022 03, as), (b) uses Assumption and Lemma 2
Using
Assumption the above inequality can be further passed to
([](((z))) - 12 s 3(1 + g²
1 ) Le ((x(())) - r'12 + +3(1 + ( n L M3llv' v(2')11
+ 3 + 3
(1 7 L3 11 - - 1p (1+ 5) - 7 (1J - J'11
1
33(1
(27² Logg + +2 Lay M3} |1 - y/12
1
+3 +
z)
(2 2 oz + 12 Mf T.y11ss - -
+ +31+
(1 )mG) 2L3 13112² - 211 + (1 + 5²) (110) - J-112
82
= -6(1 + g n² (Loz + M3y 11u(0' - -221
+ +3(1+ + )) ((2 Lozz + +27 L3y Lg + (1 233) || - 2''
1
+ +1 + (1 7P))
) ) [1)J(((x 111
where the last inequality uses Lemma Then the conclusion follows from the fact that ||||| S ||||| s for any matrix A.
|||||
Now we are ready to present the detailed version of Theorem 1
Theorem 4. Consider (1 and let Assumptions and hold. Suppose that F is bounded from below.
Let ((a', (aa',/..u JJ)} be generated by Algorithm 2 Let a (0, pa Denote Č == 2pc
+tao" Let dg > and
dy E (0, 10. 1). Denote 5 (1+ + d1 2). Let
and satisfies s² < Va(1-7po) 1. Let
s(Gg))
> 0 and satisfies > max
I <-6(44)) La +12g
Let (1 - 1)) uo
< Y <
min
5
Let 8 > 0 and satisfies
6(1 6(
12 1.2
Gay 1
Bi
4(Lf2)² + 8M3
(1- - 6(1 1 N (Lēg + M3
8 <1
(16)
18

---

Published in Transactions on Machine Learning Research (October/ 2024)
and
δ < S( (1 + 11++))ml - YmG))
(17)
Denole
C2 = (1 + (1+
(1 + 5/2 v Togy T 1zgg 12z+00 716)
1 +31+
Let A > 0 and suppose 3 is small enough such that
L Ar Ar 23-1
+025-4
(18)
2
Denole
H(r, N., J) = (x) + A| - + (1u(()) u11 + [I([(((()) -
Then 11' = (x xl-1, t/ 11+ is nonincreasing and
H S H' - Allz' -
112 6011/(1)) - 1
11.
(19)
Furthermore, there crists H such that (Hl+1} is convergent to H
Proof. Using Lemma we have that
Lif =1I't1 121
f(xlt1) ((x)))))))))
1411 - +
2
= =f(()) + (
22) +
1
| 221
23
(V/(x)) v/(65) x 11 - x4) Ls 881
| - x11
(6)
2 $1(' 1
1211 ||,lt1 2112 + (Vf(x') - ( xz()
Lg Ly- 9-1
11
23
2
= f((') + (V)(x') v)(x)), 1441 - z4) Toj
2
||, 1/112
2
S $((+)) + ? [VF((>)) - 4((2))2 + 4r -
+
||0 - x 1112
2
where (a) is because 1اا is minimizer of min, (V/(z)), x - sl)
+ $ || - xt whose objective is strongly
convex. Using
12 the above inequality can be further passed to
1(1111 S s(())) + T + 4r-22 28-1
10 1+1 - 22112
2
(20)
4(T1222 8M3
llx(x') - 112 + 8(C,)) ([((((+))) - J
On the other hand, recall that Ç -- Thanks to the assumption that ug we have that Č E (0, 1).
Thanks to Assumption 2 (i) and (ii), it is easy to show (see Theorem 29 of Beck (2017)) that for / 2 0,
Iy(=²) 122 < (1 (1lvv(a)) w'122
< (1 + (1 - ()1(((1)))) - n'11 )1 -1lx(()))))))) - s(x'-1)11?
(21)
< (1 dt) - -()1
(1+d, 21 - T 1ot - -11-111
- (1+ <1-1
< (1 -
111
19

---

Published in Transactions on Machine Learning Research (october/202))
where the third incquality follows from Lemma [ and the last inequality is because the definition of Ç.
Thanks to the assumption that dz E (0. 1-3 - 1), < E (0, 1).
Summing
20 15
with = +++ 1 and 21 with 1 - 1 1, we have that
f f(
(1xxxtt)) - 11 + [ (1)((()))) 1|
s {(x") + I + 4r 2 ||ااا| - =2112= + 4(L12)² + (L [lu((") - 112
2
r
+ 8(,))² [ - 1 1| + (1 - ())((())) 112 (1 + d )1
- x
+ 6(1 + 1 vnn? 2
12 + Logg M/3 [lu(x') - -1/21122
+ +3(1+ + 5 Vā (22 Logg + 227² Lgy Lig + (1 - - ||/| - -2011
1
(22)
+ (1 + ) (GG
- (1J](((()(()))
(x.)
11
f(x')+ [5 + 4r - 4
8(C +(1+ (iLL
102 |1 |12
2
r
[((LE))+ + (4(LF))+8M3 (L22
02 Wi? (Loz + Logh))3 (1((a')
1
+ (1- + 6(1+
-
where C2 = -1+ (13+ 7) 3(1 + v) (2>2Lag + +2 Lr L + (1- - [3
On the other hand, thanks to the assumption on 7, we have that Ç - 6(1 + v (Loz Using the assumption on r, we know that
2
C²
> 0.
"
4(L + LL + +1- +- 5z Vin² (Lay + L3y 1.
r
In addition, thanks to assumption on s and 7, we have < (1+ 8²) ) vTl1 7 < 1. Using the assumption on T, we know
8(CF)2
+(1+ +1++s)
1.
r
Therefore, there exists 8 E (0, 1) such that 16 and 17 holds.
Thus, using
16 and 17 (2 can be further passed to
f(z +1 + (1)(x - y/ 212 + [|[[((( - 11
T.f + 4r 4r-r2- 2 + +C2) ||alt|- 12'1 + (11((=))- - s/421/2 + II((((²)) - 1
s {((x))+ +
(23)
2
- -11)((z)) - -
1
Using 18 : the inequality 23 can be further passed to
2 f(xl+1)- + [1 +1) - 22 + (1((((((t)) -
5(xx²) A All2tt1 - 12 - 112 -
=f(z') - -||| 211
- 111 + - -/' - (1(()=)))((('')) J
- Aalaa' - 12- (1b((a)) 2 - o((J((())) - 11
Rearranging the above inequality obtain
Hl+1 = +1 + A - -
+ +1
12 + - -
< fax") + AlI-0 - - ||(('') , +|](((=')) - 11
AAlia' x² - -
= H' - A Alla -2--112-01l0a - 1
20

---

Published in Transactions on Machine Learning Research (ottober/202)
Since H' is nonincreasing, F is bounded from below and oo F(x', < H know that H is convergent.
B.2 Properties of the limits of the generated sequences
The following corollary states the detailed version Corollary
Corollary 2. Let assumptions in Theorem hold and suppose F is level-bounded. Then:
|| = O. In addition, the (1) oom |z/t1 - x'1l lim llx(x') - 1/ = oo [J(((z))) - | sequence f(d', y J(+])} is bounded.
(i) Any accumulation point x² of {x²} satisfies (x())) = 0. In addition, any accumalation point y² of {y'} is an optimal solution of the lower level problem in (1] defined with x².
Proof- Noting that (H(t+ ot , J(+2) is nonincreasing, we know that
F(x't1 u(x = f(xlt1)= s H' HH' <0.
Since is level-bounded, we have that ((att1,y(x" v(x(+|))) is bounded.
Summing 19 from = to N, we have that
N+1
N+1 Σ
N < - A
|
21112 1 8
-
112 - 8
((y(z))) JL+1
1=
1=0
t=0
Rearranging the above incquality, we have that
N+1
N+1
N+1
A
|
22112 +
+8
Σ
- 122 +
Σ
() - J < H N-1
1=0
1=0
1=
H
lim H'
co.
1-000
Taking the N in the above inequality to co, we have that limy || 1ot+1-af11
x'1| = 0, lim lly((*) - -//11|
and lim ||J [y(x))) J[+i||
This together with the boundedness of [(xtt], , g(x and the
continuity of (xx) and J(y())) w.r.t guaranteed by Lemma I and Lemma 2 have that (v') and (J+H)
are bounded.
For (ii), since llt1 is the minimizer of min, (ff(z'), - z1) + 29 1| 111 it holds that
0 (ol -2) = -c) vf(x)) - &f(x²)-
B 1(a - -x) vf(x').
1
Thus, using
12 we have that
IV < (V)()))
+((66)- + |latt1 -
1
s (2(1F)) 4433(1533) l1v(x*)) 1111112
- 1' + 3 g1alt1 2'll
(24)
< 2((FE + (MG(L)))))(())) +11 20 ()(x(z))) - | 1 ---1-111 x'11,
where the second inequality uses
12
21

---

Published in Transactions on Machine Learning Research (ettober/202)
Now let {(*2, } be the subsequence of {(2', (22, such that (im, (x", v²)). Using Lemma have that,
[VS('')I = lim |V & lim 2(112)2 + 4. (12,))())))) - -
+ 20y [J(((((1) - 5 || + 3 - - -1:11 =0
where the last equality uses (1). Thus Vf(**) = 0. Finally, let y" be an accumulation point of {1/}. Then, we have
lly" - v((xv()) = lim Ily" -y 1| + 111 - y(2')1) I1 + (1x((')) - y(*")1
s lim I1y y + Ily' y(x0)ll II Tyyl x²1l
where the second inequality use Lemma and the last equality uses (i). Therefore, have y² is solution of the lower level problem defined by z².
B.3 Proofs of Theorem
To prove Theorem first prove the following lemma.
Lemma Let assumplions in Corollary hold.
(i) Denote the set of accumulation points of {(xt x' ,/t,t, []+1]} , Q. Then Q is bounded and H is constant on f2
(ti) It holds that
dist(0, ( . o ((t1)
(25)
+ (2LF + 1)) |
/2 1'11
Proof. First, the boundedness f follows from Corollary 2 Now, (x", (x", "r, (J) be any point in Then there exists a sequence { (alh, -li- 1, 1/ J +I }r such that lim, x4:-2 ,,, ((+t] = (x* xx""""""" J*). Thanks to Lemmas and Lemma we have that H continuous. Thus,
H(x", xx" y J*) = lim H(' bb- / = H"
where the last inequality uses Theorem 4
Now we prove (it). Denoting Z (I, v. J) and using Corollary 10.9 of Rockafellar & Wets have that
(1998
H2, x', y, J) 2 8z Hx, x., y.
= (2f(x) + 8z A
|| - x' 1|2 + Oz (1)(2)) - y11 + {z((((((x)) - JIP
2
fx(x)
A(x x')
u3
(26)
A (a - x')
0
+
+
+
U2
,
where (Mz, wz) 0 l1) y/ and (ug, u4) E (|
J1 and the second equality uses
Proposition 10.5 Rockafellar & Wets (1998)
22

---

Published in Transactions on Machine Learning Research (October/ 2202)
Using the definition of regular subgradient, we have that
llv(x') v'11 - lly(()) - y/1 - ((u1, U2). (a', ,/) (x,, v)
0
liminf inf
(x,,)
11(x', 33) - (x,
(11x(10) - 1/1l + (1v((x) (1)((1((('')) - - 111((2)) -ll
lim
11x'',0) - (a,, v)1
((m1, w2), (2', (ar, v))
timsup
[1 v/ - (z,, 3)
(#' (x)))"" (1)-))))))))))))))))))))))))))))
(Ilx(2²) - 11 + (1v((a) ull (1l(())()))) - -// v(x) + vll
inm (e)))(a
[1 1/) (xr,))]
((u1, u2), (z', - (ac, v)) [1x2, ./) (ar,v)]
lim
(e' (r")))(( (())))
(1ly(1²) - 1/1l + 111v(x)) ull =l))((l((')))a/))))))) - v(x))] 11y s/ll) (xx',, - (x,
lim
(e' ("" (1)=()))>'
((u1, w2), (a', (xc, v))
sup
[1 .v) - (zz, v)
[lv(=') v(0))1 || - x:
1l v'1l 11 vl
(zl (aaa)) (f (11(22)) - 1/ll + |1v(x)) - vll) ((u1, U2), (/',))) - (z, v))
in
lim sup
[1 .vo - (x. v)ll
(x' (x)))) y ((r,))
lim (a (/) (1b((z)- - w'll + [1v(z) - vl1) (Ly + 1) ((u1, u2), (02),(())) (x', .30 - v)) [[x',, 33) v)l
This together with Lemma
gives
((u) U2), (z', (I, H)M [[(x', - (x, v)
lim sup 0 5 2(4 + 1)1b((x) - yll (ot.)) (z.3)
Thus, we deduce that [[(u uz)ll S 2(L, + 1))((r) vll. Similarly, we have that 11(4) S 2(Ls + ()(()(())) - J|r.. Combining two facts with 266 we have that
dist(0, 0H 0ist(0,0H(**++ (1 x², (4222,1+2))
||V + 11/ - 2'1l + 2(L 1)] (oalli--"" g/4211
+ 2(L, + 1) [Vv(2
11+2
s (2B)) + 4 ( 2 [2 +2051/(v((ttt) 11 }/2 |l 1lt1l
V2A - 2'1l 2(,, + 1111)((()))))))))))) 221 + 2(L, + 1) 1)]J(y((0+t)) - 1
(V2(LE)) + 413(1)5) 2(L, +1)) (1x(0(1)) - 1
(20, + 2[L 1))lJ(((o+t)) - J- + glb - - + v2 - 2'11.
where the second inequality uses 24
Now we are ready to prove Theorem
2
Proof. Denote z = ( -'11 ++ J(+1). Note that to show the convergence of ((x', ,/ J')}, it is sufficient to show the same convergence of {
We first show that { is convergent when H is KL. Suppose there exists i N4 such that H' H Then
thanks to Theorem 4 we know that Hi = H² ||//11 - at (lx(a)) - [[(((())) J(+1|| = 0 for all
23

---

Published in Transactions on Machine Learning Research (ottober/202)
12 I. This implics that {Z'-1} converges finitely to (x', x², (( Thus, in the rest of the proof, we only consider the case where H' > H" for all I.
Since H is a KL function and thanks to Lemma 5
H is constant on Ω2 using Lemma 6 of Bolte et al. (0014)
there exist e > 0 and a function o: [0, a) - [0, 00)
with (00) = 0 such that
(2( 11" distts 011 (z) 2
when Z E (Z: dist(2,9)) < fZ H < (Z) < H* + +.}. Since Q is the set of accumulation points of Z' we know that there exists 4 such that dist ( (2) < E when 1 2 4. In addition, using Theorem we
know that there cxists 12 such that H(z²) < H + when 2 l2 Thus, when 2 max(41, we have that
d'(U(Z)) H dist ())( 2
(27)
Using the concavity of o, it holds that
(0(11' 11")) 6(H -11') dist(0, (z)))
2 (H - -H dist 0H (Z))) -H'
(28)
H¹ -H!#1,
where the last inequality uses (27 and Theorem Now, we denote D = | x'-1|| D2
[1((z)
+1
Dj_ [[((((z))) - 1|,, A' Dj + D2 + D3. Combining these definitions with (28). 19 and
25
we
obtain that
min (A, (0,,),,((0c 8)(1)))3333)) (4 min
min ()(( (D)) (D2)3)
3A | - -x----1-- 1/ 3 - - 1| 3011J()(x))) 11
19
28
H' - H
á ((H - H³) - (H - H²)) dist(o, 2H(2'))
① (HH - H²) (H - -H+) D/ C1 D1t Dftt + v2ADi
1 B /2 (HH- (H)) (Hit1 -H') (Alt2 + A²) $ max E1 C,,
where Ci = 2( + 4M3(15)) + 2(y + 1) and Õ == 20 + 2(TTs + 1). Rearranging the above inequality and taking square root both sides, have that
mmxx(Cr (C,, J. v2A}
A411 + A
A' S
((H H²) - (H4+1 (H411-H1 -H+))
min(A,0) 8}
2
max(C1, C1, 3 /2A}
1 + A
@ ((H' - H*) -
min 5}
4
Rearranging the above inequality, we have that
H*) + max max(C1,, C1, [2 ((H' H²) (H (H"41-H
1 A' <
1 (A' A4t1).
(29)
2
Summing the above inequality from any 1 12 max(41, (2) +2 and recalling H' is convergence to H" given by Thcorem 4 we obtain that
x Σ
max(C1, C₁, 1, v21}
<
min ( (A,)) 8} 6(H H²) 2 1l xo,
(30)
24

---

Published in Transactions on Machine Learning Research (ettober/202)
Thanks to the Lipschitz contimuity of y(z) and [(((z)) guaranteed by Lemmas | and 2 we have that
1( y¹, J²) (x' , = Σ (1 - -'11 || + l1 - 80-11 1| - (1F)
1=1
(D} + D2-1 + D/- + (1y((='1)) y(55~2)) D2-1 D'- 1| - -J
1-]
(31)
Σ
(D) + D1-1 + D2= + D. + +D'S D'2 +LDD
1=]
5max{1, Lays Fin
Σ
34' 2A1-1 + Al-2 <00
where the last inequality uses convergent.
30
This inequality implies that the sequence 8 J')} and {2'} are
Now, we show the convergence rale when H is a KL function with exponent 0. First, when 1 0. there exists 7 such that H' == H when 1 2 I. In fact, suppose to the contrary that H' > H* for some 1 > L. Since Z is convergent (denote lim; Z -*) and H' is nonincreasing thanks to Theorem 4 noting that <(s) and the KL inequality holds for large I, it holds that dist(0, (z)))) 2 : contradicting (25p. Thus, there exists such that H' == H' when 1 > I and recalling the arguments in the beginning of this theorem, we have } converges finitely.
Finally, we consider the case where 0 E (0, 1) and H' > H for all I. Denote B' = Ekst A which is well defined thanks to 31.. Then, for any 1 > using (9
B' 2 max Õi, t. /2A} min(A,0] 0,
(1H* H²) (Hh+1- - -H*)
1
Σ (A* - ARt!)
2 k=l-2
l=
2 max max(Ci. Č1, 1 V
3. min ( (A
1b -H*) + 2 al
max((C, Ć1 3: ]
(bHH' -H*) + 2 [Bl - -B'-1)
min (A
max Č1, 1
3: ]
(bH H²) + 1 (B1-2 B')
2 min ( AA,)) 8}
Now, following the classical steps for analyzing the convergence rate under the KL assumptions see (Attouch
et al.
2010;; Attouch & Bolte (2009 ; Liu et al. (2019) Wen et al. (2018) for examples, we have
(i) B converges linearly when (0, []-
(ii) B' convergence sublincarly when 1).
This together with
- (x", ""","","'""
Σ
[1 ( (x'-1, (-,1,-1,,
1=1
< mmxx11,
Σ
3A' + +24!-1 + 1t-2
1-1
3B 24! + Al-2)
maxx M,, L,} LybBl-2
25

---

Published in Transactions on Machine Learning Research (October/200 2004))
guaranteed by the convergence of ((xh, ( Ji) and 31 we obtain the same convergence rate of (et, 3 J4) as Bd. This completes the proof.
]
B.4 Details of results in Section Convergence Analysis for Algorithms
Lemma 6. Consider 11p and suppose Assumptions
1 and hold. Let (('', be generated by algorithm
3. Denote Čo == po-2c " with (0. vz) ( +
Denote So
(1 o (1 (o) with dy. E (0, v 1
1-c, 1))
Suppose a < "La" Let x = x. and pick anylu u 1) _ lk" and {o=2, 10-2,001 1- s R Let s-1 S-,, B-1
and B-2 be any sample batches. Then So E (0, and for any 1 2 0,
ERillt - y(("))1 s (1 - -1
1/1
2c-2
(32)
+ (1+ + dr. ER) - 112
0
2
+ 20
or equivalently,
E R (1v(((11)) - 8/112
(E 1 (1v((=-1) 8/11² - E Re 1 2²()))
(33)
(1+ dz,)) 21 - (s)
20
I RR || - x 112 +
og.
Se
So 2 + 2a
Proof. Thanks to Assumption 2
for 1 2 0, we have that
La 11 - -/113
G(dl,//t) S ( (') -2)
8²) +
2
-G 2a |1, - -121?2
LG
1
[VVC) 3²) +
11 - 1/
2
s ( v/) + (1y(2() ) - y/112
lIv(o - 1/1
2a
2a
LG
1
-/) (, < (,
*1y y/112
2
1
+
11y( - 112
ly((²*) -
2a
2a
2 |v
LG
26 222 y/ + 2
1 y/112
where the second inequality is because 4ا in Step 3 of Algorithm is the minimizer of arg min G(z!, s²) + (V,G(a', . D', 1-+1-g') -²) + 2a modulus 1. Taking the conditional expectation of S on both sides of the above inequality and recalling Assumption for 2 O, we have that
- - and the objective of this subproblem is strongly convex with
Esq GG(x' glt S G(x., v/) + (V, ))))(()))) v') (ly((a) 3/112
1 2a
-Es
1
|1)(²') - - 11 + 2 + 26 lx(d)) - s'll
20
Lo
+ Esyne-
||//=1 -1 1
< G( ,1(x))
PG (1)(2') -
+1 1|
|l - 1/11--BB Esy
1
"ly((')) - 112
2
2a
2ax
2
Lo
+ σ²
00 + 26 202111(z²)= - 3'll -s
a
|1 1+ 11,
2
26

---

Published in Transactions on Machine Learning Research (ottober/202)
where the second incquality uses the strong convexity of G(x, .). Rearranging the above inequality, for 1 2 0, it holds that
1g (G(a', +1) G(xl, (((x)(())))) - - PG
2 llu(=') - 1/122 1
(ll((a)) -/111
2a -Esy ||y(x') - 112 + 200 + 20 l1x(t) - s'll
1
(34)
2a
LG
+ |
|1y 1+1 -
Since G(x,,)) is strongly convex with modulus pa and y(1²) is arg have
argmin, min, G(rt, v) by definition, for / 2 0, we
PG |1 - y( s Esy ( (1) G(r ,v((')))
Eg R
2
S
|,)(²1) )- y/122+ + 2a
lly('') - 3/11 + 26² 1bb(z)) -''ll
-gsy 11
- |lu(x') - 111+1112+ +
1
200 + Es
2
La 1
"
"1 - y 1|2
2a
2
MG (ly((')) 1/12
[lı(e') - 8/112 -- + 20²
1
- -1p--sspp mi
1
- 1/1111 1
2 0² σ
2a
2a
where the second inequality uses [34] and the third inequality is because the assumption that LG _/ < 0.
Rearranging the above incquality and dividing both sides with Ma
+
1 for 2 0, we obtain that 2a
2
2
Esq +lly y(2')1)² s (1 - (1))(=)))())) r/12²
o
2 2a
where 3,
2c- + + mr
E (0, 1) thanks to the assumption that 0 <<<
and a < ia" Now taking the 2
expectation on {R' } on both sides, for I 2 O, we have that
2
E +1 222 S (1 - R - llv(a*) - 1/11 +
0
c2
+ 20
s (1 + &2 (11
(1)(==)) 1/1 + (1 + d (1
(1y(")))))) -y(""")11
2
+ (
Ha 1
dG
2n
$ (1 + (y,) (11 - DIER--lll(='- 11 + (1 dz (1 Re) L2 2'' 111
2
2 2 + 1) d6
Za
= (1 - ( ft (11((*-1)) 1/ 12 + +1 + +,, 2. F 1. - -x 112
+ (2G 2n 2
where the third incquality uses Lemma I and the last inoquality uses the definition of G. Thanks to the assumption that dz < <
1, we have that 0 <<C So 1.
Rearranging the above incquality, we have that
ER--1 (1 s/112 - 5. (B 1o(a' - -1112
1
E 11 41
v(x')) 12) +
1 + 2 No (1- (o) E ||ad - 111 +
1
2
+
0
6o
So
2
+
27

---

Published in Transactions on Machine Learning Research (october/202))
Next estimate Zz v/) and V Gy vf). We first present the following basic properties shown in Nesterov & Spokoiny (2017), see equation (21), Lemma 3 and Lemma 5 in Nesterov & Spokoiny (2017) respectively.
Lemma 7. Let h Rn + a differentiable function with L-pischhttz gradient. Define hx(z) Eu [h( pu)), where f > 0 and u is standard Gaussian random vector. We have that:
(i) h4 is differentiable and (zy(z) = E. Vh(z, u), where Vh(I, u) A(*+ h(z) U.
(8) (V))(x)) Vh(=))1 L(n L +
(tii) B. 5h(z, || - 4nn
Now we bound nabla V Vay G and G. Lemma 8. Consider and let Assumptions Denote
and hold. Let ((a', be generated by Algorithm
2m Q²
(20² + 4Q((4n 15)) 4 (n+(n+3) 6Qp² 6Qn2 (n + 4)$
1dd
A my
+ oz
8(4n + 15)
and
2m
(2Q²² + +QQ(4m + +1)) n²
Lo (m +3) 66Q22 Lay (m 2)3²)
Q2
4
Caw + o
+ 4(4m + 15)
Q
Then it holds that
Bu - o')))) s 2202 + Auy
and
E G(z E be G( "' S²)2 & 20 + Auy for G(z'
Proof. Thanks to Assumption
3 holds that
E Ar
G(rl . v/) Gee,
< 2E ra V G( 3¹) V s/
(35)
+ 2E RM V
s') G :
s 20 2E IV G(r s: v ,. "' SR
By the definition of V G(z J S and A Gir v¹), we have that
B R
V G( . A. G(z 11
|s'1
V G(d (1 1
E al
R
S
Q
8
1=1
101
1 Q j=1
Q
(36)
E. RR
V G(
8
u
S
v1
1=1
Q4
VV VVs.
28

---

Published in Transactions on Machine Learning Research (October/ 2024)
where (65) are the elements in S¹. Denoting
V G(Z,Vi:E)) == E,yy 10 Vi G(æ + pat v':)).
we have that,
Q
V.. G( + palf v'E55) G(', u/
E, B
Σ
V VV, G(..G(t).
2
V V
2
SW
G(x' + v' V v
+ 2
V.(V G(d,)())))
u/
(37)
2Q Σ
V 3/ -
/=1
2
G + pnl, v' - V.. g(x'.g'
V G(d G(F.
+ 2F
"1
For the first term in the above incquality, using Lemma 7 (ii) together with Assumption (i), we have that
(V G( / 1 Log + +33
V VZ y. G(a . v3)
(38)
For the second term in 37
denote
Vg, + pul, v/:55) - vn, G(dd,s/:55) (u))
r3 ;= = (V G( v/
Then we have
V., G(d + pnl, v': - V G(xl, v1:
31 ((.l.//:))))))
(39)
Vn, G(od + uu vl - V, G( 1
2
V v G(dl, v(gg)) U4
u
+2 Σ
(Tans
Thanks to Lemma
(i) and that w/, and w/, are independent, we have that
Egg ia 180 Σ
(1)) 0, j1 + jz.
29

---

Published in Transactions on Machine Learning Research (October/ 2024)
Thus, taking expectation of u', 39 can be further passed to
G(x + pun v'EE) - Vy. G(rl, (
B
V P ((cl,)'33))
G(dl
1
Q
V ( G(2* g')43)) V., G( + mut, y :Es) V., G(xl, v':53)
E Bugl
1=1
V Vy, G(x + mul, )': Vu, G(x',
2
Bug /
u/
-IV G a('''
11
(4(n + [,
3,22 (o - G(
(40)
Σ
(4m + 15) V ( 3/ G( (m
(2(4n + 15) C (( Σ j=1
2(4n + 15) VV
Σ 3p L (n + 4)²
( Log (n ( +2(4n+ 15) (V. (2))) +3p Lay (n =))
224n + 15)
4
where (a) is because E.jl Vz(V% G(d, v':E)) Glr' (, s/ Vy, G(a'+ v/ -V,, G(z', w w(ich) u/y (b) uses Lemma 7 (iii) and the last inequality uses Lemma
uf is the variance of
(ii) and
Assumption
Now, combining
37
38
and 40 we have that
G. + mul, v': - V, Glal.'':ssa
E B
Σ
Vz(V in G(L
8=1
< <2Q)
Q Σ
(n+ + 3)3 +2 Σ 2(4n + 15)
[ 4
Lô 3)3
4
j=1
Q
+2
2(4n + 15) Σ
(V 21 G(v / =5 +2
3p2 L2g (n + 4)3 j=l
1=1
= =(2Q² + 4Q(4n + +1)) म (n
+ 6Q 33) Lg (n + 4)3
4
+ +4Q(4n + 15) (. G( ((..)/)))) |
30

---

Published in Transactions on Machine Learning Research (October/ 2024)
This together with 366 gives
Buy ie Vay my G(x' Gal, s': - G,, (''
Is'
Is m
(2Q² 4Q(4n + 15)) x²
4 L'gg (m +33 +
Σ
Σ
6Qp2Ioz Log (n + 4)
|s'|02
|S/102
1Q /
S Q2
(2Q² + 4Q(4n + 15)) /
S
m
4 (n +
m
Σ
6Qp 2 G (n + 4)
S
r=1
Is'
+ 4(4n + 15)
V
G( /
1
r=1
Taking the conditional expextion of S on both side of the above inequality, recalling Assumption (i) and Assumption 3 we have that
En', S4 1 2
Ca, 8')12
S m
(20 40Q + 15)) 4¹ Log 3)3 + 6Qp Log (n + 4)²
Q²
Oany + ob 1(4n + 15).
This together with 35
we have
But,,t s'|ns' n 1 VV, w²) ((')
2m
(2Q² + 4Q(4n + 15)) H²
$ 20 2 xy
+
4 Lāg (n + +)²² + 6Qp² L2g +6Qu2Log + 4)0)
Q2
Bany
+ 2
8(4n + 15).
Q
In the same way, can calculate that
Eu A
V
G(o', w/) - G(o', .id..''' S')
20, nv +
2m
(20² + +4(44m + 15)) 1et
Loy(m + 3)3 6Qpp2pp Loy (m + 2)²)
Q
C2 Ogy + +
+ 4(4m + 15)
Q
Next we bound of [[](((z))) 12.
Lemma 9. Assume assumptions in Lemma hold. Denote T 1- (1 + c3) + +G)(1 - 72G)2 with dy (0, --- - 1) and cJ (0, V ()(1+d)))) - -1 ((1 + + + 6(1 + (1 d Gy M3) T.g Denote C. := 4(111+02) T 6(1+c))(+d7)) M3. Let 70, Then, E (0,1) and it holds that
1). Suppose 7 E (0, V pG Denote C2 = 3(1 +
[R(J(((( 11 < 2 |1y v'1 CC7 P -0
(41)
+ +A + (1 E) ( - 31112 + A
31

---

Published in Transactions on Machine Learning Research (october/202))
where Aи = 2(11+c (202g + Auy) and AL == 6(1+ d_2 (20 + Av) M3 when
and V G (() are generated by (ii) of Step 4 of Algorithm 3 Y < W with W = 6(1 + cG)(1 + dr²) + Agy)
Proof. First, using the facts that [y((')) -7 - Vay ((())) and jut
j vg ,v G(st, we have that
[ - 1
((e.))() s ((++ -(ys"" J 22 $21+,7)7711,,G((((( - V,,
J 71 12
+ +2(1+ 2,,+,,))" +,
(42)
+ (1++)) Go J -1- VV- (/)) 1?
(
S 2( + + lo((') 1/ 2 G(zl ./) - G(='""=')')
+ (1 G( v(z)))) J (1 - - G(t' 12:
where (a) is thanks to Assumption
(ii). Note that
,,, (1- 1|2
3r
- -V, ((, M(y(e') ()(1 -1
-
-i -III--V -V G(dd / 2/12
j (1 (1- -
1|
< |t,p:://w_000ttldd0oo__oo/_//va0
+ -3 J(y(('
+(+:]))l--Vnn(((::]] -) 111
+3(1 +, V Gld (0000))'''''/0 111381111.
where the first incquality uses ||ا + 02 + 04 (1 d2) (1 + d ||a + as + a S (1 + +d)d)
3(1 | + 3(1+ 12 Using Assumption 2 (ii), the above inequality can be
further passed to
- Jr -1 (1 1|2
< 33 -
+3(1 -3L-- ((
(1 R'12
(43)
+ +3(1 --
< 331 [11--3))"((a0///0--------10-0111 y161111~u)))100000 2 - -21112
+11 + (1+ |,
G(x )
where the second inequality follows from Assumption 2 (iii) and Lemma
32

---

Published in Transactions on Machine Learning Research (ottober/202)
Plugging
43 into
42
we have that
-2 s/
h=tp::/hhhh........//////aaaa1ar + -0+-))1-+00111--==000000000011)-
+ - 111
$ (41+=)))(( ?² (11((=11)) - 8/12
+ +1 72 (1y((===1)) --(0)11111
+ ( - 1
+=1-=,))/lVV((((t::----CCCCCC, 6'112
+ 11 +
3
+ (1
Gr 11)11
Using Lemma
1 the above inequality can be further passed to
[|](v(z))) - 11
$ (4 (2(1((x 2
+ +(0==))((
1 1 221
+ (()+
= + ('11111
+ +3 G(y (1
+) -
(44)
<
-| -21-111
G(z )1 -,,
(, (1- -11
121
+ - -
2gy 2211)(2²* 22
+ "( V G(x', )12
+ -1-7+601+ + G(z' - G(d / (013"//))1111100000===)01 - J012
+ +6(1
- Glx' of / )1
where the equality uses the definitions of and C.. Note that the assumptions on c,, d, and y give that (0, 1). Now we show that A satisfics
E
51 A1
(45)
Using Lemma we have that
Eu < 1 ---
+ =1 51-4
33

---

Published in Transactions on Machine Learning Research (October/ 2004)
where the equality uses the definition of W and the second uses the assumption that / W.
Therefore,
450
holds. Combining
45 with we obtain
E By St | (1))(((((xx))))))))))))))
< (4(1 + c + (1 dj og M3) "'1 -cnpll/-
+ +(11 + oj , W. V ,,,, G(r', V.y ,1122
+ + (1- ()) 11
Go (()) 1) + + +5)(+++ dj 1,, w n 1 Go -
< (1(1 (11+)c7) + 6(1 +11+ 7 - C,, 7 -
+ Aи + (1 - 1)
+ AL,
where the last inequality uses Assumption 2 (i), Lemma and the definition of Ah and A
Taking expectation both side with R' obtain
Eg ([(([(()))) j 1|2 = Eg E af (1 -
112
22 1)) +C 111 -| 11 + AH + (1 F. m [1 3'112 AL
$ (1(1+ (72) + +(1++ (L
Before showing the details of Thcorem 3 We first give the following lemma that estimates the error between f and (zx'). Lemma 10. Suppose assumptions in Lemmas and hold. Then it holds that
E
- -
160 + 16(05)2 Cur²) Bee Be lu((())) - 222
4( + 4M3((155)
1603 + +6(C,))
Be 2211
160 + 16(C,))
160 + 16(C,)) A
(Ax AL) + (4+ OM
6
where A = Ese [[](v(=!)) - f+1 12 E [[( - f242112
Proof. First, using chain rule we have that
vf(a') VaF(a' v(=')) (((((d))
This together with the definition of fxx),, we have that
Ex [V f1122)1
< R V F v(=))) - V.F(1', (1;
(46)
2 I (wd V Fat v(>1)) (
For the first term in (46). we have that
ER V F(r v(x1)) V F(x,, . ++, B
2E Rell FG. -( ((F'))-vVF(F'' || 21 E. 1
-
(47)
< 2( 2 1
34

---

Published in Transactions on Machine Learning Research (October/ 2002)
where the last inequality uses Assumptions (1) and 3
For the second term in (46 it holds that
+ 2r (1tr)(((('))) - J(
s (1l()\((((>))) V,, - V
+
+ 14gp
2E <
+ " 
+ 4E +. +,
(a) S 2 (,
+ 4E - //
(48)
+ 4E 1 -+
(b)
< 2 "1
+ huw.:///wwwaaa//////////////1/11
+ +4E -. +
(0)
I ( (
+ - -
<
( - +
+ ( + 2(C,) )2),
where (a) is thanks to Assumptions 1 and 3 (b) is thanks to Assumption |
(c) uses assumption and the
last inequality is thanks to Lemma 2
Now using Lemma and the definition of A 48 can be further passed to
E
80 + +8C5))
S 2M (1x(d)) -112 44M30 +
Eyt - 12
803 +8(C)) 11
8 8(FF)
8 + (3
211 +
(A + AL).
v
35

---

Published in Transactions on Machine Learning Research (October/ 20244)
Combining this with
46 and
47
have that
E (x)(() {(
-
< (
11 40 + 4M3 2 - 12+ 8
1 )) C22 R (1)((=)) 1/1 160 + )6( 1 -
1 + ))
160 + ))( A
(AH AE)
4 160 + 16(C,)) Cy7²1 E
(((LE)) + AM3((222
- -
1 + 12(
C2 Brol|oott1 - x21?
B + ))(
1 + ))
A +
(An + A1) + +40 + -87308.
Now we the details of Theorem
Theorem 5. Suppose assumptions in Lemmas 0 and 9 hold. Denote
1
80 + 8(
D2 23
8
CzT
2
and
3 4(TT2) +4M3(12222
16 B + 16(
Dy =
Cos2
2
(L(d,))),((LEE)
Suppose B is small enough such that D2
1 > 0. Then
1
1 2
N N+18 (1(29) - (2
N
1=0
1
2D,
2(80 + 8(C))))
(6)+
N +1
1
2D, y
2c 2
1 2 + +8(C))2
00 +
| - -
N +11- G
[C 2a
N+1
N 2 16 16(CF)2
4D,c
(AH + AL) + 40 + +8
+
Pg 0
+1
C
2a
Proof. Thanks to Lemma
we have that
+ (V)(2'), 0/ - x²) + Ly
2 f(x))) {(
|10 - =2'12
2
= =f(x)) - (Vf(='), 7f('') + Lg -|/0t|1 - 22112
2
= -(x²) - 8 (+ 2 + 1
-
- 1
- - +
+ Ls
|| - x21?
2
= =s(x') 3 3/ - 45(2))1++ + (
1
1
23
36

---

Published in Transactions on Machine Learning Research (october/222/)
where the first equality and last equality use Step 7 of Algorithm that
3
Taking expectation w.r. R², we have
ER
(1ltt)
-
2 - + Ex 2
((V)((²)) -$5('))1
1
+
E
| - x!112
2
2
Using Lemma
10 the above inequality can be further passed to
E s Egi (f(²) 2 = |[Vf((()12
160 )6(
1(( + 4M3(L222
Gyr²) ) E -
+ 2
8 + {3
8
C2 C2 B ||| =211
B B
+ )(C
A (80 +8(C))3)
+ 3
(An + + 8M3)
Ls
1
+
BR |||l|1 - 1²1
2
2/
E f(x²)
1
V V/ )11 + D (ly((())) - g/t1/1 -
||a/t1 x2'1
1/12
2
+ 8 8 + )2
(80 + )9 A
(AH + AL) + +2 4M3)308
6 where the last inequality uses the definition of Da and Dy- Using (33 the above inequality can be further passed to
Ee f S En f1 1 9p
Dy ( Eaiiall''2 -0(00' 1113)
C
+ (1+ dr,7) Dz -66)
Dy
20 2
12 || - x112 +
I 0g - -D Ilod - 121
2n
80% + 1
Al (80 + +(C,5)))8
+ B
(A + Ar) + (2 + 1M3),80'
1
+ Dy (Ea)l - 4 12 E iu+ 11y 12 - y/(l+11111
ER- fxx")
= B (
(D.- (1+ ye D2 (1 - Go) (1- 13) ER 11:11/1111000 -/11 D, 2c
0G
16 + 2a 2
+ B 80f + 8(C,)2
(807 + 8(C
(A + A2) + (2 + 4M3)
Thanks to the assumption that B is small enough such that D2- (1 L3 2 O, the above inequality can be further passod to
ER E (1 S ER-
| D, 80 + 8(
2 g-
- - -E Eg4+=
- v(a(+1)112)
c.
+ Dy -
A + (8o 8(C
+ I 2 + B
(An + +A.)) + (2 (2+4433883
37

---

Published in Transactions on Machine Learning Research (October/ 2202)
Rearranging the above inequality, it holds that
Er =[[ff(z()1 - 2 3 (Ln ff(²) - Ex f(alt))) + 3 + )(
2D (B -BR 11l/ 3(xl )1
112
+
Ca3
A' + 1 1)(
4D yc
(AH + AL) + 4 + 8M308 +
y 0 G
"o
2a
Taking expectation on R' and R', we have that
2D (Bl1y(z)) - 112 Elly/t2 y(1(+1))13)
B| - 3
(Bf(d))- - E)(x +
SaB
+ 2 - 8(C
A + 1 + 1)(
(An + AL) + 40 + +MM300 +
uc
-0-
+ 2a
2
Summing the above incquality from 1= 0 to N, we have that
N
2D (Blu(z2) - y²112 E11 - =(a (12)
E [)
- 3 Ef(x*+1)) +
SoB
1=0
1 + 16(
- - -1 -
- (242112)
160 B + 16(C,))
(N + 1)
(A# + + + 1)03 + +8(N + 1)M330
++1 4D,c 2
5. "G" + $ G
(49)
2 (J(x))
- -B((x++
+ 2D y -
<
B
1602 + 1)(C,)) E]J(y(z²)) J21
1602 + 1)(C,))
+ (N + 1)
(An + Ar) + 4(N + +100% +8NN + +1M330%
N ++1 1
4D,c
2 + B G
6
MgB
-1 -2 ,...,, u be any vectors in R Now we define x = x = xd and yー = y0. Let {ur ....,,. .. "1
and {uT ,..., ² 11 (5²) be any vectors R. Tet --1,5 2,,,,11,111 1-1,,-2,B-1,, B- be full batches. Then since fa-1, x 2 are deterministic, using 41 using Lemma 1 we have that
f )12 [V )12 < (C,5)
Using this together, 41 with ( 1 and the fact that x = x and y 1 y0, we have that
El|{(((=")) - 12 < (c,)) + 2(80 + 8(CF)9) (Cv)2) |1 "1 - 12 E v 1)122+ 2(S0 + )() ' 8(203 + 2(C (1 - :)
BIJJ(((z - 10 2(8o + +((()))
(An AL) i
< <(yy)²+ 2(80g + 8(C,)))
(Cg12) ||v(x - 1
2(807 + 8(C,))
[](((x - 1 2(80 + 8(C))))
(AH + AL),
38

---

Published in Transactions on Machine Learning Research (ottober/202))
where the last inequality follows from the fact that (0,1) and the fact that jo is deterministic. This implies
2(80 + )2) B ())((())) = (c,))+ + 2(80 + 99
s
(G27²) (1b(xx -
(50)
2 + +8C,)) A-1 2 + +8()
(A + At).
On the other hand, using 32 it holds that
2c 2
Elyy' - 2() < (1 - (.)l (1+
x2-1112 +
(51)
PC
20
Sum
50
51
and
49
we have that
B || < 3 - ( B1(x
2
3
1=0
2Dy
2c-²
C (1 (1- !) 11 (1 56) -2001----
=0-112+
(M4 + 1 0G
2n
+ (C,)) 2(80) + (
(Cg,²) |10(x=1) - 2(80 + }3)
2(80 + )3)
A +
(An + At)
+ (N +1 2 ))(()))
++ 4D,c²² 2
(Anr + Ar) + 4(N + 110 + 8NN - 1)M +
PGB 2
+ 3 GG
2n
Since f is lower bounded by x-, x² and A-1 = -1][((<>1)) j by the definition of A in Lemma 10 the above inequality can be further passed to
2Dy B {( S 2 (((x9)-))
(1 (1))))l - 11 +
2c
G
(46
0
2a
+ (0,)2+ 2(80 (9)
(C,,?) [1x(2)) - 11 2(80 + ((C,))3
|| ((l(x==))= - 10
160 B + ))( (N 2)
N+1
4D,c
(An + Ar) 4(N 1)03 8(N + 1)M3o3
B OG.
C
PG3
+
2
2a
Dividing the above inequality on both sides by N + 1, and rearranging terms, we obtain
1
1 2 (f(x9) -f + (z
N
N
1
2Dy (1 -6)++ +
2(80 + 8(CF)2)
C,7T²
(u(=")--'11
N +1
G.
1
2D
y
22
2 +
1
2(8 + +8(()))
| - 10
00
++1
G
+
N+1
2
2a
N 2 1
+ 16(CF)
2
40,c
(An + Ar.) + 40 + 48
N +1
+
C
AgB
+ GG
2
2a
39

---

Published in Transactions on Machine Learning Research (October/ 2024)
C
Additional Experimental Details
The code is available in a anonymous way at http::/aaaoonoossoooo..dcc///ccd formulation of the hyper-representation task is as follows:
The
min mat (A, w² (A)) El (A, wn (A)):
E
[((W3)* ((=;; A).
Dvve
s.t. w (A) = arg min ler (2, w) = |Dr.gl (
Σ
I(w o(z;;A) vi) + C/
where ((-) denotes the cross entropy loss, D and Dy. are training and validation dataset for a randomly sampled meta task. Here {Ai are ixper-represenatioon and C 2 0 is tuning parameter gaurantee the inner problem to be strongly convex. In experiment, we set C 0.01.
The Omniglot dataset includes 1623 characters from 50 different alphabets and each character consists of 20 samples. We follow the experimental protocols of Vinyals et al. (2016) to to divide the alphabets to train/val aoain/vaiiatton/teen
with 33/5/12, respectively. We perform W-way--Kshhe classification, more specifically, for each task, we randomly sample characters from the alphabet over that client and for each character, we sample K samples for training and 15 samples for validation. We augment. the characters by performing rotation operations ( multipliers of 90 degrees). We use a 4-layer convolutional neural networks and each convolutional layer has 64 filters of 3x3 and is followed by batch-normalizztioon layers Finn et al. (2017b). The parameters of convolutional layers are treated as ryper-representttiion and the last linear layer is the fined tune inner parameters. For all experiments, we use mini-batch size 4, outer learning rate 0.1, inner learning rate 0.4, perform 4 inner gradient steps. In particular, for F2SA, we set the Lagrange multiplier as 2.
40


Reviews:
[{"review_id": "HBEgmhzSR7", "reviewer": "Reviewer_HiMK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors propose a new Jacobian approximation method that works in the bi-level optimization at least for the experiments the authors provide.\n\n2. The proposed algorithm has a convergence guarantee that the algorithm can converge to the neighborhood of the solution.\n\nWeaknesses:\n1. Some claims in the paper may not be correct.\n    \n    (i) In the introduction when the authors introduce the Neumann series, the claim says that the larger b is, the less error this approximation has. However, although the difference from the expected value of the approximation to the real inverse will be small, since p is randomly sampled from $\\{1,2,\\cdots,b\\}$, the variance of the approximation will increase. The error will not decrease when the variance error dominates the approximation error, especially for large b.\n\n   (ii) For the definition of ITD, I don't think that  Ghadimi & Wang, 2018, Ji et al. (2021) or even the proposed method belong to the ITD. ITD means using the differentiation among the iterates of y while these methods are based on the implicit function that tells to use Jacobian.\n\n   (iii) I don't understand why computing $J^{t+1}\\nabla_y F(x^l,y^{l+1})$ needs $O(l^2)$ HVMs. It seems that by knowing $J^{l-1}$ only 1 HVM is needed.\n\n2. The experiments should include the comparison with [1], a fully first-order method for bi-level optimization. Moreover, what's the dimension of w in the experiment？\n\n3. Theorem 1 and 2 seem to be meaningless. Instead of sequence converging, it is more important to show where the sequence converges. Algorithm 2 should have a convergence analysis like Theorem 3.\n\n4. Theorem 3 does not clearly state the algorithm whether it includes Guassian sampling or not.\n\n5. Some assumptions are redundant. For example when F is $L_F$ Lipschitz, $\\|\\nabla_y F(x,y)\\| \\leq L_F$ automatically.\n\n6. Does Equation (8) relate to the algorithm? According to the proof, it seems that the gradient and Hessian related to $x^k,y^k$ should be calculated with batch $S^k$ instead of $S^l$.\n\n7. For remark 1, it seems that when Q>1, we should use direct computation instead of the Gaussian technique, which degrades the contribution of introducing this technique.\n \n[1] Kwon, Jeongyeol, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. \"A fully first-order method for stochastic bilevel optimization.\" In International Conference on Machine Learning, pp. 18083-18113. PMLR, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a new method to calculate the Jacobian matrix for bi-level optimization problems, which involves historical accumulation and random finite-difference approximation. The authors prove that under KL condition the proposed stochastic algorithm converges to the neighbor of the first-order stationary point. The experiments show the improvement of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.  Solve weaknesses or correct me if there is some misunderstanding, especially for 1,2,3,6 and 7.\n\n2. The authors have to go through to correct typos besides the following:\n     \n    (i) Page 4 we denote $\\nabla_x F(x,y)$..... $\\frac{\\partial F(x,y)}{\\partial y}$. It should be $\\frac{\\partial F(x,y)}{\\partial x}$.\n\n    (ii) At the beginning of Section 6.1. \"We first give a decent lemma\" and the following is Theorem 1.\n\n    (iii) In Definition 1, $dist(0,\\partial f(x)) \\geq \\cdots$, a right bracket is missing.\n\n    (iv) In Theorem 3, what is the definition of $\\bar{\\nabla}$?\n\n    (v) The problem formulation in Experiments, both $w^*_\\lambda$ and $w^*(\\lambda)$ are used.\n\n    (vi) Page 16, the last but the second line of the first inequality part, there is a redundant $||$.\n\n    (vii) Section B.4 there is a strange F.", "broader_impact_concerns": "I don't have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uEl8LFxNWk", "reviewer": "Reviewer_XGse", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The setup is clear\n- The assumptions are well-stated\n- The results have the potential to be interesting\n- It was tested numerically.\n\n# Weaknesses\n- Theorem 3 is incorrect, as we will demonstrate below with a counterexample.\n- Theorem 2 appears to be plausible, but it relies on an uncheckable KL assumption,which makes the contribution dubious.  \n- The writing is sloppy.\n\n## A counterexample for Theorem 3\n\nLet $x$ and $y$ be scalars. Consider the functions\n\\begin{align*}\nF(x,y;\\xi)&=F(x,y)=cx\\\\\\\\\nG(x,y;\\eta)&=G(x,y)=y^2\n\\end{align*}\nwhere $c$ is a constant to be chosen later.\n\nThese functions satisfy Assumptions 1, 2, and 3. (Note that the definition of Lipschitz continuity is stated incorrectly in Assumption 1.) We can take $\\sigma_B=\\sigma_G=0$. Also, $G$ does not depend on $x$, so that $\\bar\\Delta_{xy}=0$.  It follows that $E_2 = A_2 \\bar\\Delta_{yy}$. \n\nIn this case, Algorithm 3 is just gradient descent, and in particular we have that $\\nabla f(x^\\ell)=c$ for all $\\ell\\ge 0$. Then Theorem 3 states that \n$$\n\\frac{1}{N+1}\\sum_{\\ell=0}^N\\\\|\\nabla f(x^\\ell)\\\\|^2 \\le \\frac{E_1}{N+1}+E_2,\n$$\nwhere $E_1$ is a constant (depending potentially on the initial conditions) and $E_2$ is a constant which does not depend on $f$. In particular, $E_2$ does not depend on the choice of $c$.\n\nBut, by our choice of $f$, Theorem 3 would imply that\n$$\nc^2 \\le \\frac{E_1}{N+1}+E_2,\n$$\nwhich fails for all sufficiently large $N$ and $c$.\n\n## Issues with the KL assumption\n\nTheorem 2 relies on assuming the function $H$ defined in Theorem 1 has the KL property. However, this function depends on the solution to the lower-level minimization, $y(x)$, and the corresponding Jacobian $J(y(x))$. These will typically be very complicated functions. As a result, it is unclear if the KL property could ever actually be checked in an example.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents convergence results for two single-loop algorithms for bilevel optimization. One algorithm is for deterministic problems, and is proved under a Kurdyka-Łojasiewicz (KL) assumption. The other is for stochastic problems, and does not require the KL assumption. The results are tested on a hyperparameter optimization problem.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In my view, Theorem 1 alone is not strong enough for publication.\n\nTo merit publication, I would recommend:\n- Fix Theorem 3 or remove it.\n- Get a version of Theorem 2 that doesn't rely on an uncheckable assumption, or remove it.\n- At least one of (the fixed versions of) Theorem 2 or 3 should still be in the paper, even if the other is removed.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mq4ZjJzQ8Q", "reviewer": "Reviewer_v4oY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths***\n\n1. This submission has provided solutions to avoid computing Hessian Inverse or Hessian Vector Multiplication.\n\n2. Convergence analysis have been established. \n\n3. Experiments looks promising on the considered task. \n\n***Weakness***\n\nI have several questions that the authors could hopefully address in the revision.\n\n1.  The following paper has also proposed stochastic single-loop algorithms (SMB, SBMA) that Neumann series to approximate Hessian Inverse. Thus, can the authors please discuss the difference and novelty of this submission on this matter?  I guess the main difference is that this submission used Gaussian smoothing to get rid of Hessian Vector Multiplication.\n\nGuo, Zhishuai, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. \"A novel convergence analysis for algorithms of the adam family and beyond.\" arXiv preprint arXiv:2104.14840 (2021).\n\n2. The following paper has also leveraged KL property to establish (imply) the sequential convergence and get rid of Hessian Inverse and Hessian Vector Multiplication. Therefore, can the authors please discuss the difference and novelty of this submission on this matter? Is it still safe to claim \"As far as we know, this is the first work that provides the convergence rate of the sequences generated by single loop methods.\"? Please check it out.\n\nLiu, Bo, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. \"Bome! bilevel optimization made easy: A simple first-order approach.\" Advances in neural information processing systems 35 (2022): 17248-17262.\n\n3. In experiment section or in the appendix, can the authors discuss more on the hyper-representation task? So the audience who are not familiar with this task, like myself, can understand it more easily. In particular, what are $\\lambda$'s.\n\n4. Minor issues: \n \ni) The complexity rate for ES-ITDM has been missed in Table 1. Is it intended? \n\nii) The first sentence in Section 7 Experiment seems incomplete, do you mean \"we test XXX\"? \n\niii) The first problem formulation in Section 7 Experiment has both $\\omega^*_\\lambda$ and $\\omega^*(\\lambda)$. You may want to have only one expression for this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a single-loop algorithm to address bilevel problem under a KL property. The algorithm does not require computation of Hessian Inverse or Hessian Vector Multiplication. Convergence analysis and experimental results have supported the efficiency of the proposed algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Above.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article aims to address the task of developing efficient methods for nonconvex bilevel optimization problems. Specifically, the authors focus on creating single-loop iterative differentiation (ITD) methods that can approximate the hypergradient while avoiding computationally expensive Hessian calculations. By proposing a Hessian-free method, they aim to reduce the number of backpropagations and lower the computational cost, while also ensuring convergence properties and maintaining efficiency compared to other state-of-the-art bilevel optimization approaches. The reviewers have all provided positive feedback. Through the rebuttal, the authors have addressed most of the reviewers' concerns. Therefore, this paper has reached a level suitable for acceptance.
Decision: Accept (poster)