qNBO: quasi-Newton Meets Bilevel Optimization
Authors: Sheng Fang
Yongjin Liu
Wei Yao
Chengming Yu
Jin Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: bilevel optimization
quasi-Newton
convergence analysis
Hessian-free
Primary area: optimization
TL;DR: We leverage quasi-Newton algorithms to enhance the hypergradient approximation for solving bilevel optimization problem with a guaranteed convergence rate.

Abstract: Bilevel optimization, which addresses challenges in hierarchical learning tasks, has gained significant interest in machine learning. Implementing gradient descent for bilevel optimization presents computational hurdles, notably the need to compute the exact lower-level solution and the inverse Hessian of the lower-level objective. While these two aspects are inherently connected, existing methods typically handle them separately by solving the lower-level problem and a linear system for the inverse Hessian-vector product. In this paper, we introduce a general framework to tackle these computational challenges in a coordinated manner. Specifically, we leverage quasi-Newton algorithms to accelerate the solution of the lower-level problem while efficiently approximating the inverse Hessian-vector product. Furthermore, by leveraging the superlinear convergence properties of BFGS, we establish a non-asymptotic convergence analysis for the BFGS adaptation within our framework. Numerical experiments demonstrate the comparable or superior performance of our proposed algorithms in real-world learning tasks, including hyperparameter optimization, data hyper-cleaning, and few-shot meta-learning.

Published as a conference paper at ICLR 2025
QNBO: QUASI-NEWTON MEETS BILEVEL OPTIMIZA-
TION
Sheng Fang!? Yong-Jin Liu Wei Yao Chengming Yu Jin Zhang
Public Health School, Fujian Medical University, 'School of Mathematics and Statistics, Fuzhou University, CCenter for Applied Mathematics of Fujian Province, *Department of Mathematics, SUSTech, 'National Center for Applied Mathematics Shenzhen, SUSTech, "Shooo of Science, BUPT, CCET Key Laboratory of Smart City Modeling Simulation and Intelligent Technology, The Smart City Research Institute of CETC
shengfangl 99601 com, yjl uu zu. edu. cn on yaow@sustech. edu,
688bbppt. en, zhang Saanngg9@suttehhheo edu.
ABSTRACT
Bilevel optimization, addressing challenges in hierarchical learning tasks, has gained significant interest in machine learning. The practical implementation the gradient descent method bilevel optimization encounters computational hurdles, notably the computation of the exact lower-level solution and the inverse Hessian of the lower-level objective. Although these two aspects are inherently connected, existing methods typically handle them separately by solving the lower- level problem and linear system for the inverse Hessian-vecte product. In this paper, we introduce a general framework to address these computational challenges coordinated manner. Specifically, we leverage quasi-Newton algorithms accelerate the resolution of the lower-level problem while efficiently approximating the inverse Hessian- vector product. Furthermore, by exploiting the superlinear convergence properties of BFGS, we establish the non-asymptotic convergence analysis of the BFGS adaptation within our framework. Numerical experiments demonstrate the comparable or superior performance of the proposed algorithms in real-world learning tasks, including hyperparameter optimization, data hyper- cleaning, and few-shot meta-learning.
INTRODUCTIONS
Bilevel optimization (BLO), which addresses challenges in hicrarchical decision process, has gained significant interest in many world applications. Typical applications machine learning include meta-learning (Franceschi et al.
2018
Rajeswaran et al. 2019), hyperparameter optimization (Pe)
dregosa 2016: Franceschi et al.
2017
Okuno et al. 2021). adversarial learning (Goodfellow et
2014; Plau & Vinyals 2016), neural architecture search (Chen al.) 2019; Elsken et al.) 2020), and reinforcement learning Yang et al.
2019;
Hong et al. 2023). 3. In this study, we revisit the following
BLO problem:
min ZERO
((x) = F(x,y" s.t. y" (x) arg min f(x, v),
(I)
yER"
in which the upper-level (UL) objective function F; IRm x R" + R is generally nonconvex, while the lower-level (LL) objective function f : x R" - R is strongly convex with respect to (w.Ez.) the LL variable y R".
The gradient of (x)). known as hypergradient, is crucial not only for applying gradient descent but also for developing accelerated gradient-based methods for BLO problems. Therefore, fundamental question in solving BLO problems how to efficiently estimate the hypergradient. Assuming that is continuously twice differentiable, and by applying the chain rule and utilizing the first-order optimality condition V (x, y/ (x)) = 0 of the LL optimization problem (Ghadimi & Wang 2018 the hypergradient is given by
(Φ(x) = v.r)),
V / (x)) ( (x)) F(,,,
(2)
Coorresonndence Jin Zhang

---

Published as a conference paper at ICLR 2025
Two main challenges in estimating the hypergradient are: (C1) evaluating the LL solution y (z); (C2) estimating the Jacobian-inve once a good proxy y for the LL solution y (z) is obtained.
vector product [V my (z, y) [V by fxx Fx,
For (CI), the common approach is to perform a few additional gradient descent steps for the LL problem on the current estimate yk. using it as a proxy for the LL solution. For (C2), two main approaches have been proposed in the literature. The first is to estimate the inverse Hessian using the (truncated) Neumann series (Ghadimi & Wang 2018 Ji al. 2021). The second approach is to (c. y) by solving the linear system
compute the inverse Hessian-vector product V yy. (z,y)
V.
[x y)]æ = V, (x, y) for z, and then calculating 2 I (a, v)1 (Pedregosa) 2016 Arbel & Mairal 2022 Dagréou et al., 2022). Clearly, the hypergradient approximation error depends on the errors in both (CI) and (C2). Most existing methods handle (CI) and (C2) separately, using different
techniques.
A notable exception is the recent breakthrough by (Ramzi et al. 2022). which introduces a novel approach (named SHINE), specifically designed for deep equilibrium models (DEQs) (Bai et al. 2019 2020) and BLO problems where the UL objective function does not explicitly depend on the UL variable, i.e,, F(x. y) C(y)- The novelty of SHINE lies in its approach to addressing (C1) and (C2) closely. The main idea is to use quasi-Newton (qN) matrices from the LL solution process to efficiently approximate the inverse Hessian in the direction needed for the hypergradient computation. SHINE provides three methods for approximating the hypergradient by incorporating a technique OPA with Broyden's 's method and BFGS. Note that in the OPA method from Ramzi al., (2022). the qN matrices derived from the L.I. resolution are influenced by additional updates. This can potentially lead to incorrect inversion, as noted in Ramzi et al. (2022). ). To mitigate this issue, they employ a fallback strategy. In theory, SHINE demonstrates asymptotic convergence to the hypergradient under various conditions but does not guarantee convergence of the algorithmic iterates.
Therefore, inspired by SHINE, our focus is on improving hypergradient approximation and reducing barriers to solving BLO problems. In particular, our main research question is: Can we develop method to enhance hypergradient approximation for solving the bilevel optimization problem in (7) with a guaranteed convergence rate?
1.1
MAIN CONTRIBUTIONS
Our response this question is affirmative, and our main contributions are summarized below.
NBO, a new algorithmic framework utilizing quasi-Newton techniques, is proposed for solving the BLOO problem ① Unlike SHINE, qNBO includes subroutine that applies quasi-Newton recursion schemes specifically tailored for the direction F, y), avoiding incorrect inversion.
We validate the effectiveness and efficiency of NBO with two practical algorithms: NBO (BFGS) and qNBO (SR1), corresponding to two prominent quasi- methods. The numerical results demonstrate qNBO's comparable or superior performance compared to its closest competitors, SHINE (Ramzi et al.) 2022) and PZOBO (Sow et al.) (0226), as well as other BLO algorithms, including two popular fully first-order methods: BOME (Liu et al. 2022 and F2SA (Woon et al. 2023).
By leveraging the superlinear convergence rates of BFGS, we analyze the non-asymptotic convergence of BFGS adaptation within our framework, qNBO.
1.2 ADDITIONAL RELATED WORK
Quasi-Newton methods. Because of the low computation cost per iteration and fast convergence
rate, quasi-Newton (qN) methods has been extensively studied (Nocedal & Wright 2006). The
most common qN methods are the Broyden--Fletcher-GGolll Goleeerooooffbbbboooa Shaaarrb---ooooooo (BFGS) (Broyden 1970b a
Fletcher 1970 Goldfarb| 1970; Shanno 1970), its low-memory extension L-BFGS (Liu & Nocedall 1989), and the symmetric rank one method (SR1) (Davidon) 1991; Broyden 1967.. For BLO
problems, Pedregosa (2166) first uses L-BFGS solve the LL. problem to certain tolerance. Then a soojugate-gradienn method is applied to solve the linear system 2 (x. v)]= V Fxx v) through
matrix-vector products. Finally, (V2 f v)] is calculated.
2

---

Published as a conference paper at ICLR 2025
Hypergradient approximation methods. Various bilevel methods have been proposed recently to approximate the inverse Hessian or omit some second-order derivative computations in the hypergradient. For example, FOMAML (Finn et al. 2017 Nichol et al. 2018) skips calculating all second-order derivatives. DARTS (Liu et al. 2018) solves the LL. problem with just one gradient descent step. The Jacobian-Free method (JFB) (Fung al. 2022 approximates the inverse Hessian with the identity. Giovannelli et al. (202)) proposes practical low-rank bilevel methods (BSGI and BSG-N-FD) that use first-order a approximations for second-order derivatives through finite- difference scheme or rank-1 approximations. Recently, several zeroth-order methods have been proposed to approximate the full hypergradient, such as ES-MAML (Song et al.) (219) and HOZOG (Gu et al. 2021). Another zeroth-order method, PZOBO (Sow et al. 2022b), approximates only part of the hypergradient by comparing two optimization paths.
There is another line of research for BLO problems, which does not explicitly use the hypergradient in (2). see, e.g., -.g..... Liu et al. 2023); Sow al. 2022a);{Shee & Chen (203) [Luu et al. (2022); (
[ et al. 22023 2024). These algorithms first use the value function of the lower-level problem to transform the bilevel problem into single-level problem. Then, they apply the penalty function method or other techniques to solve the reformulated problem. For instance, BOME (Liu al. 2022)
is a novel and fast gradient-based method that uses a modified dynamic barrier gradient descent on the value-function reformulation. F2SA (Kwon et al. 2023) is fully first-order method developed from a value function-based penalty formulation. It can be implemented in a single-loop manner. Additionally, it is shown in Kwon et al. (2023) that the update direction of F²SA has global (LL/A)-aaproxxi) appp///pppoxxibbliit of the exact hypergradient, where À is the penalty parameter.
2 PROPOSED FRAMEWORK
In this section, we introduce general framework, qNBO, to enhance hypergradient approximation. addresses the computational challenges (CI) and (C2) using quasi-Newton techniques. We begin by rewriting the hypergradient as:
< = V,F(x, y (x)) - [(, y (x)))(")))[ u (a,
(x)),
where w" (z, v) := 2 f(r y) F(r, F(r,)),,,.)))).. y). As in Arbel & Mairal (022) and Dagréou et al. (2022), the proposed algorithms introduce an additional variable 4y alongside 2y and ye. Naturally, qNOO consists of three components. The details of qBOO are presented in Algorithm
Algorithm 1 NBO quasi-Newton Meets Bilevel Optimization
Input: To, yo: initial matrix Ho: stepsize a > 0; iterates numbers K, [Qx) KK11 for k = 0, l,..., , K- 1 do
1. Mk++1 <- A(xK, yk) update y by a subroutine
2. if Qx= = 1:
uk+1 t- CyN (V, F(r,, Mk+1), Ho. fst, Dt (To) # share {st, ge T-1 with A(rk, Uie)
else:
Uk+1 +- B(xx, 1, Ho. F Fx Wh+ Qk) # improve u by subroutine B
3. T6+1 <-
(V,F v1+ [V [< Mk+ 1)]" (Tu+ti)
end for
Part 1: qNOO updates yi towards y (xx) using a ba-ba subroutine A(æx, yk) in Algorithm 2 starting from yı. The key is quasi-Newton recursion scheme C,N, which computes the -eetor product Hd by performing a sequence of inner products and vector summations involving d and the pairs {s;, 9: 1- Here represents the inverse Hessian approximation of the LL objective, d = fx,(x, Ut), $; = ys+1 yi. and 9; = fx, 11+ [z, (2..z) yk) in this subroutine. Two prominent quasi-Newton recursion schemes are provided in Appendix [B.
Part 2:
To update u4+1, provide two options: Q = or Qx > 1. In the case of Q: 1, NBO T-1 from A(IR: ykk are shared to approximate
updates Us++ similarly to SHINE. The pairs (st, 0: F== the inverse Hessian in the direction V FIF( 36++). Unfortunately, incorrect inversion may occur
TT in A(zE. yrh) are designed to satisfy the secant equation H,+19t 19: = st- To address this issue, qNBO adds subroutine B in Algorithm which uses quasi-Newton recursion
because the pairs {s,, )r ==0
3

---

Published as a conference paper at ICLR 2025
schemes for the direction V F [z Mk+1) when Qs 1. The price to pay is that the pairs {s,, 9i in A cannot be shared with B, increasing the computational cost. Thus, choosing between Qx = 1 and Qk involves trade-off off between performance and computational cost.
Part 3: After computing V and uk++1 qNBO updates rk+11 by
Ct [ FIk,, yk+1) V xy f yk+1)l )]2 uu+1u.+
Tk+1
where og is a stepsize, and 4 (xg)= = V (I,, Mk++1 1 V (at, 4k+11) 1] uu++1 is a hypergradient approximation. This update rule for ag is commonly used in muddenttbbasdd algorithms, such as those in Arbel & Mairal (0022) and Dagréou et al. 2202)..
Algorithm 2 A(x,, y"): gradient descent steps + qN steps for the LL problem
Input: ;: initial matrix Ho; stepsizes 8, 7 >> 0; iterates numbers P.T
1. for y 0.........P .......P-. P
8d vf
end for
2. y0 + yp
for t = 0..... 11
M/+1 t- 8/1 - -di,,
where de + CNN( y (z, vr), Ho. (si, (())))) (t 1), do + Ho HoV, 9t - ye+1 +-+1 yt 9r vuf (2,3((1) Vvf(I.
end for
Return yr. (st, 9t 1:
Algorithm 3 B(x, Hu, d, Q)
Input: x, y: initial matrix Hy; vector d; stepsize > iterates number
1. do - Hod, 8g + Eoug and ğo + V f y y 80) vzl(x,))
2. for i i= 1,2.... Q
U; + CyN (d, Ho. (5,, )-
$; < E.u. 9b + (z, + 8,) - V (zf(2,
end for
Return UQ-1-
Two practical qBBO algorithms: QNOO (BFGS) and QNBO (SR1). We describe two prominent quasi-Newton recursion schemes, CyN, for computing the inverse Hessian approximation-veet product H,d. These schemes involve sequence of inner products and vector summations with
and pairs {&i, St H-1 One is the BFGS two-loop recursion scheme, outlined in Algorithm 4
corresponding the BFGS updating formula (Broyden) 1970b a Fletcher 1970, Goldfarb 1970
Shanno 1970):
1 H p(stit)) H, (I pigist) + pest Pt
(3)
9 8t
The second algorithm is presented in Algorithm 5 which corresponds to the symmetric-rank-one (SR1) updating formula (Davidon 1991 Broyden 1967p:
(st Hig:)(s H.gh)
H4+1 H, +
(s+ H.gh) Y ge
Implementation and improvement. Several details and enhancements are needed for an efficient implementation of qNBO.
First, the purpose of including a few gradient descent steps in subroutine AA is to bring the iterators closer to neighborhood of the LL solution, enabling superlinear convergence in subsequent quasi- Newton steps. A warm-start for yd is effective because y (#x+1) remains close to (2x) when Tk+1 is TA- This is guaranteed by the Lipschitz continuity of y" ((x). In practice, conjecture
4

---

Published as a conference paper at ICLR 2025
that few initial gradient descent steps are sufficient, although they necessary for the theoretical analysis.
Second, because fzz, y) exhibits strong convexity w.r.f. y in context, the curvature condition of 9t > O, required for BFGS, is consistently satisfied. This allows the use of a fixed step size, eliminating the need for time-consuming line searches. Furthermore, as the solution approaches region conducive to superlinear convergence, employing a few quasi-Newton steps is sufficient to achieve satisfactory solution.
Third, in experiments, the initial matrix Ho is chosen as a scalar multiple of the identity matrix. This simplification ensures that the recursion algorithms, Algorithms 4 and [ involve only vector inner products, significantly reducing computational costs. In Algorithm the parameter Ç is typically set to either ||u/|| || in most cases.
Fourth, qNBO is a flexible framework that can integrate other quasi-Newton methods, such as limited memory BFGS (L-BFGS) (Liu & Nocedal 1989). also supports "non-loop" implementation of L-BFGS by representing quasi-Newton matrices in outer anter-product form (Byrd et al. 1994).
Finally, qNBO consists of three parts, with the first two utilizing quasi-Newton recursion schemes. A stochastic adaptation involves replacing these schemes with stochastic methods (e.g.. K-BFGS (Goldfarb et al., 2020), Stochastic Block BFGS(Gower et al., 2016)) and using stochastic gradients in Part 3, aligning with Dagréou et al. (2022). Key challenges in implementing the stochastic adaptation include constructing effective unbiased or biased estimators in Part 3 using techniques like variance reduction and momentum, and analyzing the convergence rate and complexity of the proposed stochastic algorithms in bilevel setting that leverages noisy second-order information. Addressing these theoretical issues may require breakthroughs beyond the scope of this work.
3 THEORETICAL ANALYSIS
In this section, we analyze the non-asymptotic convergence of the qNBO algorithm, as outlined in Algorithm I under standard assumptions commonly used in BLO literature (Ghadimi & Wang 2018 Ji et al. 2021 Chen et al. 2022 Dagréou et al. 2022 Ji et al. 2022).
3.1 ASSUMPTIONS
Assumption 3.1. Assume that the UL objective function F satisfies the following properties:
(i) For all x, the gradients v, F, y) and F(r, are Lipschitz continuous w.r.t. y. with Lipschitz constants Lr, and Lr,, respectively.
(ii) For all y, V Fx, is Lipschitz continuous w.r.l x, with a Lipschitz constant Lr,-
(iii) There exists a constant CF, such that V,F v)1l < CF, for all r,y.
Assumption 3.2. Assume that the LL objective function f has the following properties:
(i) For all x and y. f is continuously twice differentiable (a, v).
(ii For all æ, f", y) is strongly convex w.r. y with parameter μ > Moreover, V v) and 22 / (x, y) are Lipschitz continuous w.rlf y with parameter I and L,,,, respectively.
(iii) For all x, 2 (x, y) is Lipschitz continuous w.r.f. y with constant Lfav-
(iv) For all v. y. we have 2 Zy (z, w|ll S M, for some constant M fev'
(v) For all y. f v) and V J (a. v) are Lipschitz continuous w.r.. x with constants T,,,, and Li respectively.
Assumption 3.3. There exists & R such that inf,, ((x) 2 4.
5

---

Published as a conference paper at ICLR 2025
3.2 CONVERGENCE RESULTS
The evolving nature of inverse Hessian approximations through updating formulas in qNBO sig- nificantly complicates the analysis of non-asymptotic convergence. Additionally, various update formulas present different challenges, similar to studying the convergence rates of quasi-Newton methods. In this section, we focus on the non-asympiotic convergence of QNBO (BFGS), leveraging the superlinear convergence rates of BFGS. Some results can also be extended to qNBO (SRI). Comprehensive proof' of these results are provided in Appendix [
Let Lg be the Lipschitz constant of 4 given in Lemma D.12 We first present the convergence results of qNBO (BFGS) for solving the bilevel problem quadratic.
D.. where the LL objective function is
Theorem 3.4 (quadratic case). Suppose that f in 7 takes the following quadratic form:
[(x, v) = 2² Ay - y²x,
(5)
where μI 3 A 3 LI. Assume that Assumption 3.7 and 3.3 hold. Set Qk = k + 1 and Ho LI. Let L/μ. to == 4nlnx, Ct == 2t and w C1 } )c (T) where is positive
constant given in Theorem D.19 We can choose positive parameters 0, & and T such that T == (
()))())) ((1 +e) + + )a=ci < and aLo + wa² ( + +ab)) I S Then the iterates
In generated by qNBO (BFGS) satisfy:
K-1
((((z)) ir ((x))
35p
18n InK
+
(6)
K
ak
K(1 T)
μ²
K=
with the initial error 5n xc calle woll? where 02 is a constant.
Remark 3.5. For the quadratic case, quasi- quasi-Newton methods achieve global superlinear convergence
(Ye et al. 2023 Rodomanov & Nesterov 2022; 2021b), allowing P = 0 in Algorithm 2
Remark 3.6. The convergence rate of qNBO (SR1) for the quadratic case is similar that in Theorem 3.4 However, for the general case, the NBO (SRI) algorithm lacks convergence guarantees without specific corrections used to achieve numerical stability, noted in Ye al. (2023).
Next, we explore the case where the LL objective function in ( takes a general form. While the convergence rate of qNBO (BFGS) resembles that of the previous quadratic case, it is much more challenging. The specific convergence rate for this general case detailed in the following theorem.
Theorem 3.7 (general case). Suppose that Assumptions
3.7
3.2 and 3.3 hold. Set Qs = k + 1. VE
Choose the parameters 3 and P such that (1 -
(1-3p)" 3pp""lle
300 and assume Ho satisfies:
J (Ix)) 2 by (a y² (xx))-1/2[(1r Σ 7. Define T = Bp)p. with constant 63 given Theorem D.24 We can choose positive parameters o, E and T such that t < and
VIV? J (xx)) 112 (Ho'
R( (T - By) ((1 ++) + (1 + )))²ca) and w == ca(1 + ()((())
al4 + wa² (1 + aT.o) I-r
< 3. Then the iterates Ug generated by gNBO (BFGS) satisfy:
1
K-1
|V 4(2(20) - inf ((x))
380
18nLM?
Jxx C2,nK
InK
+
(7)
K
aK
K ((1-T)
where 60 = 3m( (T) 3y) c4 yo is the initial error with constant c4. The constant É is related the property of f. as given (29
The proof sketch of Theorem 3.7 can be found in Appendix D.2
The complete version of the parameter specifications and the proofs of Theorems 3.4 and 3.7 are provided in Appendices [D.3 and
D.4 respectively.
Discussion on convergence rate and complexity. Choose (k 3)
O(In k) and the step size + S 4. Under the same setting as Theorem
such that
and aLg + wa? (1 aL4)
3.7 we have K Σ K 0 [[ O ( K
In To achieve an e-stationary point, it is K
required that K Ō(r3c-1), resulting in gradient complexity of Gc(f,c) ((n6c-3) and Go(F,e) = 0 -1), well as Jacobian-vector product complexity of JV(c) O(13e-1).

---

Published as a conference paper at ICLR 2025
The details for ensuring 1 and aLæ + wa? ( aLg) 1- 1. as well the specific complexity analysis, can be found in Appendix E.
Theoretical comparisons. Our analysis provides non-asymptotic convergence rate, superior to that of SHINE (Ramzi et al.
2022). It is established in et al. (2022) that the fastest deterministic
k== ( [ = ( ), is achievable. In comparison, BOME (Liu et al. 2022) reaches convergence rate of O(K- FASA (Kwon et al. 2023 attains O
convergence rate, K
Ib and K
SABA Dagréou et al. 2022) achieves O R) To achieve an e-stationary point, the matrix-vector complexity for qNBO is O primarily due to the / (i]",,)]'" calculations. It is worth noting that the number of Jacobian-vector products and Hessian-vector products for AID-BIO (Ji et al. 2021 are of the orders O(xre= and (1x355c- respectively. Although the gradient complexity Go(F, e) for qNBO is higher than that AID-BIO (Ji et al.) 2021). the computation of gradients is generally less complex than performing matrix-vector operations.
NUMERICAL EXPERIMENT
In this section, we conduct numerical experiments to evaluate the performance of the qNBO algo- rithms in solving bilevel optimization problems. We first validate the theoretical convergence through experiments on toy example, followed by an assessment of efficiency by comparing qNBO with its closest competitor, SHINE (Ramzi et al.) (022), well other bilevel optimization (BI.O) algo- rithms such as AID-BIO (Ji et al. (2021) with CG method), AID-TN (Ji et al. (2021) with Truncated Neumann method), AMIGO (Arbel & Mairal (2022) with CG method), SABA (Dagréou al. 2022) and BSG1 (Giovannelli et al. (021)) Additionally, we compare qNBO with two widely used fully first-order algorithms, BOME (Liu et al., 2022) and F2SA (Kwon al. 2023). in real-world applications including hyperparameter optimization and data hyper-cleaning. Finally, we explore qNBO's applicability to complex machine learning tasks by exclusively comparing with PZOBO (Sow et al. (002b) in meta-learning experiment, where PZOBO is regarded the leading algorithm for few-shot meta-learning. Details of all experimental specifications are provided in Appendix C Additionally, we perform ablation study in Appendix C.5
4.1 TOY EXAMPLE
In this section, consider quadratic bilevel problem where both the UL and LLL objective functions are quadratic. Given 20 E R" and the symmetric positive definite matrix A E Rax=, the problem is formulated follows:
1 1 "/"5"(aa (x)² Ay" (x) s.t. y y²(x) aar min 5y¹ Ay x= | - 20l12 2
min FER
(8)
EER"
In the experiment, the vector on and the matrix A are randomly generated, with 1000. The hypergradient is given by v = (A-1+ +/x zo, which yields the unique solution (x yy) = AA-
((A-++ T) this problem, we analyze the hypergradient estimation errors and the distances between the iterates (Ir, and the optimal solution (x" .y"). The results, shown Figure 1 [)), indicate that AID--IO,, AMIGO-CG and qNBO (SR1) achieve smaller hypergradient errors and produce iterates closer to the optimal solutions compared to other methods. Furthermore, we analyze the impact parameter {Q+) K-1 Algorithm on the performance of qNBO (BFGS). As depicted in Figure (d) shows that the hypergradient (xx) generally decreases as Qs increases, with [Qk] performing the best, thereby supporting the claims of Theorem 3.4
1) 20, A
zo). To evaluate the performance of various methods in solving
K-1 = {1r + 1)K-
4.2 HYPERPARAMENT OPTIMIZATION IN LOGISTIC REGRESSION
We perform hyperparameter optimization for Iz-regularized logistic regression on the 20News (Lang 1995) and Real-sim (Chang & Lin) datasets, formulated as bilevel problem:
exp(x))
min RER
Σ lld,, B.y. (x)) s.t. (x()) = arg min yER"
C(a;, by.
11.12
(9)
2

---

Published as a conference paper at ICLR 2025
Q AID-BIO
QNBO(BFGS) AMIGO-CG
BOME
SHINE-OPA
PZOBO
F2SA
AID-TN
(a)
(b)
10
10
10
100
10
x
10
10
10
10
10
10
10
10
10a
10.
10
10
107
10
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3.0
Running Time (s)
Running Time (s)
(c)
(d)
10a
10a
Q0-20
10
0.4k1
10
104
10
10a
10a
10a
10-
10
10a1
0.0
0.5
1.0
1.5
2.0
2.5
3.0
10-3
Running Time (8)
20
60
100
Iteration: k
Figure Numerical results on toy example. (d) Testing results on the impact of the parameter (Qx [Q in qNBO (BFGS).
:NRO(BFGS)
@NBOISRII 1)
RSGI BOME
F2SA
AID-TN
AMIGO
PZOBO
AID-BIO
10
Test loss
Test loss
10a
10a
10a
5
15
0
2
4
6
8
10
Rumning time (s)
Running time (s)
Figure 2: Hyperparameter optimization experiments for lz-regularized logistic regression two datasets (Left: 20News; Right: Real-sim).
where (ai, bx) E Darain and (a), E DDntt the training data and validation data respectively, and f(a;, by, log exp( bb,, (aa,TT)), The LL variable y is the model's parameter, while the UL variable x refers to the regularization hyperparameter.
The performance of different methods the unseen dataset Dreat shown in Figure 2 where the results over 10 runs are plotted for each method. Here AMIGO refers to the algorithm AMIGO in Arbel & Mairal (2022) that employs gradient descent solve the auxiliary quadratic problem. The
8

---

Published as a conference paper at ICLR 2025
results show that qNBO (BFGS) reaches its lowest loss faster than the other methods. Notably, the performance of qNBO (SR1) on the 20News dataset was omitted due to its ineffectiveness this experiment, which resulted in oscillations. This issue arises from the numerical instability of SR1
when solving general functions without a correction strategy (Ye et al.
2023
(NBO(BFGS)
(NBO(SRI)
SHINE-OPA
SABA
F2SA
AID-TN
AMIGO
PZOBO
BOME
AID-BIO
0.92
0.840
Test accuracy
0.90
Test accuracy
MMMM WW
0.825
0.88
0.86
0.810
0.84
0.795
0.0
0.5
1.0
1.5
2.0
0
2
4
8
10
Running time
Running time (s)
Figure 3: Data hyper-cleaning results on two datasets. (Left:: MNIST; Right: FashionMNIST).
4.3 DATA
This subsection focuses on data hyper-cleaning for the MNIST Deng 2012) and FashionMNIST (iiao al. 2017) to enhance model accuracy, using noisy training set Ptrain := {a,, b, and clean validation set Vaal- The objective is to adjust the training data weights to improve performance on D This task can be formalized as the bilevel problem:
min eral (y* s.l. (x) arg min ( v) + c||y/|1},
(10)
where gval is the validation loss on Dval and (train = E (xx))((a,, by, y) is a weighted training loss with (x)) = Clip(æ, [0, 1)) and æ E I In the experiment, both E(a;, b;, y) and gval are the cross entropy loss, with 0.001.
Table 1: Comparison results for hyper-cleaning. We compare the time and Fl score of various algorithms in achieving specific test accuracies (91.50% for MNIST and 83.00% for FashionMNIST), Bold font indicates the fastest time to reach the target accuracy. If an algorithm fails to reach the required test accuracy, the time is recorded up the highest accuracy achieves.
MNIST
FaShionMNIST
Method
Time (s)
Acc. (%)
Fl score
Time (s)
Acc. (%)
Fl score
qNBO (BFGS)
0.42
91.54
95.34
0.83
83.04
93.56
QNBO (SRI)
3,68
91.51
94.59
1.53
83,02
94.09
BOME
6.31
91.50
94.94
3.59
83.00
93.48
SABA
3.35
91.44
94.79
44.29
82.79
88.81
FASA
8.06
91.46
93.31
8.72
82.98
86.55
SHINE-OR
20.25
91.51
95,44
9.96
83.07
93.87
PZOBO
1.05
91.46
95.46
2.96
83.05
93.77
As shown in Figure 3 qBBO (BFGS) significantly outperforms other methods, achieving lower test loss and higher test accuracy more quickly. All results are averaged over 10 random trials. Table iillustrates that while qNBO, BOME, and SHINE-OPA are able to achieve the required accuracy, QNBO (BFGS) does so the shortest time. Notably, both F2SA and SABA fail to reach the target accuracy either dataset. For example, the MNIST dataset, qNBO (BFGS) requires less than one- tenth of the time taken by BOME, the second fastesst method. The exclusion BSGI's performance from this experiment is due its ineffectiveness in addressing these data hyper-cleaning problems.

---

Published as a conference paper at ICLR 2025
4.4 META-LEARNING
In this subsection, we consider the few-shot meta-learning, which can be described as:
min Σ ui (x)) s.t. y" (²())=)((+>>>))))>( arg min Σ Ls. (z,, vi).
Due the superior performance demonstrated by PZOBO compared the baseline methods (MAML (Finn et al. 2017) and ANIL (Raghu et al. 2020)), the comparison of qNBO (BFGS) is exclusively conducted against PZOBO, excluding the atorementioned baseline methods.
65
99.2
99.0
Test accurasy (%6
98.6
98.4
50
98.2
45
Test
98.0
JNBOIBFGS)
97.8
QNBD/BFUS)
P20DO
97.6
97.4
35
0
1000
2000
3000
4000
5000
200
300
500
600
700
800
Running time (s)
Running time
Figure 4: 5-way 5-shot experiments on two datasets. (Left: minilmageNet; Right: Omniglot.)
As shown in Figure 4 and Table 2 NBO (BFGS) achieves superior accuracy compared to PZOBO on the minilmageNet (Vinyals et al. 2016) and Omniglot (Lake et al.) 2015) datasets. Results are averaged over 5 runs, with all algorithms starting from the same initial point with 20%. For clarity, the graphs begin at the second data point, omitting the initial one. It is reported that qNBO (BFGS) reaches peak test accuracies on the Omniglot dataset within 800 seconds, after which performance declines, likely due to overfitting or other factors. Notably, on the minilmageNet dataset, QNBO (BFGS) attains test accuracy exceeding 60%. while PZOBO fails achieve comparable results. Furthermore, the results in Table 2 show that qNBO (BFGS) reaches higher test accuracy in significantly less time compared PZOBO as the number ways increases. We do not plot the curves for other methods like SABA, SHINE-OPA, and BOME, as they are difficult to converge under various hyperparameter configurations using their source codes.
accuracy of
Table Few-shot meta- leta-learnnng on the Omniglot dataset: highest test accuracy and time required by each algorithm.
PZOBO
qNBO (BFGS)
5-shot
Acc. (%)
Time (s)
Acc. (%)
Time (8)
5-way
99.31
11124
99.14
772
20-way
97.94
17869
99.14
1648
30-way
97.15
21043
99.05
2978
CONCLUSION
This paper introduces NBOO, a flexible algorithmic framework for improving hypergradient approxi- mation. It leverages quasi-Newton techniques to accelerate the solution of the lower-level problem and efficiently approximates the inverse Hessian-vector product in hypergradient computation. No- tably, qNBO includes a subroutine using quasi-Newton recursion schemes specifically tailored for the direction F(x, y) to avoid incorrect inversion. Furthermore, addition to the prominent BFGS and SR1 methods, qNBO can integrate other quasi-Newton methods such limited- limited-memon memory BFGS (L-BFGS) and single-loop implementations. Extensive numerical results verify the efficiency of the proposed algorithms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Authors listed in alphabetical order. This work is supported by National Key R & D Program of China (2023YFA 101 1400), National Natural Science Foundation of China (12222106, 12271097, 12326605, 1233 12371305), Guangdong Basic and Applied Basic Research Foundation (No. 0022B1515020081 the Key Program of National Science Foundation of Fujian Province of China (Grant No. 2023J02007). the Central Guidance on Local Science and Technology Development Fund of Fujian Province (Grant No. 20231,0003), and the Fujian Alliance of Mathematics (Grant No. (023SXLMMSON We sincerely thank the anonymous reviewers for their insightful comments and suggestions on this work.
REFERENCES
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In International Conference on Learning Representations, 2022.
Sébastien MR Arnold, Praateek Mahajan, Debajyoti Datta, Ian Bunner, and Konstantinos Saitas Zarkias. learn2learn: A library for meta-learning research. arXiv preprint arXiv:2008. 2020.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances neural information processing systems, 32, 2019.
Shaojie Bai, Vladlen Koltun, and J Zico Kolter. Multiscale deep equilibrium models. Advances in neural information processing systems, 33:5238-5250, 2020.
Charles G Broyden. Quasi-newton methods and their application to function minimisation. Mathe- matics of Computation, 21(99):368-338 1967.
Charles G Broyden. The convergence of a class of double-rank minimization algorithms: 2. the new algorithm. IMA Journal of Applied Mathematics, 6(3):222-231, 1970a.
Charles George Broyden. The convergence class of double-rank minimization algorithms general considerations. IMA Journal of Applied Mathematics, 6(1):76-90, 1970b.
Richard Byrd, Jorge Nocedal, and Robert Schnabel. Representations of quasi-Newton matrices and their use in limited memory methods. Mathematical Programming, 63(1):129-156, 1994.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. URL https: www..ntu....mm
Accessed: 2021-05-
06.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2466-2488. PMLR, 2022.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1294-1303. 2019.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-26710. 2022.
William C Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1(1): 1-17, 1991.
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6): 141-12441142 2012.
Thomas Elsken, Benedikt Staffler, Jan Hendrik Metzen, and Frank Hutter. Meta-learning of neural architectures for few-shot learning. In Proceedings of the IEEE/CVF conference on Computer Vision and Pottern Recognition, pp. 12365-12375, 2020.

---

Published as a conference paper at ICLR 2025
Jennifer B Erway and Roummel F Marcia. On solving large-scale limited- memory quasi-newton equations. Linear Algebra and its Applications. 515:196-221 225, 2017.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pp. 1126-1135. PMLR, 2017.
Roger Fletcher. new approach to variable metric algorithms. The Computer Journal, 13(3): 317-322, 1970.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pp. 1165-1173.. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning In International Conference on Machine Learning, pp. 1558-1177) PMLR, 2018.
Samy Wu Fung, Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley Osher, and Wotao Yin. JFB: Jacobian-free backpropagation for implicit networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 6648-6656, 2022.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018
Tommaso Giovannelli, Griffin Kent, and Luis Nunes Vicente. Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems. arXiv preprint arXiv:2110.0066 2021.
Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of Computation, 24(109):23-26, 1970.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. Advances in Neural Information Processing Systems, 22226662399,, 2020.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
Robert Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block BFGS: Squeezing more curvature out of data. In International Conference on Machine Learning, pp. 1869-1878, PMLR, 2016.
Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyperparameters via automated learning algorithm. arXiv preprint arXiv:2102.09026, 2021.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 3371):147-180 2023.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp. 4882 4892. PMLR, 2021.
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. Advances in Neural Information Processing Systems, 35:3011-3023 2022.
Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi-newton methods. Mathematical P Programming, 200(1):425-473, 2023.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Jeongyeol Kwon, 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.
12

---

Published as a conference paper at ICLR 2025
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright,, and Robert D Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference Learning Representations, 2024.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 1332-1333,,,, 2015.
Ken Lang. Newsweeder: Learning to filter netnews. In Machine learning proceedings 1995, pp- 331-339. Elsevier, 1995.
Bo Liu, 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.
Dong Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1):503-528, 1989.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In International Conference Learning Representations, 2018.
Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. calue-function-bast -base sequential minimization for bi-level optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803. 02999, 2018.
Jorge Nocedal. Updating quasi-newton matrices with limited storage. Mathematics of computation, 35(151):773-78, 1980.
Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer Science & Business Media, 2006.
Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe. On eprrraarrrrr learning via bilevel nonsmooth optimization. The Journal of Machine Learning Research, 22(1): 11093-11139, 2021.
Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. Advances Neural Information Processing Systems, 31, 2018.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pp. 737-746. PMLR, 2016.
David Pfau and Oriol Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint arXiv: 1610001944 2016.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness of maml. In International Conference on Learning Representations, 2020.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
Zaccharie Ramzi, Florian Mannel, Shaojie Bai, Jean-Lue Starck. Philippe Ciuciu, and Thomas Moreau. SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models. International Conference on Learning Representations, 2022.
Anton Rodomanov and Yurii Nesterov. Greedy quasi-newton methods with explicit superlinear convergence. SIAM Journal on Optimization, 31(1):785-81, 2021a.
Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi- newton methods. Journal of Optimization Theory and Applications, 188:744-769, 2021b.
13

---

Published as a conference paper at ICLR 2025
Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi-newton methods. Mathematical Programming, 194: 190, 2022.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 11:2211-22,, 2015.
David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of Computatioo, 24(111):647-665 1970.
Han Shen and Tianyi Chen. On penalty- based bilevel gradient descent method. In International Conference Machine Learning, pp. 30992-31015. PMLR, 2023.
Xingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski, Aldo Pacchiano, and Yunhao Tang. Es-maml: Simple hessian-free meta learning. In International Conference on Learning Representations, 2019.
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A primal-dual approach bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01 123, 2022a.
Daouda Sow, Kaiyi Ji, and Yingbin Liang. On the convergence theory for hessian-free bilevel algorithms. Advances in Neural Information Processing Systems, 35:4136 11-36649999 2022b.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in Neural Information Processing Systems, 29, 2016.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07743 2017.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergudic cost. Advances in Neural Information Processing Systems, 32, 2019.
Haishan Ye, Dachao Lin, Xiangyu Chang, and Zhihua Zhang. Towards explicit superlinear conver- gence rate for SRI. Mathematical Programming, 199(1):1273-1300) 2023.
14

---

Published as a conference paper at ICLR 2025
A OUTLINE OF APPENDIX
The appendix is organized as follows:
Appendix
B
presents details of recursive algorithms for computing the inverse quasi-
matrix-vector product.
Appendix provides details of the numerical experiments from Section 4
Appendix includes the proofs of the theorems from Section 3.2
Appendix D.1
reviews some useful results of the BFGS method;
Appendix
provides the proof sketch of Theorem 3.7
Appendix
D3
presents the proof of Theorem 3.4
Appendix
D.4
presents the proof of Theorem 3.7
E contains the theoretical discussion and complexity analysis of the proposed algorithms.
Appendix
B RECURSIVE PROCEDURE TO COMPUTE THE INVERSE HESSIAN APPROXIMATION VECTOR PRODUCT
Due to the low-rank structure of the updates in and (4 for any vector d, r H++1d d can be efficiently computed using the recursive methods detailed in Algorithm 4 for the BFGS update (Nocedal 1980), and Algorithm for the SR1 update (Erway & Marcia 2017), respectively. Note that Algorithms and S involve only the computation of first-order information, provided Hg is scalar multiple of the identity matrix. Consequently, by avoiding the storage and computation of the full Hessian, computational costs can be significantly reduced.
Algorithm 4 (d, Ho, (8i, 9: )=)): Two-loop recursion for computing H,d when He is the inverse of the BFGS matrix.
1: d;
2: for 1,t
(5) (9) s);;
1= Osgri;
end for
3: r Hlg:
4: for i 0,
3 = (g r) / 8:);
(a: B)ss
end for
Return r = H,d.
Algorithm 5 (d, Ho. (sy, :=)))) Computing r = H,d when H, is the inverse an SRI matrix.
1: for = O.....t ..........
pi s; Hogh:
2: for j = 0. 1-1
Pi = Pt (1 9.)/ 9:)))
end for 3: end for
Return r Hod + D d) p:)
C DETAILS ON EXPERIMENTS
In this section, we additionally compare more algorithms, such as AMIGO Arbel Mairal (2022) with CG method), AID-BIO (Ji et al. (202T) with CG method) and AID-TN (Ji et al. (202) with
15

---

Published as a conference paper at ICLR 2025
Truncated Neumann method). At the same time, add meta-leaminng experiments comparing with the PZOBO algorithm. All experiments are conducted on a server equipped with two NVIDIA A40 GPUs, an Intel(R) Xeon(R) Gold 6326 CPU, and 256 GB of RAM.
C.I DETAILS OF THE TOY EXAMPLE
In this experiment, the initial point for all algorithms is (zo, Ho) (2e,2e) where denotes the vector all ones.
NBOISRR)
NNBIBEESS) AMIGO-CG
QNBO(BFGS))
BOME
SHINE-OPA
AID-BIO
PZOBO
F2SA
AID-TN
(a)
(b)
10a
10
10
10
M
10
10
10
10
10
10
10
10
10.5
10
10.
10
10
10
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Rumning Time (s)
(c)
Running Time (s)
10a
10'
Ildx vol
10
1
2
10
10
0.5
1.5
2.0
2.5
3.0
Running Tine (s)
Figure 5: Numerical results toy example: Comparison of qNBO (SR1), qBOO (BFGS) and qNBO (BFGS)-Ws -w with other bilevel optimization methods in a toy experiment. Here, "ws" indicates that a warm-start strategy is applied for uk, with Qs min(k + 1, 60).
BOME: The maximum number of outer iterations is K 5000, the number of inner iterations is = 100, the inner step size is = 0.1, the outer step size is E 0.1, and
max 0.00010(xx, yk)
(VF 2k 0k), V (g vk)) 03. V 1
A
FOSA: The maximum number of outer iterations is K 5000, the number of inner iterations is T= 10, the inner step sizes are "/k = 0% = 0.1, the initial multiplier Xg = 0.1, the multiplier increment is 0.001, and the step size ratio is f 1.
The maximum number of outer iterations is K = 5000, the maximum number of inner iterations is T' 100, the inner stopping criterion is f M*+1)]l S - the inner step size is determined using strong Wolfe line search, the number of extra updates of upper-level information in the BFGS algorithm is (i.e., every 5 steps of BFGS iteration includes an update with UL. gradient V, y P), the initial matrix is Ho T, and the outer step size is 0g 0.1.
SHINE-OPA:
16

---

Published as a conference paper at ICLR 2025
Q
Q,-10
0.-20
0,=50
Fws
0,=k+1
(8)
(b)
10
10"
10a
x-x x
-10
-10
10a
10a
10
10
10a
10
10
10
0.0
1.0
1.5
2.0
2.5
3.0
0.0
1.0
1.5
2.0
2.5
Running time (s)
(c)
Running time (s)
10a
10
10
10a
10a
10a
10
0.5
1.0
1,5
2.0
3.0
Running time (s)
Figure 6: Testing results on the impact of the parameter Qx in NBOO (BFGS) in the toy example. (The NBBO (BFGS) parameters are the those in Figure D except for Qs. Additionally, Qk = ws means that Q min(k + 1, 60), where the warm start strategy is used for ug.))
AID-TN: The maximum number outer iterations K 5000, the number of inner iterations T= 1, the TN iteration P = 1, the inner step size is 3 = 0.01 and the outer step size is 0.2.
AID-BIO/AMIOOCG::
The maximum number of outer iterations is K 5000, the number of
inner iterations is T = 1, the CG iteration P 1, the inner step size is B = 0.01 and the outer step size is 0.2.
PZOBO:
The maximum number outer iterations 5000, number inner iterations
is Q N 10, the parameter μ 100, the inner step size is 0.01 and the outer step size is
0.01.
NNO (SR1): The maximum number of outer iterations is K = 5000, the number of inner iterations 6, the warm up iterations = the number of iterations is Q2 25, the inner step sizes are 3 0.1.7 = 1, the initial matrix is H, I, and the outer step size is = 0.4.
NBO (BFGS): The maximum number of outer iterations is K 5000, the number of inner iterations is = 15, the warm up iterations P 1, the number iterations Qj = k + 1, the inner step sizes 3 0.1.7 = the initial matrix is Ho 7, and the outer step size is 0.1.
17

---

Published as a conference paper at ICLR 2025
C.2
FURTHER SPECIFICATIONS FOR LOGISTIC REGRESSION
C.2.1
IMPLEMENTATIONS AND HYPERPARAMETER SETTINGS
This section introduces the specific parameters of different algorithms used in the logistic regression experiment, formulated as bilevel problem:
exp(x)
min
Σ Midy (x)) s.t. (²) = arg min ZER
Σ eaa EER
11yl
(11)
2
where (at, b.) E Drain and (d., B/) E D vat are the training data and validation data respectively, and Eaa; bi, y) = log(1 exp( b.a," "y), The LL variable y the model's parameter, while the UL variable refers to the regularization hyperparameter.
In this task, we consider two dataset, 20news and Real-sim. The 20news dataset Lang 1995) comprises total of 18,846 samples with 130,107 features. It is divided into three subsets: the training set Perain has 16961 samples, the validation set Peal has 943 samples, and the test set Prest has 942 samples. Similarly, the Real-sim dataset (Chang & Lin) contains 72,309 samples, each with 20,958 features. This dataset is also split into three parts: the training set Dtrasn has 65078 samples, the validation set Det has 3616 samples, and the test set Drest has 3615 samples. For all algorithms, we set zg to and yo to a random value. Unless otherwise stated, the batch size of algorithm is assumed to be 200. In following, AMIGO refers to the algorithm AMIGO (Arbel & Mairal (022) that employs stochastic gradient descent to solve the auxiliary quadratic problem.
BOME: The maximum number of outer iterations is K 200, the number of inner iterations is = 10, the inner step size = 0.01, the outer step sizes are & = 0.1 and Ey = 0.01. The update rule for 0 is:
b = max 0.5 uks) (VF( yk). Vi(Zk, va))
VQ( 11:)1
F'SA: The maximum number of outer iterations is K = 2000, the number of inner iterations is = 10, starting point 20 yoo inner step sizes " = at 0.1, the initial multiplier Ao 0.1, multiplier increment & = 0.0001, step size ratio & = 1, and the batch size is 1000.
SABA: The maximum number of outer iterations is = 20000, the initial point on = 0, step sizes 0% 0.125 and 3x 3 0.125, and the batch size is 32.
BSG1: The maximum number outer iterations K = 300, the number of inner iterations is T 10, inner step size B& 0.01, outer step size ag 0.01.
SHINE-OPA: The maximum number of outer iterations is = 30, maximum number of inner iterations is T 1000. The initial matrix Hg T, for more details see SHINE code [
NBO (BFGS): The maximum number of outer iterations is K = 50. the number of inner iterations is T
warm-up iteration steps = iteration steps Qi = 1, inner step sizes = 0.0001/(5 /(j + 1),7 = 0.1, outer step size selection strategy is the same as the SHINE-OPA algorithm. When the dataset the 20news dataset, the initial matrix Ho 0.17; when the dataset the Real-sim dataset, H, 0.017.
qNBO (SR1): The maximum number of outer iterations K 100, the number inner iterations
T 7, warm-up iteration steps P 3, iteration steps Q+ = 3, inner step sizes 8 0.0001
1). 7 = 0.1, initial matrix Hg = 0.17 and outer step size selection strategy is the same as the SHINE-OPA algorithm.
The maximum number of outer iterations is K = 1000, the number of inner iterations T 1, the CG iteration P inner step sizes 3 0.01 and outer step size 0.01.
ADD-BI//AMIGO-CG:
https: www.t http://:ttttuu..ccococccccccaaaa http://rraaaa//aaarrrree///////
18

---

Published as a conference paper at ICLR 2025
AMIGO: The maximum number of outer iterations is K = 1000, the batch size is 32, the number of inner iterations is T 1, inner step sizes / 0.01 and outer step size a = 0.1.
AID-TN: The maximum number outer iterations K 1000, the number of inner iterations
T 1, the TN iteration P = inner step sizes 3 0.01 and outer step size 0.1.
PZOBO:
The maximum number of outer iterations is K 5000, the number of inner iterations Q N 10, the parameter μ 10, the inner step size is a 0.01 and the outer step size is
0.03.
C.3 FURTHER SPECIFICATIONS DATA HYPER-CLEANING EXPERIMENTS
This subsection focuses on data hyper-cleaning to enhance model accuracy, using noisy training set Durain == {a, by ) and a clean validation set Dval- The goal is to adjust training data weights to enhance performance Dval. The task can be formalized the bilevel problem:
min eval (y" (2)) S.L. y (x) = arg min grraán (x, 9) + c|ly|13},
(12)
where eval is the validation loss on Dval and gtrain th ( b,, y) is weighted training loss with (xx) = Clip(æ, [0, 1]) and x E R In the experiment, both E(a;, b,, y) and eval are the cross entropy loss, with = 0.001.
Experiments are conducted using MNIST (Dngg 2012) and FashionMNIST (Xiao al.) 2017 datasets, with 50% of the training data corrupted by randomly assigning them sampled labels. The data is divided into four parts: training set, validation sets and 2, and the test set. The training set comprises 50000 samples, while the validation and test sets contain 5000 and 10000 samples, respectively. For each method, model training is conducted on the training set, with the tuning of hyperparameter using validation set 1. The LL variable y (W, b) denotes the parameters of the linear model with weight W E R 10x7884 and bias R10
C.3.1 IMPLEMENTATION AND HYPERPARAMETER SETTINGS
The initial point yo for all algorithms is obtained from a pretrained initialization model, and the initial weight vector zo 0.5e e 50000
BOME: The maximum number of outer iterations K 10000. the number of inner iterations T= 1, the inner step size a = 0.01, the outer step sizes & = 100, & = 0.01, and
0.11((TK: ma) (VF mn). VV(EK, V1(( VQ 1
A max
Details can be seen in the code
F'SA: The maximum number outer iterations = 7000, the number of inner iterations T the initial point 2g yo. the inner step size " Or 0.01, the initial multiplier Ào 0.1, the
difference multiplier 0g = 0.001, the step size ratio & = 10000, and the batch size is 2000.
10000, the initial point vp = 0, batch size is 2000. For the MNIST dataset, the step sizes ag 10, 8 0.01, S 0.1; otherwise, the step sizes ag 100, Bx = . = 0.001.
SABA: The maximum number outer iterations
SHINE-OPA: The maximum number outer iterations = 50, the maximum number of inner iterations T 1000, the inner stopping criterion V yk++ )I < 1 1/1000)), the inner step size determined using strong Wolfe line search, the number of extra updates the BFGS algorithm is (i.e.. upper-level information is introduced in the BFGS iterations for every 5 steps), the initial matrix Hn = 7, and the outer step size 100.
https://githhin
ROMK
19

---

Published as a conference paper at ICLR 2025
(NB)
QNBO(SRI) AMIGO
SHINE-OPA
SABA
F2SA
AID-TN
PZOBO
BOME
AID-BIO
(a) Test accuracy vs Time
(b) Test loss Vs Time
0.92
1.2
Test accuracy
0.90
Test loss
1.0
0.88
0.8
0.86
0.6
0.84
0.4
0.0
0.5
1.0
1.5
2.0
2
Running time
Running time (s)
0.840
1.0
Test accuracy
Wm
0.9
0.825
Test loss
0.8
0.7
0.810
0.6
0.5
0.795
2
10
10
Running time (s)
Running time (s)
Figure 7: Data hyper-cleaning two datasets. (First row: MNIST; Second row: FashionMNIST. All results are averaged over random trials. The exclusion of BSGI's 's performance this experiment is due to its ineffectiveness in addressing these data hyper-cleaning problems.)
NBO (BFGS): The number of iterations Q+ the inner step sizes 0.1, 0.1, the outer step size a 100, the initial matrix H, I. For the MNIST dataset, the maximum number of outer iterations K = 5000, the number of inner iterations = 7, the warm-up iteration count P 3: otherwise, the maximum number of outer iterations K 600, the number of inner iterations T = 47, and the warm-up iteration count P 33
GN (SR1): The number of inner iterations T = 17, the warm-up iteration count P 3, the number of iterations Qs = 3, the inner iteration step sizes 0.1, 7 0.1, the outer iteration step size a 100, the initial matrix Hg 0.01 In addition, the inner iteration will terminate early if | f 11ll)l < 0.1. For the MNIST dataset, the maximum number of outer iterations K 5000; otherwise, the maximum number of outer iterations K 2000.
ADD-BIO/AMIOO-GG:
The maximum number of outer iterations is K = 1000, the number of
inner iterations 1, the CG iteration steps P 1, inner step sizes 3 0.01 and outer step size 10.
AMIGO: The maximum number of outer iterations is K 1000, the batch size is 200, the number of inner iterations is T 1, inner step sizes 0.01 and outer step size a = 100.
AID-TN: The maximum number outer iterations K 1000, the number of inner iterations is T = 1, the TN iteration steps P 1, inner step sizes 0.01 and outer step size 30.
20

---

Published as a conference paper at ICLR 2025
PZOBO:
The maximum number of outer iterations is K 5000, the number of inner iterations
is Q = N = 10, the parameter = 0.01, the inner step size is a 0.01 and the outer step size is 10.
C.4 META-LEARNING
In this subsection, we consider the few-shot meta-learning, which can described as:
min 1 Σ Co. (z, (x)) s.t. y" (x) arg min Σ Cs. (z, 9.),
where CD. (2) yf) LEED, ((: is the validation loss function and Cs, (2, 31) 18.1 Eses, (C(x, E6:E) + R(y))) is the training loss with the classification loss L and the strongly- convex regularizer R(y;). the experiment, L is the cross-entropy function and R is the lz norm. In our experimental setting, the task-specific parameters y denote the weights of the last linear layer of a neural work and x are the parameters of a 4-layer convolutional neural networks (CNN4).
The few-shot meta-learning has tasks {T,, i 1.... ... task T, has loss function ( ya: E) with data sample ç. the spec-scccific parameters ys and the parameters of an embedding model shared by all tasks.
m3 sampled over distribution Py. Each
50
49
48
46
Tost
43-
@NBOOBFOS)
42
41
100
200
300
400
500
600
700
800
Running time (s)
Figure 8: 5way-5shot on FC100 datasets. Results are averaged over runs, with all algorithms starting from the same initial point with test accuracy of 20%. For clarity, graphs begin at the second data point, omitting the initial one. We report that qNBO (BFGS) reaches peak test accuracies within 800 seconds, after which performance declines, likely due overfitting other factors.
C.4.1 DATASETS
minilmageNet: The minilmageNet dataset (Vinyals et al. 2016), derived from ImageNet (Rus sakovsky al. 2015), is large-scale benchmark for few-shot learning. The dataset comprises 100 classes, each encompassing 600 images of size 84 84. Following Armold et al. (2020), we partition the classes into 64 classes for meta-training, 16 classes for validdaiia,,,,, and 20 classes for meta-testing. In the experiment, CNN4 has four convolutional blocks, in which each convolu- tional block contains 3 convolution (padding=1), ReLU activation, 2x2 max pooling and batch normalization. Each convolutional layer has 32 filters.
FC100: The FC100 dataset (Oreshkin et al.) 2018). generated from Krizhevsky & Hinton (2009). consists of 100 classes with each class containing 600 images of size 32. Following Oreshkin et al. (20T8), the classes are split into 60 classes for meta-nraining, 20 classes for validatinn,, and 20 classes for meta-testing, Each convolutional block of CNN4 comprises a 3 x convolutional layer (with padding set to and a stride of 2), subsequent batch normalization, ReLU activation, and 2x2 pooling. Each convolutional layer has 64 filters.
Omniglot: Comprising 1623 character classes derived from 50 diverse alphabets, the Omniglot dataset (Lake et al.) 2015) contains 20 samples within each class. The classes are divided into three parts: 1100 classes for meta-training, 100 classes for mata-validation, and 423 classes for meta-testing. The CNN4 network is identical to that used the minilmageNet dataset but has 64 filters per layer.
21

---

Published as a conference paper at ICLR 2025
C.4.2 EXPERIMENTAL SETUP
The meta learning experiment is carried out using the code available at the website At each meta- iteration, a batch of 16 training tasks is sampled and the parameters are updated based on these tasks. The max outer steps K is set 6000 for both algorithms. The initial parameter yo is selected O.
PZOBO: The parameters involved in the algorithm are the same as those Sow et al. 2022by.
QNBO (BFGS): For all three datasets, the inner steps is set to 20, the hypergradient updates Qx is 3, the step sizes / and are both specified as 0.1, and the Hessian matrix is initialized as Ho = 0.01 In addition, the inner iteration will terminate early if || ||b|| < tol, where A and are the components of the parameter y denoting the weights of the final linear layer in neural work. The specific values of tol and other parameters can be found in the code provided in the supplementary materials.
T-100
0.9
0.89
Test loss
0.8
0.88
0.7
Test
0.87
0.86
0.5
0.85
0.4
T-180
T-10
0.84
0
5
10
15
20
25
30
0
5
10
15
20
25
30
Running time(s)
Running time(s)
Twi00 T-200
T-100 T-50
Tw30
0.835
Test accuracy
0.830
0.9
Test loss
0.825
0.7
0.6
0.815
T:200
1::00
10
Running time(s)
Running time(s)
Figure 9: Ablation study on the iteration number T of NBO (BFGS), (The first row illustrates the test accuracy and test loss for MNIST, and the second row shows these values for FashionMNIST.)
C.5 ABLATION STUDY
C.5.1 TOY EXAMPLE
In this subsection, conduct ablation study to assess the impact of the parameters Qk the performance of the qNBO (BFGS) algorithm the toy experiment. As illustrated in F the setting Qs 1 + 1 outperforms the others. Furthermore, employing the warm start strategy for u, (denoted as Qx = ws) enhances the performance of qNBO (BFGS), suggesting the potential benefits of this strategy.
22

---

Published as a conference paper at ICLR 2025
C.5.2 DATA HYPER-CLEANING
In this subsection, we conduct an ablation study to assess the impact of the parameters and Qu within the qNBO (BFGS) algorithm on its performance in the data hyper-cleaning experiment. As illustrated in Figures 9 and 10, smaller values of T and Qx lead to improved performance in terms of both accuracy and loss across the two datasets, thereby indicating the efficiency of qNBO (BFGS).
0.92
Q-20
Q-5
Qm1
Q-10
Q+2
0.91
0.9
0.90
0.89
Test loss
Test
0.6
0.86
0.5
0.85
0-220
0--5
0-1
0.84
0-110
Q-2
10
15
20
25
5
15
20
25
30
Running time(s)
Running time(s)
0.835
Test accuracy
0.830
0.9
Test loss
0.825
0.7
0.820
0.815
Q-26
Q-4
0.5
0
5
10
15
25
30
Running time(s)
Running time(s)
Figure 10: Ablation study the iteration number Q of qNBO (BFGS). (The first shows the test accuracy and test loss for the MNIST dataset, and the second row shows the same metrics for the FashionMNIST dataset.)
D PROOF OF THE RESULTS IN SECTION 3.2
D.1 RESULTS OF QUASI-NEWTON METHOD
In this subsection, we first summarize the convergence properties of BFGS method for solving the problem:
min g
(13)
yER"
Besides, to derive the upper bound of the hypergradient estimation error, review some conclusions of BFGS update presented in Jin & Mokhtari 2003); Rodomanov & Nesterov (2022 2021b).
D.1.1 CONVERGENCE RESULTS BFGS METHOD
Assumption D.1. Assume that g has the following properties:
(i) ( is strongly convex w.r.t. y with parameter μ > i.e., μul - v²g(y). Moreover, g (y) Lipschitz continuous w.r.t y with parameter L > (i.e. V² Ll).
(ii) The Hessian V2g(v) satisfies:
V V9g(n)) V²9(z2) 3 Mlln vzll= V Vy,, U2, 2, R
23

---

Published as a conference paper at ICLR 2025
where 1vll= (z)(,))))) and M 0.
Lemma D.2. Rodomanov & Nesterov (0221)) Global convergence) If the function has the following quadratic form:
gly) - Ay Au v²
(14)
where pl A 3 LI such that Assumption D.1 holds. If the BFGS method is used solve the problem (13), and if Ho = LI and the number of iterations 2 4n In to then for all i 2 4n In t. the following inequality holds:
11 v"1l - 2x ( 1800 v²ll
(15)
with 1.2 and to 4nlu
Lemma D.3. (Rodomanov & Nesterov (0021)), local convergence) Suppose that Assumption D. on holds. If Ho = L1 and the initial point satisfies:
11:0 10 S K1 Ki = 21n VL
max
(16)
3 Mμ
2L Ko + +
where Ko = 8rln 2L and 2 Ko, then for all 2 Ko, the iterate generated by the BFGS algorithm has the following superlinear convergence rate:,
11 - 101 - 2x 3/2
1800 - y'
(17)
with to 2 Kg and K
Lemma D.4. (Theorem Ji & Mokhtari (2023) Suppose that Assumption D.1
holds. If the initial point yo and the initial Hessian approximation matrix Bo (with Ho Bo satisfy:
(o'00")'1 y²'ll= 6'
(18)
[V'g("")~11 (Bo -(o"" S
where e, E (0, p) E (0,1),
(3 + cJe
(1 (1 - p) S 8, and 28 S -1)20)p
then the iterate generated by the BFGS algorithm has the following superlinear convergence rate:
L &CioVi+ C2)21100 y"1l.
IIu - v01l s $V
(19)
where C = 202222211111 p) + 5), C2 3(1-p)
(1+
and q
1-26
To be specific, the superlinear convergence rate of BFGS algorithm also be expressed in the following alternative form.
Lemma D.5. (Corollary 4 Jin & Mokhtari 2023
Suppose that Assumption D.1 on g holds.
the initial point and the initial BFGS matrix B, satisfy:
1
| pl 1/2 -y"")) y²)ll ك 300
(20)
| (B-
7
then the iterate solved by the BFGS algorithm exhibits the following convergence rate:
L [ 11 w² 11-
11 ~ <
(21)
24

---

Published as a conference paper at ICLR 2025
D.1.2 PROPERTIES OF THE BEGS UPDATES
Lemma D.6. If the function g in the problem 13 has the following quadratic form:
s(u) = 2 Ay y²x, x.
(22)
with μl 3 A 3 LJ, then the BFGS matrix B; satisfies:
BBs: - As;)= (Bis: Ass) nL sf B;s;
S P
(23)
Proof. Define o; = o(A, B:) (A- A) (B. - A)) 2 0, then
(A,, B.) (A, B141) (A-), - -B
(B, AB,A-1 BB,8,, (B,A-BBB8,,,85)) 81)
(Biss, 82)
(B. (A- -B: Biss;
(24)
(B,s;,8))
( A)A-1(B;
A A)8i, 88)
(B,8i, 82)
where the last inequality follows from the fact that
ABA A)
B,A 1
2B; +A
A-B, z B;A-1 - B,
Thus, is derived that
(B, AB, s)s
0:41 2
VO -
(B:8;,8))
Finally, summing the above inequality over yields:
(B, A), A)ss, Si)
- - -1) A)
(Bis,, si)
< A L -
-
-1 T2
A
11
11
Definition D.7. Define
(AA & (A-1, G A) De
(25)
where Det denotes the determinant of the matrix.
Definition D.8. Define
(, :- {BB A)A A)u, u) 1/2
(BA-1Bu, u)
and let 0 (-1, + IR be the univarite function:
8(t) : In(1 + +t) 0.
Remark D.9. On the interval [0, +oo), (tt) satisfies:
t²
$2
2 0(t) <
(26)
2(1 +t)
2 2+
25

---

J Published as a conference paper at ICLR 2025
Lemma D.10. Rodomanov & Nesterov (021b), Lemma 5.2) Define Jj := So g + ts;) dt
and Vi+1 + Then, J.8: = Vg(Ui+t) Vg(ui). If Bo L.I, then vi 2 0. the BFGS matrix B, satisfies:
L Vgy(y)) 3 B; 3 E v g(vi),
(27)
Jj 3 B: 1 Li+1 L J p
(28)
Si+1
where : ||sillgs & =- M Ej-orr
1) and the strongly self-concordant constant M of
Lemma D.11. When Bo = LI, the BFGS matrix B, satisfies 27 and
28
If =
max E1+1 S
i=0,- .k-
2 in 28 then the following inequality holds:
K-1
$
0 S n
-
A.
(29)
11
1=0
1=0
where 2((
OJJ,, B₁, u4), t/: = (Ji, B,), te41
(JJ, B1+1). and A.
Vi+11 1-+11
Proof. Note that
Ei+1 L E1+1
1 1 B: 1
(30)
1
From Lemma 2.4 of Rodomanoo & Nesterov (2022), can be further deduced that:
v/ V 2 1
0g
(31)
E++1
Since = max Ei+1 S 2, it follows from the definition of 0; that:
i=0... (=0,....-1
0f (B: - J,)J, J.Yus, us) =1 ((2B, J..uu, uz)
(32)
(B:J, B,u, u.)
(B.J, Bau;, uz)
Then, it is derived that:
c 8?
26
1
Bi
2
0¹ =
87.
(33)
E1t1
2 [1 (1++0001
0:)
2 (1+
1
2 ( + Ei+1)
Thus, it holds that:
E0? w/ 0.41 1/. -1 A,, vi 1),
(34)
where E =( and
A 1h41 Jen (J J B.t1) In Det(J (J+1).
(35)
26

---

Published as a conference paper at ICLR 2025
By summing equation
34
over i and given that thx 2 0, it follows that:
0 S
400
A S 40
+ Σ
A
=
1=
==0
(Jo,
LI)
Σ
A
1=
A-1
-Jo LI Jo) In Det LI)
Σ
(36)
S (Jo (J,,II LI
Jo) + Σ A
L
$ (J01
-J
Jo) +
4
1
L - + Σ
k-1
n
A.
Notations: step of Algorithm 2 y/ establishes the initial value of y at the start of the k-th iteration. After P warm-up iterations, denoted as yk.u y the term yk. refers the state of y following 7 further iterations with fixed. In the second step of Algorithm I Qu represents the state of after Q+ iterations, with both æy. and yk++1 fixed.
D.2 PROOF SKETCH OF THEOREM 3.7
The proofs of Theorem 3 and 3.7 encompasses three critical steps: first, splits the hypergradient approximation error into the T-step error of estimating the lower level solution | - v/ll and the Qs-step error ||ux,Q, - "E'l 2 second, it establishes upper bounds for these errors based on previous iteration errors; finally, it combines the above results to substantiate the theorem's 's convergence. Since the proofs Theorem 3.4 and 3.7 are similar, we only elaborate on the proof sketch of Theorem 3.7 below.
Step 1: Decomposing the hypergradient estimation error.
First, the hypergradient estimation error at the kthh iteration can be bounded by:
L3 Cf
[[((())) (2x)) = 3(13, +
11
vill 3.M,, 1uu.. - u (37)
Step Upper-bounding the error.
The T-step error of estimating the lower level solution
|| - yī is bounded by:
luvt 0 s T rlyvã_1 1k-11r + 2(1
nn( T
)T(( 3p4 [V
3/) 12a nLM? Joy C7, 1 1 (
(38)
12(1
- | )²²((
1²
12 02
4M² 13
4M7 Cz L2
where = -n(e)=
P (00)))(((11))))))))) (11+))+6(1+ 2) (LP P.
+
)).
a2
The Qt-step error u4.Q= uill is bounded by:
nLC2%
122
C2 L2
|ui - < E/2Qx
+4
110k - T1
(39)
112
27

---

Published as a conference paper at ICLR 2025
Step 3:
Combining Step 1 and Step 2.
Combining
37 38 and 390. the upper bound of the hypergradient estimation error is derived as:
[V0(T)) V (2xx))
607 wa 2
(
1=0
nLM?
C
nLM C2
+ 6wex
Jzy
+
Joy
Qk-1-j
130EQ
j=0
with
D L CF
4M²
D3
4M2, CF Jag
80 = - (1-)))(()
Jov 112
F.
Joz >11b 30ol2
1
14
and
12 Cj 1xn 12
4M3 1.2 Jan n22
4M², C2 7. Jay
= 6(L +
P.
= -1 P 1d )(1
Due to the La-smoothness of o the final convergence result can be proved.
To prove Theorems 3.4 and 3.7 we first present the following lemma.
Lemma D.12. (Lemma 2.2 of Ghadimi & Wang (018)) Under Assumptions
3.1 and 3.2 we have:
For all x,
where (x;;y)) [VF(z - [F yl1, - VV Vy v) and C LF.
LRy Mi + OF
[15xx + Liv M
y (x) is -ippchhit continuous in x:: lly (x1) y" (122)l < L,]|æ1 xzll.
Miax
where Ly
v is LapLipschitz continuous in x: [V (xxx2) S Iuplar sall. where La (L) + LF. + CF,, (Lean Cre + L Live Mesu
D.3 PROOF OF THEOREM
Lemma D.13. Suppose that Assumptions 3.1 and 3.2 hold. The error between the approximate hypergradient (x((x) and the true hypergradient in Algorithm can be bounded by:
L2,,,, C7,
[V v<(2x)) $ 33( +
1lyKT yEll 3M, fzy 1lux ugl1
(40)
42
Proof. Let ut 2 f va)l v Fzzk, vk), then
[)0()))) (#x))1
V. F(KK, Vk.r)
V2 (IK, yk.T) )1² Un,Q. (V. 222 fax, (rx, vi)1 u1;))
= -I/V, A. F( WK,T)
F (rx: vir) - ((V2 ([V2 (F Uus.e. - 2 (xx, v TT)))
=IIV,, v. F( VK.T) V Flrk; Vir)
- 2, (IR, )) U..Q. V2y Vr. TT ((V2 (1 (xx vill" - V (x Vr,T) u())) 1?
= V| F (I )V.T) F(rk, Vir)
IV2 2 J (IA, )) ( (1.... -u²) - (IV2 by (1x. - 1V2 ( u
<3 F(IK, Mk.T) VzF' 21l 3|| 3/ 2, f yrrT) (IT) w
+ V 2 MK.T) - V2y fxx,, v 1|?
28

---

Published as a conference paper at ICLR 2025
Based on Assumptions 3.1 and 3.2 it can be derived that:
[V - (xxx))
CR, 1k
<3L 8KiT ylll + +3M
|uu. u111 +3
-fll
412
L,, C7 1lyk. vil12 3M,,,, 1/ uiel?
=3 +
n
Lemma D.14. When the qNBO algorithm (Algorithm 7 is applied to solve the problem 7 if the LL
objective function f takes the quadratic (22) and Ho (1/L)I, holds that:
CF. 1
nLQx
Σ
|A-i F -k,ill
with Qk >> 1.
Proof. From Lemma
D.6 it follows that:
A y (IA: M6+11 - WH. A(A V. F U1++1) ug..))
u/[ B
Q
(A V (Ikk Mc+1) - uk.i) ACTAAAATT F FZ yk+1) uk.s)
V. F (0 B V. (TT, Wi+11
nL
with Bg. = H
Since μT 1 A < LI and A < BE < 1.2 A, we have:
Qx 1 A FIK,, 2k+1) u1
nL 1
(o 111
Since || F(r Me+1))l S CF,, it can be further derived that:
Qx
n..CI. F.
A V y (# 31+1) uk, <
(41)
113
Finally, by applying the Cauchy-Schward inequality, we can deduce that
CF
nLQu
| V F (1rk, Bk+1) u
(42)
/ 1
Lemma D.15. Choose the parameters 3 and such that (1 - B1) Plyxk - Vill S 300 and ensure
Ho satisfies: f y (Ix) 1/2
H (H, V2 Viny f y" (xx) 2 (I 1/" (xxx)) 1/2 | S 4.
Then, under Assumptions 3.1 and 3.2 holds that
livt VK.T S (1+8)m(
- (1--81 U1 Vi 11 (1++(1+))+(( (1--3))
( " 1 |0
12
(43)
with positive constant
29

---

Published as a conference paper at ICLR 2025
Proof. Under the setting of parameters B, P and Ho, the condition (20) is satisfied. Furthermore, based on Lemma D.5 and the fact that yk,o = yk and yk = yb. it holds that:
1 1ykTT vil? I 16(, (T ) vil? I kg( G ((1 3x) llue vtll?
where & = I. Finally, since yı = 1,,,, using Young's inequality yields:
lyK.T vtll < (1 + F)m( + (T(1 -Bp)
111--111 11p)
ve-1ll 11 + (1 + nns( 7 ) (1p) 31))111k111 viel
S {1+ b T Bu) Bu))P1lm--1 11 1i=1 (1 + - )m( )T(( -Bx) 1| L 2xx11
where e is a positive constant and the last inequality follows from Lemma 2.2 in Ghadimi & Wang (0188).
Lemma D.16. If the LL function f takes the quadratic form and T 2 th, under Assumptions 3.1 and 3.2 it is derived that
1u Us,T|1 S (1+E) 19- 11-1112 - )cg ( L2 xx- 113 (44)
with to 4n and positive constant E.
Proof. From Lemma D.2 if 2 to. it holds that:
1IuET - vtll S (F 1 1yy,o I11E, - will?
where c, 2t, Furthermore, since ykoo yk-1,7, using Young's inequality yields:
y 1 - vi-i 12 + (1 + )e 1 yr >'vl vkll
Ivv.r Del 1 < (1 + =)c
T
$ (1 + e) ( 11 12 + (1 +
Jot [ - =xxl?
(T)
where e a positive constant and the last inequality follows from Lemma 2.2 in Ghadimi & Wang (0118).
Lemma D.17. Choose the parameters 3. P such that (1 - P1) - sill I Ki, and Ho = LI, under Assumptions 3.7 and 3.2 it derived that
1 vū-1 7 (1 ( - 11
llvt - < (1+6)
(45)
with positive constant T Kg. Kg 8nln 2L a 21
Proof. From Lemma D.3 if 2 Ko, it holds that:
lluLT vill S &2 ( ( IIv.o )
vill S & ( (1- 110
122
where ai -t Furthermore, using Young's inequality yields:
llve. 2 < (1 + c) 3p)
1 ( 11llllll11 1 + (1 1 (1 (
(,) )
vil12
1 -ib--IT--E-- + (1+ xxx Bp) $ (1+ +1++scnx+ B4) (-)
x - 2x 1
T
where s is a positive constant and the last inequality follows from Lemma 2.2 in Ghadimi & Wang (008)).
30

---

Published as a conference paper at ICLR 2025
Lemma D.18. (Error of uk, Suppose that the lower level function has the quadratic form and Assumptions 3.1 and 3.2 hold. If uk. Qu = [i and
Uk argmin||A- - (a 3k+1) ux.ill.
(46)
then Qs 1, the following inequality holds:
nLCz
D3
UuxQ uill S 2
Fv
+
Fu
lu - yk.T11
(47)
n²Qu
Proof. From Lemma D.14
we have:
n..CB.
||A V F( Uh+1) ū
(48)
10Qu
Moreover, under Assumption 3.1 and given that Uk+1 Wk,T. it holds that:
|uu.Q. - - $ 2| uk
1
v (ITK uk++))l2 + 21
F(xx, 0k+1) A V F(t.
nLC7
L2
<
Fg
11y y2,T11
11 xQx
1
Theorem D.19. (Restatement of Theorem 3.4 with full parameter specifications) Suppose that the function I in 7 takes the quadratic form:
f(x, y) = v² Ay yf x.
(49)
2
where pl < A 3 LI such that Assumption 3.2 holds. Choose the stepsize > 0, the positive
constant E > 0, Ho LI and T 2 to (t, 4nlnk) such that
< 1 and aLı + wa? (1 *aLx) 1-7 4'
< 1
where GR 2M?
+ =) 6(1 3) (L3 +
L7 C2a
2017 1
Fx 6(L3,
)).
12 C3 n2 and 3.3 the iterate generated by the qBOO (BFGS) algorithm (Algorithm 7 has the following
1/
)(1 (t) == 1 and c 21 Then, under Assumptions 3.1
convergence rate:
K-1
4(0(20) [V
$(x'))
38p
1
K-1
18mLM? Oz
Σ
129
(50)
aK
K(1 - 7)
K
1²Qu
k=
L3 L. c2
2M L3 11²
with the initial error dn = (c) (L3
+
1l16 yoll2. Specifically, if
Qs = k: + 1, we have;
K [+ 4(0(20) inf, f(xx)
18nLM3 J., C.A.r,_C.,n1 In
350
+
(51)
aK
K(1 -
Proof. Substituting the inequality (47 into (40) yields:
L2
C
())()z) v 3(1 +
Jep
IlyeeT 2ill2
122
LL
L2
+ 3M² (2
+2
2
11y1 - Vk.2rl1
1 Q2
122
(52)
3L3 Jan Fy
6M? L2
< (3L% F.
+
+
llvE yk.r
122
n2
nLM? 1zy
C2,
+6
31

---

Published as a conference paper at ICLR 2025
Then, by plugging the inequality
52)
into
44
we obtain that:
Vi 11 + 2(1 + - ) (
1 T L2 V2(I==1)1
llon U1,T11 - (1 + E) T
|1kk 1T
+ 2(1 + 1 | 3
T 1. (0x - V (3x 1)1
8
< 51lvi-1 yh 1. || 2(1 + 1
1,00² |
+ +12(1 + 102k2 {
1
1 L2a nLM2 Joy
Oz,
T
p²
(53)
1/ oz
2Minn 122 ))
where 7 == C2 ((1 + +) 6(1 + 2) +
+
#²
By telescoping 53 over k. it follows that:
1-1
l1 - 11, -u,-11 S ~180 yo.r + 2(11 + Jegnn 1
2
Σ
7"
T
j=0
12(1
1 )62k20
1 ( T
nLM? C₁.
Jay
Σ
k-1
13
Qk-1-j
j=0
Combining the inequality that
522 and 1l uo S en ( (1) 11:8 Vo we can further derive
k-1
wa (V0(z)) - (xxx2) S 607
2
Σ
1=
(54)
mLM?
C²
nLM? PF.y
+ Ewex²
Jay
+ 6
Jay
13
Qk-1-
1²Qu
1=0
with 8y = 3c) (L2 + L. of 2M1 12 2² [[1 +) (+) L2
12 2M
11:6 - y0,oll and w = 6(L2 + 12 of
Since vT6()) is linciiiiicchtt continuous (Lemma 2.2 in Ghadimi & Wang (018)), we have:
$(<++1) < + (V - xx)) + L
| - 1x
2
S (xx) a -
FT(x))) (xx))) - +
(55)
+ L. [ - {1(1))11
< <(x))= ( - d²Lo |[
a
a + a² Lo) |V - (.
+
2
Using the inequality (54) it holds that:
Φ (xx+11) {T()))
(x a² L.)
|| +
a + +a² +ooLo) |[ {+(+))1
2
<T(Tz)
a² Lb)
| +
+ a a Lo 607
2
k-1
6nLM?
J2y C2 (56)
+ w 2
(
a
+ T²T.0
Σ
7
|
(
a +
( + ar
100
1=0
nLM?
C2
k- 2
+6w
+ a² a²2L))
a
Jzy
2
43
Qh-1-j
f=
32

---

Published as a conference paper at ICLR 2025
Finally, summing the inequality (56) from ls to t = K - 1 yields:
K-1 [+((=)) =
a. TT
(((x) + ( a² T²o)))
2
1 1-7
K-18-1
+ wa? (5 + LZ2LB)
k=0 1=0
(57)
NLM C2
K-1k-1
+ 6w
a
+ +
Fg
ΣΣ
2
n
Qk-1-5
k=
k- 1
GnLM C₁. Iry
a LiB
2
m3Qu
k=0 0
Furthermore, from the inequality
Σ
k==0
K-1 k-1
11
S
Ek=o aKk 2j=0
K-1 bj. we obtain
K-
K-
K-
V
k=
k=
K-1R-1
K-1
K
K-1
Σ
Qx Qk-1-j
Q
D
k=O ==
k=0
k=0
k=0
Thus, we can conclude that
11
K
2 ala wa2
a
[+(())))
2
1-
K
k==
((10)= - ((Ex)
80
+
+
+abg
(58)
aK
2
TT
1
K-
GnLM
C¹.
6w (1
1
K-1
nLM?
C2,
+
2 + aabo))
lsn
+ 1-7 +
abo
a
Jay
K
1²Qu
K
u²Qu
k=0
k=0
Moreover, if aT. wa? ( +aba)) 1-r S 7. then
1 K
Σ [+*x))1 4(0(20)) - ((x)))
38p
1
K-1
18nLM?
(59)
ak
K(1
7)
K
10Qu
where (xx') inf, (xx). Finally, Qx + 1, then (11) is established.
Next, we consider the case with warm-up steps and provide the corresponding theorem, which proves to be similar to Theorem D.24 detailed proof is not provided.
Theorem D.20. (Warm-up for quadratic f') Suppose that the LL. function f in 1 takes the quadratic form:
f(x, v) = = Ay yfxx. x.
(60)
where pl - A = L1 such that Assumption 3.2 holds. Choose the stepsize 3 and warm-start iteration
steps P such that (1-3)p (4)) Ilyx v S /t and ensure the initial Hessian approximation matrix
Ho satisfies: f yn (xx)) 1/2 (11 V f y² (xx))) of (Ir, ya (xx)) S 4.
Choose the stepsize a > 0 and the positive constant & > O such that
1
1
T <<> and alg + wo 3
- +Tb
2
1-7
33

---

Published as a conference paper at ICLR 2025
where (1 - 3p) ((1 E) + 6(1 + 1) + Ling
2 Lin
(p)
1eyy Cr
+ 2M 12 )(1
6
and K x= 4. Then, under Assumptions
#²
3.7
and andd3.3)
3.3 the iterate generated by the qNBO (BFGS) algorithm (Algorithm) 7
has the following
convergence rate:
K-1
Σ O
4(8(20) +(x*))
36p
K-1
18ILM? C
119
(61)
K
aK
K(1
K
10Qu
k=
L7 Ct
Li 2M
with the initial error 50 3x( - (T.F +
11126 yoll?
D.4 PROOF OF THEOREM 3.7
Proposition D.21. (Example 4.1 of Rodomanov & Nesterov function f is p-strongly convex w.r.t. y and its Hessian is Livv" Lipschitz continuous w.r.. Then f is strongly self-concordant with constant M
(021aa) Suppose that Vx, the LL
Lux p3/2
i.e.,
f y1) V2 by v2) M y1 yella V of w) Vy 22, 2, R..
where |lyl|a = (y ( =)y 1/2
Proof. Using the Lipschitz continuity of the Hessian, we have
v fx, fz, v2) N L 1l -y2ll (Veg 23 -222 - 1/2
3 Liv
n//2
L 1/2 1lya vell=T
Lrsu
11 - y2l1= V? 5 fxx, w): 13/2
where the second and the last inequalities follow from the fact that pl V2 Vyr v). This demon-
Lige 2312
strates that f is strongly self-concordant with constant M
Lemma D.22. If the Assumptions 3.1 andd 3.2 hold, then uas generated in the step 2 of the Algorithm
7 satisfies:
Q
nLC? F
2 f (ox, 3k+1) VV Vyy F(x,, yk+1) uk
(62)
Eu3
where Qk >1
min
and & nf Ejed slgbbbbeei.
i=1," Q. 2((++;))
Proof. Note that in Algorithm 3
J;== = f Vi Vay (Tk, Bk+t + (8i) dl, J++1= = ('' VeyllEe. Be4t + +1841) dl,
with s, S.HR, F(rk, 1k+1).
When the step size çi is chosen appropriately, based on the definition of Jj and the properties of f stated in Assumption 3.2 be concluded that J; is nearly equal to J.41, i.e., A, x and II J < LI. From Lemma D.I1 follows that
F Mb+1) J FFF((K, Vo+1) uk.)) nL
(63)
V Fx 2h 1)th J. V V, (IH.
Eμ
Since μuī 5 J; 3 LI, we have
Qx Mlll F(.., - u
nL
<
(64)
V
Eμ
34

---

Published as a conference paper at ICLR 2025
Moreover, it follows from Assumption 3.1
nLC Enr
Vy Me+1) uk 1|2
If the parameter M of function f Çrug, is sufficiently small, Jj can be considered as approxi- mation of V of Wk+1). Therefore, (J,, B,: u,) can be used to characterize the upproximation between Hf and of (xx, (x+1)]=1 along the gradient direction V V yk+1), i...
nLC? F
Σ
2 of f vk+1) (k+1 V F( yk+1) uk,ill²
(65)
where Ç min
i=1,- Qs 2(0+45)) and & M Ejzó Kysmslllee
Lemma D.23. Suppose that Assumplion 3.2 holds. Note that uk+1 Un,Qu in the step 2 of Algorithm UR. = Us with
Uy == argmin V By
fæk, 9k+1)
F 0k+1) uk
(66)
then
n.Cr
T.P
C7,
|us.Qu - -
F
+
+
1lut Vu.T12, 1,
(67)
3
112
1e
where
& min im1.". Qu. 2(E)+E() and &
M Σ}=b
Proof. Combining Lemma D.22 and the definition of üg yields:
nLCg F2 EN3Qk
Ny (I 11+1 F(rk: v1+11) "*
(68)
Under Assumptions
3.1
and 3.2 since yk+ 1 yk, it holds that
vy (I 11++1 y (II 11+1)
4 vy (ark) v VV y 11211
vy (T)k, 11+1
V F (Tk, Vk+1))
V 22y (F wk+1)
(K Vi 1l? V f (I vkr (Ik: vEll
+ 2| 2 yy (0k, w/++1
v y (rkk vir)
1
2
1 Mk.T 1 + 207 2 I 91+1)
V (Irk, 1ih)
112
12
<2
11
1
(69)
112
+ 2C
V
(Ir,, 31++2) 112 2 (fx, (1-1) V2 f (xx.)())) 1 2 (#k, vi)
F,
22
C². L2
1
V +
llvi - 11
112
1²
1
C2,,
Syv
llvt 11.
112
44
Finally, from Assumption 3.1 and the inequality (69 it is derived that
[u.qq. 2 <2||um
V 1 VV Fæ 2112
( [
1k+11) -V F(rk 11++1) 42 (xr, -V "
nLCz
C2
L3
< 2 Py
+4
Pi
+
F.
ll y1.T11?
En3Qu
112
(70)
35

---

Published as a conference paper at ICLR 2025
Theorem D.24. (Restatement of Theorem 3.7 with full parameter specifications) Suppose that
Assumptions 3.7
3.2 and hold. Choose the stepsize 3 and warm-up iteration steps P such that
(1- -B4)) 11yk-
Vi. S / and ensure the initial Hessian approximation matrix Hn satisfies:
J V² (2x)) (x=x))-1/2 -1/2 1
[ V" (Ix)))
(II:
y (xx)))1122) S +. Define
1.
Cz
4M3,
n 1/2
4M3
C2 CB, (mm) and
<( ( ( Bu)² ((1 + +,) + 6 + (L +
+
6(T,2= + 1), Fv
am Li / CF Live
)(1 ))²{
F Bui) P2 Choose the
1²a + 1ra
stepsize a 0, the positive constant & > 0 and iterate T such that
<< and als + wa² 2
1
+
-
1 .
2
Then, the solution Ik generated by Algorithm I acchievss the following convergence rate:
K-1
[V((2))1 v 4(D(20) inf 2(x))
360
K-1 18nLM Jey Cj
+
(71)
K
aK
K(1 T)
K= prEQu
Lig0,, Oz
4M4 12,
4M%,, C7, 1/ )11ō yo 12 the
where 8g
3x( (1 pp) (L?
+
+
162
11²
initial error. Specifically, Qs= = 1+11, we have:
K [V 4(0(50) +(("))
1 K
350
18nLM? /2p C22 lnk
Σ
+
(72)
aK
K(1 T)
W
Proof. Substituting the inequality (67 into (40)
yields:
(+xz)) (=+)))) s 3
+
IlyE. Vill
1²
nLC
L2
C7, D7,,,
+ 3MM..
2
Fu
+
1lua - yk 112
EN²Qu
112
1xt
3L2 SzN
C7,
12
O7, 12mm)
3L
+
12M²
11
yk 112
42
122
nLM²
C2
Px
6
(73)
Then, based on Lemma D.15
substituting the above inequality into 443 yields:
llvi 3k. s (1 (1+e))) c)x(( T T(1
vi. 21 2(1 + = T (1- Bp))
)x((
((1-8p) 13,0² 21 (x
+ + + _ |k| 1 (1( P 7 (I - (2
T
S A1ll 1 - 1 + +2(1+ + - n2 1 |T (1 3 \
T
+ 12(1+ + 1 |m x T1- L2 nLM? Joy C7,y
8
k1
(74)
1, c2
4M² Jyy Fv
4M2
Oz 1,3 )).
where - =
+
a
Summing the inequality 74
from to l results in:
k-1
llvt - 11 < * >=11 yo. 12 + 2(1 + 1 )K(( ) 3p)) 12,0
Σ
75
1=0
nLM3 C2 k-1
1 1 T 3p) 1" L3 a
+ 12(1 +
- )
1zy
7
3
Qk-1-j
1=0
36

---

Published as a conference paper at ICLR 2025
Combining the inequality 773 and l1s6 yo.rl1 S (T
-B4)
yoll? it follows that
k-1
[Q - (2 S 607 + wa
2
1=0
(75)
nLM?
k-1
nLM CF,
+ 6wa
Σ
7)
+6
Jay
Qk-1-s
13E
j=0
Ii Cz +
4M Lip
4M Cr 1/ 11:ō - voll and
where 50- = (x( (T? +
+
Jzy
1²
= 6(L3, + [ C7
4M². L7,
AM1.
C2,y
x
+
/ +
)(1 + ))(( (p)) = L.y
Since (.) is Li - Lipschitz, it can be obtained that
L
((<++1) 2 ((xx)) + (V4(2z)) I++1 - xx)) +
|| - xz ||
2
< ((xx) a((V (T(T))) v+((xx))
all -
(76)
+ a² L+ [ - 71(Ix)11
I ((x)) 2 a² LL || +
(g a + a² LLL [V - F1(2))13
2
Using the inequality 75
yields:
((Ix+1) (xx)
a a² L4) [] + (5 + +z>Lo) [[(()))) (
2
((() -
a
a² Lx
| +
2 + a² Log 60t*
2
k-
6nLM3,,
loy Gr, (77)
+ wa?
+ 2
Lo
~' 17 ( + @0e
+ a
2
2
13EQ2
1=
nLM?
C²
k-1
+ Gw
(2 + a² Lo)
a
Jay
Σ 7)
2
Qk-1-j
1=0
Finally, by telescoping the inequality (77) from k- = to 1 = K - 1, it is derived that
(2 a² LLL
K-1 1
Σ
2(IK) (
+
(a
+ a² a²Lo))
50
2
1-T
k=U
K-1A-1
+ wa? 2 (a
+ 22T00
ΣΣ
/ (T
k=0 ==
(78)
K-1
6nLM O7
+
+ a LB)
k=
nLM2 C2,y
K-1R-1
+ [6
(
a
+ a²T
Jay
ΣΣ
1
2
Qk-1-j
k=
j=0
Moreover, due to Ek- E5=
azbk-1 S K-1
Ex=o bj. we can deduce that
Ok
1-
K-1
K-1
)2
(
k=0
k=0
K-1
Σ
Qk-1-j
Q
Q
k=0
37

---

Published as a conference paper at ICLR 2025
Then, the following inequality holds:
1
K
1/
aLx wa²
[ + aLo
taLo
2
22
1
K
A=
(1)))
D(TK)
(1
80
+
+ aLx
(79)
aK
K(1- T)
1 K-1
1
1
+ aeib
6nLM
1
K-1
6w
1
+ aLs
a
lay
C2,
K
2
12EQk
K
1
2
10
k=0
k=
If flls + ww
(2 + aLv)
1-7 S /.2 then
1
[o(x=)] 4(0(zn) inf. (xx))
360
K-1
18nLM}
C2
(80)
K
aK
K(1
7)
K
k=
Finally, by substituting Q== = k + into
80
72
is derived.
In addition, we present another theorem that does not require the strict assumption on the initial Hessian matrix Hy, but does require that T 2 8n
2L
Theorem D.25. Suppose that Assumptions 3.1
3.2 and 3.3 hold. Choose the stepsize 3 and warm-up
iteration steps P such that (1 (1-31%) 3/ 11yk - Vi
K1 where K1 defined in 16). Set Hu = LI and
Jey C+ 4M² 1a,
T > 8nin 2L, Define e7 (2' (1- ( (61t))6611+3
p. 4M7 C7, (im) and w 6 [ + 2, or
4M7 22, 4M7,, 27 12 1/
1²a +
)( (
19" 3p) L. Choose the stepsize a > 0, the positive constant & >> 0 and iterate T > 0 such that
w²a
T << and als + wa? (² 1-7 ) 4
Then, the solution In generated by Algorithm D acciivess the following convergence rate:
K-1
[o((1))1 < 4(D(20)) 4(x*))
380
1
18nLM?
J.n Cj.
Σ
(81)
aK
K(1
T)
K
K=U
3e ml ( (T - P + 13 C2
4M7,
Li
4
Jay C2, 1. 1i 1lvō
where 5n
yoll2 2 is
the initial error. Specifically, if Q2= k 1, we have:
K
(x+)) < ((0( inf ((x))
35g
18nLM?
C7. InK
+
Jay H
(82)
K
aK
K(1-1
Proof. Substituting the inequality 67 into (40 yields:
T.2
C2
( v < 3 312
+ 112
Ilux.
vil1
2 n.C
I22
C2 T2
+ +3M²
+ 41
+
1117 Wk. 112
112
nr
3L3 30
C7,
L2
C²,
31
112
+ 12M2
Sey
112
+
1
1111 - yk. 11?
nLM?
C2
+ 6
(83)
38

---

Published as a conference paper at ICLR 2025
Then, based on Lemma D.17 substituting the above inequality into 45 yields:
llvt yr.T11 < (1+ =)
+ [
_
8p) 1TT v 2(1 Jcq -
Bp) - (|
+ + + ) 3 7
1 ( Bu) 1| () - (
S &Tllii-1 - yk- 1r7l + + + 1 j (1
(1- - [
? Jegn 0 ( )z Bu) L n nLM? Jav 2r,
+ 12(11 + -
p
(84)
cz,
4M L7x
where: T =
- (1
((1 + e) + 6(1 + 2)0
+
+
4M1 Cr (ix))))) ns
Summing the inequality (84) from 0 to k results in:
k-1
loo - yk. 112 S 11vō - y0.r/1 + +2(1 + ( 1
B1)
Σ 7
1=0
+ 12(1 +
Jofnn 1 [( B1) B 12
nLM?
jay
C7.
Σ
k-1
_ T
1.55
Qk-1-j
j=
Combining the inequality
83 and l - 30, S G7 (+) 11 (1 - /11) 31 - woll 2 it follows that
k-1
(V(()) - V (<x))) 12 I 807* wa
V V (I
1=0
(85)
nLM?
C²
k-1
nLM Oz,
+ 6waa
Jay
7)
+6
use
Qk-1-j
13EQu
j=0
where 8n = (+) (L3 + 1 C2
4M7 Jay
1.
4M2,, Cz,y 1.uue >1li0 - voll and
+
+
a²
12a
4¹
-6[T,, + 47,0 Ct,
4M 4i, 4Mf7.., nt
Cr,
1i )(1 + c
( [1 -Bu)) r.y-
n²²
n²a
Since (.((-) is L+ Lipschitz, it can be obtained that
Lo
< ((xx) ((<++1)
+ (V0( - xx) +
|| - xz 2
2
- < (TT)) (Z)() (()))) all -al +a (86)
+ LL [2(xx)= - {111))1
< < - ( - d²Lo) |[( + ( + LL) ) [V - =2(2))1
a
Using the inequality (85) yields:
Φ (xx++1) {T(1))
(x a Lo)
(x+)) + ( + +a² +ooLo) |[ {+(+))
2
<
0
a² Lb)
| +
+ a La2Lyy Lo) 607
2
k-1
6nLM? C2 (87)
+ wa? 2
(
a
+ T2T.0
Σ
7
/
(
a +
( + artaa)
Jzy
1
1=0
nLM?
C2 k-
+6w
+ a² az2L))
a²
Jzy
Σ
2
Qh-1-j
f=0
39

---

Published as a conference paper at ICLR 2025
Finally, by telescoping the inequality (87 from &o = to ks = K - 1, it is derived that
K-1
a² TT)
( T(xx)) + ( + t
6n
2
1 --T
k=
K-1k-1
+ wa
a
+ LL
V (
k=0 1=
(88)
K-1
O2,y 6nLM
+
+ a Lo
Jyy
k=0
nLM? O7,
K-1k-1
+ Ew
(
a
+ a² Lag
Jay
ΣΣ
1
1
Qk-1-j
k=
j=0
Moreover, due to -
a-bk-1
S Ei=0
Σk= bj. we can deduce that
K
(+(x))|
k=0
k=U
k
K
K-1
Qk-1-j
Qx
k=0 1=
k=U
k=u
k=U
Then, the following inequality holds:
1 aLs wa?
(
K-1
1/
taLo aLo
2
+
-
K
(11O)
((IK)
80
+
+ abb
(89)
aK
2
K(1 T)
1
K- 1
GnI.M3
K
6w
1
Cz.
+ aLo
+
+
abs
a²
Jav
K
2
UsEQk
K
1
2
10EQx
k=U
k=0
aLs + wwa (2 aLo)
1-r S 1. then
K-1
[++)))) v 4(0(20)) - +(xx))
36p
K-1 18mLM? C2.
(90)
aK
K(1
T)
K
u²EQx
R=
where (xx') inf, (zz)
Finally, by substituting Qx = k +1 1 into
90 82 is derived.
E COMPLEXITY AND THEORETICAL DISCUSSION
Corollary E.1. Consider T = ((nk) and O( such that 1 and aLa wa? (2 + aLo) 1-1 S 1.2 Under the same setting of Theorem achieve an c-stationary point, we require K Ō(13c=1), resulting the gra- dient complexity of Ge(f,e) = -(x-E-?), Gc(FFF) = O(x3e and a Jacobian-vector product complexity (V = E
3.7 we have K K-1 [+
O + xx9nK),
Proof. For Theorem 3.7 by Theorem D.24
we have
12,,,
C2
4M2
12
4M2 C2 L2 Ixy > ((:)). 11
61
+
Jzy
122
42
40

---

Published as a conference paper at ICLR 2025
Since 0 < -p)) and O 9), it is derived that
T = ki T
(1 Bu) ((1 + + +1+ ! )a²cs) ( =(x(1TT)))
T
1 b = (1) = =0(x211T)) (1/T)*).
w = c3 + &
)mmm
Based on Lemma D.12
V is L Lo-Liscchitz with Ls O(x*), ). For a suitable choice of a = +(x
follows that LLD wa = ((x(1/T)))
Additionally, with 7 @In x). the conditions
I and
g
v To are satisfied. Consequently,
(1 + aLo aal
1 --
1 4
aLv + wa?
10
2
8
Since O(k "), it be obtained from
72 that 3 Eks VD(=x)]1
0 n²² + =llnk) ).
Furthermore, in order to achieve an c-stationary point, we have K = 0 In 1 Therefore, the following complexity results are derived:
01130
Gc(fie)= = K + P) + EK- Qx K(T+ +P K(K+1) Ö(N 2):
2
Gc(FF))= = = Ö
. JV((c) = =KŌ(63
wa = - (m(1/T)²² and 2 1, it is enough to show that Cys(1/T)² < 1/10 by choosing T = (In Here, Co > 1 is a positive constant in r and wa?, depending explicitly on the Lipschitz constants the assumptions.
Details for obtaining r - 1/2 and wa? < 1/10: Since r =
(x(1)T))" o
By taking the logarithm both sides of Cox(1/T)T - 1/10, we get:
In Th < - In(10C)).
This is equivalent to Thm 2 Inx + ln(10C)). Therefore, choosing T > las + In(10C)) + e is sufficient, since In 7 2 1. Similarly, we can prove the result for Theorem 3.4
41


Reviews:
[{"review_id": "SVVO07fM6F", "reviewer": "Reviewer_E1d6", "summary": "This paper integrates a quasi-Newton approach into a bilevel optimization algorithm to approximate the inverse Hessian-vector product.", "questions": "Can this method be effectively applied in a stochastic setting while maintaining comparable convergence rates and computational efficiency? The required adjustments in iteration rounds and step size suggest potential difficulties in achieving the same convergence speed as existing methods.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The proposed method avoids costly second-order computations for approximating the Hessian-vector product while achieving a comparable convergence rate.", "weaknesses": "The paper is challenging to follow, with a vague explanation of the quasi-Newton recursion scheme. The design of the proposed method appears overly complex compared to existing methods, and there is limited explanation regarding the validity of  $u_{k+1}$ as an accurate approximation for the Hessian-vector product.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZEwwCDPJ3I", "reviewer": "Reviewer_5z6s", "summary": "This paper proposes an algorithmic framework, qNBO, which leverages quasi-Newton methods to solve bilevel optimization problems in the nonconvex-strongly-convex setting. Some practical implementations are also provided under the theoretical framework. It establishes non-asymptotic convergence for the BFGS adaptation within the framework and provides numerical experiments demonstrating the superior performance of the proposed algorithms across various machine-learning applications.", "questions": "Please see the questions in the weakness part. Here, I want to add some minor questions:\n\n1. Page 6: In Eq. (6) of Theorem 3.3, the constant $M_{f_{xy}}$ can be computed, as $f$ takes the quadratic form given in (5).\n2. Page 8: In Eq. (9), ``${a_i}’$, ${b_i}’$” should be ``$a’_i$, $b’_i$”.\n\nI think this paper provides a good attempt to use second-order optimization to accelerate bilevel optimization. Overall, I like the approach. I am raising my score to 8 if the questions and the typos can be addressed well in the rebuttal.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and easy to follow. Quasi-Newton type methods for solving bilevel optimization have not been well studied, even in the nonconvex-strongly-convex setting. This work provides a quite general algorithmic framework, allowing any quasi-Newton method to be applied in qNBO.\n2. A convergence rate and complexity analysis are provided for qNBO (BFGS). Technical derivations seem to be nontrivial. The authors incorporate the superlinear convergence of BFGS into the non-asymptotic convergence framework commonly used in bilevel optimization literature. \n3. Experiments validate the promise of the proposed methods.", "weaknesses": "1. For the theory, the results in Theorems 3.3 and 3.6 are limited to the setting where $Q_k=k+1$. As a result, qNBO is a double-loop algorithm. Is it possible to design a single-loop version? Recent progress has been made toward single-loop bilevel optimization algorithms, especially in the nonconvex-strongly-convex setting, by using a warm-start strategy. \n2. For the experiments, since the value of $Q_k$ affects the running time, it would be beneficial to empirically demonstrate how increasing $Q_k$ influences performance gains. Note that the numerical results in Fig. 1(d) illustrate only the impact of $Q_k$ as the outer iteration $k$ varies.\n3. Page 6: Do Theorems 3.3 and 3.6 require the assumption that an optimal solution $x^*$ exists? Note that $\\Phi(x^*)$ appears in both (6) and (7). \n4. Page 7: Why is it stated that qNBO is more efficient than AID-BIO? Note that the notation $\\tilde{\\mathcal{O}}$ omits the $\\log\\frac{1}{\\epsilon}$ term. \n5. In Appendix C.5, the authors report various ablation studies on the parameters $T$ and $Q$, but they do not specify which experiment these ablation studies are based on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YjorkLiSaF", "reviewer": "Reviewer_yCCW", "summary": "Summary:\n\nThe paper considers bilevel optimization problems with strongly convex lower-level objectives and proposes a framework for performing hypergradient approximation by using recursive quasi-Newton schemes to avoid issues in Hessian inversion arising in common BO algorithm. \nThe proposed algorithms, qNBO (BFGS) and qNBO (SR1), take inspiration from an existing algorithm 'SHINE' (Ramzi et al 2022). SHINE uses quasi-newton for solving the lower-level and reuses the approximate inverse hessian to perform hypergradient computation. \nHowever, such approximate hessian is only accurate when multiplied with a specific vector: the gradient of the inner objective. \nHence, it might yield inaccurate solutions when multiplied by the gradient of the outer objective, as required by implicit differentiation. Although SHINE propose a way to steer the approximation towards the upper-level, it is unlear to what extend the method enjoys good quantitive convergence rates. This paper addresses such limitation by introducing a separate quasi-newton based estimation of the inverse-hessian along the gradient of the outer objective. This results, in principle, in a more accurate estimation of the hypergradient. \nThe paper then provides finite time convergence guarantees and illustrate the method on a toy example, a regression task and a meta-learning task.", "questions": "Some of the figures in the appendix seem to be consitent with what the python file toy3.py produces. However, it contains a number of bugs for various implementations: \n 1- AID-TN:  a) the implementation of the function TN is wrong, it should be:\n\t \tv = v - inner_lr * output\n\t\treturn inner_lr * p\n\tinstead of :\n\t\tv = v + inner_lr * output\n\t\treturn p\n\n\t     b) the function TN (truncated-newton) should be called to compute v before computing the cross derivative f_xy, otherwise, one uses an outdated version of v for computing the hyper-gradient i.e.:  \n\t\tv = TN(fyy,Fy)\n            \tfyx=f_xy(x,y,v)\n\tinstead of:\n\t\tfyx=f_xy(x,y,v)\n\t\tv = TN(fyy,Fy)\n\t\t\n 2- AID-BIO:  Same issue as in AID-TN: Conjugate gradient should be called before computing the cross-derivative for the same reasons, otherwise this results in unnecessarily inaccurate hyper-gradients which slow performance:\n\t\tv = cg(fyy,Fy,v,10)\n\t\tfyx=f_xy(x,y,v)\n\tinstead of:\n\t\tfyx=f_xy(x,y,v)\n\t\tv = cg(fyy,Fy,v,10)\n 3- AmigoCG: In the deterministic case, this corresponds exactly to AID-BIO algorithm, so they should give the exact outputs. Similarly to AID-BIO, cg should be called before the cross-derivative. Additionally, there is no need to evalulate f_x(x,y) and f_y(x,y) for hyper-gradient computation as this unnecessarily slows the method. More importantly, there should be a minus sign instead of a + in front of the implicit gradient:\n\t\tx_grad=Fx-w\n\tinstead of:\n\t\tx_grad=Fx+w\n\n 4- Shine: The implementation is also incorrect though I did not have time to fix it myself. The OPA correction involves only the cross derivatives of the inner-level function not the outer level function:\n\t\togrady = f_xy(x,y)\n\tinstead of:\n\t\togrady = F_y(x,y)", "limitations": "", "rating": 5, "confidence": 5, "soundness": 1, "presentation": 3, "contribution": 3, "strengths": "- The motivation and approach in the paper are quite interesting, it makes sense to accelerate convergence of the inner problem using quasi-newton approaches. It is also nice that the method provide convergence rates for their algorithm, although I think the analysis do not seem to capture the benefits of qn for computing the hyper-gradient (when computing  the iterates u_k). \n- The paper is overall clearly written and well explained, which makes it easy to read. \n\n- The method seems to give quite an improvement compared to SHINE in terms of convergence speed (no full finite time convergence was provided for SHINE). While the experiments seem in favor of the proposed method, I think the implementation of SHINE contains some errors after checking the code (see weakness section).\n\n- I appreciate that the authors provided the code to reproduce the results, this allows for a better assessment for the results. Although there were bugs in it, that unfortunately change some conclusions (see the weakness section), I think this should be seen as an opportunity to improve the experimental study.", "weaknesses": "- Experiments: The results in the toy experiment looked suspicious to me: AID-TN, AID-BIO and AmigoCG seemed to work unreasonably worse on a quite simple example where they are supposed to perform quite well. I decided to check the implementation provided in the supplementary and found a number of bugs that explain these results. Please refer to the questions section for the details of these bugs. \nI think these can be easily fixed. However, after fixing these bugs, the results do not exactly match the conclusions of the current paper: it is possible to solve the toy problem faster/more accurately using AID-BIO/AmigoCG using a single step of CG (instead of 10). More precisely, after fixing the bugs: AID-BIO/AmigoCG reach 10^-4 relative error on the upper variable (instead the numbers reported in the paper: 10^-2 for AID-BIO and 10^0 for AmigoCG), and further go below 10^-5 (better than qNBO) when using only a single CG step and single gradient step. AID-TN reaches 10^-1, instead of 10^0. I do not exclude other bugs on other methods (the implementation of SHINE already looks incorrect (see questions section)), so I strongly encourage the authors to test the implementation with care. \n\n\n\n\n- Convergence results:  \nWhile the convergence analysis exploits the super-linear convergence of quasi-newton for the inner-level iterates, the iterates used for computing the hyper-gradient do not seem to benefit from such super-linear rate. In fact, the convergence of these iterates is sub-linear: 1/Q where Q is the number of quasi-Newton iterates.  This might explain the worse dependence of the algorithm on the number of gradient queries on the lower loss epsilon^{-2} compared to AID-BIO epsilon^{-1}. Still there is an improved dependence on the conditioning for the vector-jacobian complexity (kappa^3) vs AID-BIO (kappa^{3.5}). However, it is unclear how this compensates the increased complexity for the gradient, especially given the results of the toy experiments (without the bugs). \nOn a positive note, the result is an improvement over the guarantees provided for SHINE as they are quantitative.  \n\nAblation studies: methods such as AID-BIO do not exclude using other solvers for the lower-level problem. One could then use quasi-newton methods and still apply CG for the conjugate gradient. How do you think this would perform? \n\n\nAlthough I think the proposed direction is interesting, there is a number of problems with the current version of the paper that need to be addressed. I have many reasons not to trust the empirical results and that would require checking all the details of the code for all experiments. It is unclear to me if the rebuttal period would be enough for that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uKqiozJ5aO", "reviewer": "Reviewer_ozni", "summary": "This work studies the bilevel optimization problem, where the lower-level problem is strongly convex and the upper-level objective function is nonconvex. The authors introduce a novel framework called qNBO, which approximates the hypergradient by employing quasi-Newton methods for both evaluating the lower-level solution and estimating the inverse Hessian-vector product. When the quasi-Newton method used is BFGS, they establish a non-asymptotic convergence for the proposed algorithm. Finally, empirical experiments demonstrate the superior performance of qNBO compared to other bilevel optimization algorithms.", "questions": "For both the theory and experiments, here are a few things that need to be addressed.\n\n1.In Remark 3.4, the authors stated that the qNBO (SR1) algorithm lacks convergence guarantees without specific corrections used to achieve numerical stability in the general case. It was also mentioned that the performance of qNBO (SR1) on the 20News dataset was omitted due to its ineffectiveness in the experiment in Section 4.2. What are the underlying reasons for these issues? A bit more discussion on these points would be helpful.\n\n2.From the first terms on the right hand sides of both (6) and (7), it seems that Theorems 3.3 and 3.6 require a lower bound assumption for $\\Phi(x)$. Is this correct? Additionally, in the proof sketch in Appendix D.2, $\\tilde{\\nabla}\\Phi$ is mentioned but not defined. It would be helpful to specify its definition. \n\n3.In the experiments, how to select the step sizes and the number of inner iterations for the proposed algorithms?\n\n4.In Table 1, why does qNBO (BFGS) save so much time compared to SHINE for data hyper-cleaning?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The new bilevel algorithms are well motivated. By employing quasi-Newton recursion schemes, they incorporate two subroutines to accelerate hypergradient approximation and avoid incorrect inversion in solving the bilevel optimization problem.\n\n2.Several machine learning tasks, including hyperparameter optimization in logistic regression, data hyper-cleaning, and few-shot meta-learning, are evaluated, demonstrating the superior performance of the proposed methods. Additionally, various ablation studies are provided.\n\n3.A convergence rate guarantee is established when the quasi-Newton method used is BFGS.", "weaknesses": "My main concern is that: \n\nAlthough quasi-Newton methods are used to estimate the inverse Hessian-vector product, the proposed algorithms still require computing Jacobian-vector products, which can be computationally expensive in large-scale cases. Could this computation pose a potential problem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rnqqo59xjk", "reviewer": "Reviewer_XUKY", "summary": "The paper presents a bilevel optimization framework, QNBO, which utilizes quasi-Newton methods to address the computational challenges associated with hierarchical learning tasks. The authors integrate quasi-Newton recursion schemes for efficiently approximating inverse Hessian-vector products, specifically using BFGS and SR1 methods. The authors argue that QNBO offers superior convergence and computational efficiency, substantiated through theoretical proofs and numerical experiments.", "questions": "1. Given the success of stochastic adaptations in other optimization frameworks, could the authors discuss potential challenges or advantages of incorporating stochastic quasi-Newton methods into QNBO? Specifically, how might this adaptation impact convergence rates or computational efficiency in practical implementations?\n\n2. The initial matrix $H_0$ plays a significant role in quasi-Newton methods. Here, a scalar multiple of the identity matrix is used. Could the authors provide specific results or theoretical analysis on how different choices of $H_0$ might affect QNBO’s convergence rate and computational efficiency?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The QNBO framework presents an innovative approach by combining bilevel optimization with quasi-Newton methods to improve hypergradient approximation accuracy.\n\n2. The paper provides a non-asymptotic convergence analysis for QNBO, especially for BFGS, detailing convergence under both quadratic and general settings. \n\n3. The authors validate QNBO on real-world tasks such as hyperparameter optimization, meta-learning, and data hyper-cleaning. QNBO’s performance is benchmarked against established algorithms, including SHINE and PZOBO, with performance gains observed in multiple scenarios.\n\n4. I did not notice any major issues with the clarity of the presentation.", "weaknesses": "1. The SR1 method, despite its potential in quasi-Newton methods, is noted for its numerical instability in general functions without correction strategies.\n\n2. QNBO offers a flexible choice between subroutine A and B based on performance and computational cost. However, the conditions for selecting one over the other are not rigorously outlined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)