Beyond Value Functions: Single-Loop Bilevel Optimization under Flatness Conditions
Authors: Liuyuan Jiang
Quan Xiao
Lisha Chen
Tianyi Chen
Venue: NeurIPS 2025 poster ()
Keywords: bilevel optimization
Holder's condition
value function
penalty bilevel
Primary area: optimization
TL;DR: This paper proposes PBGD-Free, an efficient, fully first-order and single-loop bilevel optimization method, and applies it to mitigate catastrophic forgetting during LLM fine-tuning.

Abstract: Bilevel optimization, a hierarchical optimization paradigm, has gained significant attention in a wide range of practical applications, notably in the fine-tuning of generative models. However, due to the nested problem structure, most existing algorithms require either the Hessian vector calculation or the nested loop updates, which are computationally inefficient in large language model (LLM) fine-tuning. In this paper, building upon the fully first-order penalty-based approach, we propose an efficient value function-free (\textsf{PBGD-Free}) algorithm that eliminates the loop of solving the lower-level problem and admits fully single-loop updates. Inspired by the landscape analysis of representation learning-based LLM fine-tuning problem, we propose a relaxed flatness condition for the upper-level function and prove the convergence of the proposed value-function-free algorithm. We test the performance of the proposed algorithm in various applications and demonstrate its superior computational efficiency over the state-of-the-art bilevel methods.

Beyond Value Functions: Single-Loop Bilevel Optimization under Flatness Conditions
Liuyuan Jiang" , Quan Xiaot:o, Lisha Chen", Tianyi Chen "Rnsselaer Polytechnic Institute, Troy, NY "University of Rochester, Rochester, NY
CCornlll Tech, Cornell University, New York, NY 1jiang24@ur rochester. edu, qx232@cornell. edu edu 1 sisa. chen@rochester, edu, tianyi. www.ocorreen..eeee.......o
Abstract
Bilevel optimization, hierarchical optimization paradigm, has gained significant attention in a wide range of practical upplications, notably the fine-tuning of generative models. However, due to the nested problem structure, most existing algorithms require either the Hessian vector calculation or the nested loop updates, which computationally ineffieient in large language model (L.LM) fine-tuning. In this paper, building upon the fully first-order penalty-based approach, we pro- pose an efficient value function-free (PBGD-Frea algorithm that eliminates the loop of solving the lower-level problem and admits fully single-loop updates. In- spired by the landscape analysis of representation learning-based LLM fine-tuning problem, we propose relaxed flatness condition for the upper-leve function and prove the convergence of the proposed performance of the proposed algorithm in various applications and demonstrate its superior computational efficiency over the state-of-the-ae bilevel methods.
contee-fnntto-fieee free algorithm. We test the
Introduction
Bi-level optimization (BLO) has gained significant attention for its powerful modeling capabilities in hierarchical learning across a wide range of real-world applications, such as distributed learning
69 (28] meta learning 27
12 27, model pruning 96), reinforcement learning [008 84
79 85]. 107 and this paper, we consider BLO problem with / Rd x R IR
continual learning 8
33
fine-tuning large language models (LLMs) [76]
68 64
56
diffusion models 993
17
R being the upper-level (UL.) and lower-level (LL.) objectives that are continuously differentiable but not necessarily convex. Since the LL problem may contain multiple solutions in St (x). we consider the optimistic BLO formulation which selects the that minimizes the UL objective, given by
and 9 Rd x d
min (w, y E S7()) arg min (( w) K.
In large-scale machine learning problems, efficiency is given a higher priority [10 and it is critical to gradient-basee approaches to solve the above problem. One can perform direct gradient descent (GD) on the hyper-objective p(x) == minges;()) f(x y). A popular GD-based method is the implicit gradient descent (IGD) method with second-order Hessian evaluation 29
34
39
15
47 82).
However, evaluating Hessian or its inverse in IGD is costly. To reduce the computational burden, especially in large-scale problems, first-order gradient-based methods, including the penalty-based
BLO methods [105]] 50 77 45 40 (5), have been developed. For example, penalizing the L.I.
"The work was supported by the National Science Foundation Projects 2401297, 2532349 and 2532653, and by the Cisco Research Award.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

objective optimality gap into the UL via large penalty constant 7 has been proposed [105 78 45 yielding the following objective
58
min (x) := min E3 (a, y) == (xx 1) + (g((,, - min g(x, =)).
(2)
Under a proper curvature assumption for the LL problem, the penalty reformulation proves to be differentiable and smooth [78
45 40 IT which enables the design of penalty-based gradient descent 44 45 T0. Furthermore, the function value gap (x) Φ(xx) = (
algorithms (PBGD) [78
ensures the solution to the reformulated problem is an approximate solution to the original problem.
The reformulation in (2 provides two choices of algorithm update: jointly updating x and y to
minimize F,, (a. y) [105 [78. or alternatively optimizing y then updating x to minimize the hyper objective F2 45
Each has its pros and cons. For example, joint update eliminates the inner loop of so that it has low per-iteration cost, but high smoothness constant of (,, y). which increases with y, making the convergence rate suboptimal [78 [05]. In contrast, the smoothness constant of F,, (2) remains (1) since the value function gap (g((z, y) min; g( z)) remains in (L) when minimizes F(x, y), but estimating (x)) often requires running inner loops to obtain vg (z) E (x) and (x) E (xx == argmin, (z. 9) M. Then a natural question is:
(Q1) Can we develop an efficient algorithu that combines the best of both worlds?
The idea is to update by Vzf(zz v,, (x)) and skip the inner loop estimation for v.J (z). which we term as PBGD Free of value function evaluation (PBGD-Free). To be more specific, we illustrate the updates for standard PBGD, its variants, and PBGD-Free in Figure
Positive empirical observations on Q1: PBGD-Free largely duces computation and memory cost while preserving the accu- racy in LLM parameter efficient fine-tuning (PEFT) [72 2V.. See
V-PBGD
Xt.
yi 1/1
Mir kg0rm
Xe+1, Vt+1
FSA
Yu V41
Mir xg(r))
X2+1
No -/
1/2 Ye+1 35(x))
PBGD-Free
X2
x yt+1 [51xa))
x+++
Xx+2
Figure 2 and experiments in Sec-
tion We prioritize supervised
Figure I: Update schemes for V-PBGD, F2SA and PBGD-Free. (middle) refine the LL variable over multiple steps before updating 24 via V, (3,,, ye) for V- PBGD or F,, y:) for F'A while PBGD-Free (bottom) applies 1-step inner update to find a more efficient yet potentially less accurate v (31, Mt+1) RJ (x.)).
fine-tuning (SFT) loss at the LL to ensure a capable base L.M model, while we keep direct preference optimization (DPO) loss (70) in the UL to keep align- ment with human preferences:
V-PBGD 78 (top) and FSSA 45
Surface Rx.
min fDPO(æ, y: DDPO) 2.y
PBLD-Frue
fxx, (xl) Free
F25A
s.t. y E arg min (I, yi DSFT),
F25A
where I is a pretrained LLM model, and y is an easy-to-fine fine- tune head. This design is aligned with both theoretical and practi- cal needs in LLM deployment, as detailed in Section 4
F25A
Time (second)
Figure 2: An Illustration to show PBGD-Free does not work in Example I but works well in PEFT. The left plot shows the f(z, y) and ((z,0(()) in Example 1 with red and blue dots the converged points using PBGD- Free-FFre& and F2SA method. The middle plot shows the trajectory of updates in PEFT. The orange, cyan, and green contours the landscapes of foro(æ, v). ISFT (I. v), and (2 y). respectively. The right plot presents the convergence vs. time in PEFT, showing faster convergence of PBGD-Free. (See Appendix C.I for details.)
Negative theoretical observa- tions on Q1: There are some counterexamples where PBGD- Free does not converge. cl) When the UL objective solely depends on the LL variable f(z v) = fy). as in data hyper- cleaning 75 34 76 and meta-learning
27 12 27 the LL penalty gradient term contains all the gradient information about the UI. variable so it cannot be omitted; and, c2) When f(x, v) jointly depends on both variables, omission of the penalty gradient term can lead to different update direction; see more details in Example D and Proposition 2

---

Property
PBGD-Free
V-PBGD
BOME
F'SA-MA
F'SA
BVFSM
f(x,-)
Flat
Lip
Lip &
Lip
Lip
Diff
g(x,)) .)
PL
PL
PL B
PL
PL
Diff
f(x y) + 79(2,
PL
/
PL
PL
Single-loop
/
X
Memory cost
de + dy
dg + 2dg 3dg + 4dy
de + 5dy
dy + 2d,
dg + 2dg
Complexity
)
O(E (9) Oie
Oie
O(E
Asym
Table 1: Comparison of the proposed method (PBGD-Free) with the existing first-order approaches
for BLO with nonconvex LL problem (PBGD 788,, BOME [T05], F SA-MA
45 (with momentum
assistance), F2SA [TT] and BVFSM (51) deterministic setting. The notation O hides dependency on (og(( terms. 'Flat', 'Lip'. 'B'. 'Diff", and "Asym' stand for 'flatness condition" in Def. 'Lipschitz continuous', 'bounded', 'differentiable', and "asymptotic convergence".
Example 1. For the BLO problem in 1 with f(x, y) x²² 10y and g(z. y) = (y x 1)?, the gradients (VP, (z), fz, (x)); exhibit opposite directions for x E (-5, 0). As a result, (z) 2z + 10 converges to = while [z, (x)) 2x converges to
These findings leave unclear when PBGD-Free can be applied without sacrificing accuracy. In this paper, we focus on the case with UL joint dependency, where the objective [(a,, y) depends intrinsically on both x and y (i.c., cannot be simplified to f(y)). We explore the following question:
(Q2) Can we identify sufficient conditions under which the PBGD-Free algorithm is guaranteed converge to the stationary solution of the original problem?
We give an affirmative answer to the above question. Specifically, our key contributions are summarized follows, and the broader impact is discussed in Appendix D
CI) We propose PBGD-Free, a computationally efficient fully-single-lopp. first-order algorithm. See detailed comparison with other algorithms in Table [ Specifi- cally, compared to V-PBGD, it reduces the memory cost from O(d2 + 2dy) to Ord + dy). and the per-iteration computational complexity cost from (KK) to (()). where K is the number of inner iterations. Furthermore. we show that empirically, it works in large-scale problems such as PEFT B). But theoretically, under a Lipschitz condition on the UL objective, PBGD-Free only converges to an é neighheighooroood of stationary point.
C2) We then introduce Hölder- alike condition to describe the flatness of f(x,,) :) (see Defini- tion I which relaxes the standard I f..o-Lipscht continuity assumption when y,00 is small. This condition allows us to establish an improved complexity of the PBGD-Free algorithm in O(- (Theorem
necessary stationary condition of the original problem.
C3) We validate our methods through applications to LLM with PEFT and bilevel low-rank adaptation, Across all experiments, PBGD-Free demonstrates much better efficiency and comparable or better accuracy than the state-of-the-arl baselines. See Section
1.1 Prior art
Second-order BLO methods. The convergence for IGD-based BLO approaches was firstly es- tablished for the unconstrained strongly-convex LL problem 22 with later literature focused on improving finite time convergence rate 229
97 Another branch of but they generally lack finite-time guarantee under stochastic setting 32 37]. However, convergence analysis for both ITD and IGD methods mentioned above is limited to the setting where the LL problem is strongly convex over y. This assumption does not align with large-scale machine learning applications, where the LL objective represents the loss of neural network and is inherently nonconvex [86
14
15
42
methods is based on iterative differentiation (ITD) methods 600
26
63
75
41 Recent studies 52 or even nonconvex
have generalized the IGD and ITD methods to address BLO with convex
8I
LL problem 192 49 50, 66, 98]. Nevertheless, both ITD and IGD require the computation of second-order information, making them inefficient for large-scale machine learning problems.
First-order BLO methods. Fully first-order bilevel methods based on equilibrium backpropagation 74 74 [13 and penalty reformulation 78
[03] have become increasingly popular due to their computational efficiency and the ability handle nonconvex LL problems. Later, penalty
45 105

---

approaches have been generalized to address BLO with constrained LL problem [100] 40 and distributed learning settings |99 87 However, the iteration complexity of fully first-order approaches remains suboptimal, exhibiting logarithmic dependency due to the inner-loop overhead. To reduce the cost in inner loops for both v (a) and y (z), PRGD 78 eliminated the inner loop for y (2r) by
jointly optimizing x and Vy in 2) FASA 45 managed to be fully single-loop using momentum and warm-start techniques. However, both methods incur suboptimal iteration complexity of O(e -.5). [TI further improved iteration complexity of double-loop version of F&SA by exploiting the fact that Fy (z) is (1)--iipshitzz smooth, but its inner loop leads to a high per-iteration computational cost and suboptimal convergence rate as O Oe log(e +)).
Landscape-aware optimization. Landscape- objective functions into algorithm design to accelerate the convergence or improve the generalization. Newton-type methods. which use second-orde curvature information to rescale gradients, have been utilized in BLO (23 7 21 for efficient Hessian-vector calculation in IGD-based BLO methods. Sharpness- aware minimization 255 which seeks solutions robust to local perturbations and promotes convergence to flat minima, has also been incorporated into BLO [ for improved generalization. Other landscape conditions in single-level optimization, such as relaxed smoothness [109] 46) and Hessian spectrum [12 30), are key to explaining the theoretical benefits of empirically effective algorithms like gradient clipping and Adam 43 However, most existing works focus on second-order BLO algorithms, and none have explored BLO tailored landscape conditions.
optimization leverages structural properties of
2 Value Function Free Algorithm for BLO Problems
In this section, we introduce the value function free algorithm for bilevel problems and show that it does not always converge under the traditional Lipschitz condition.
2.1 Preliminary: the Lipschitzness condition and the penalty-based reformulation
We begin by introducing the standard Lipschitz condition on the UL objective f(z, v). which is common in BLO analysis.
Assumption 1. Assume that for all x, the UL objective fax -) is 1,po-iipschhtz in y at (z) with some 1,0 > 0, i.e.,
(f yg (2)) (2. S 11,0l13 15 (x)]).
(4)
For differentiable f, Assumption implies V the key results in BLO literature; e.g., [78 45 15
(xr
This assumption is crucial for 38
105]. Together with the following standard assumption, it enables good approximation of (x) to the original problem.
39
34
Assumption 2. Suppose that i) f and g are respectively 1 and smooth; ii) V and V2g are respectively 14.2 and Lipschitz continuous; and, iii) there exists finite Y such that of (x. + g(x, y) is
(PL) in y for all E [0. 10," for some 0.
We provide the definition of smoothness and PI. in Appendix A Here, the smoothness condition is standard 29
38 15 40 The Hessian Lipschitzness helps establish the smoothness of F, (w)
with constant nonincreasing with y and is also conventional [45] 11 19]. PI. condition is weaker
than the strong convexity assumption [[5] 34 29 38 9 and is conventional the first-order BLO
literature 45 78
[. Under these, the penalty objective is differentiable (78 45 II 63) and
(x,(2) = (x + ((((),
(5)
with Vyg (2) E (x)) and (x) E (²))) == argmin, F,,x,,) y). Moreover, the following proposi- tion shows that F,, (x) a good approximation of the original objective d(x).
Proposition 1 (Approximation error (78
45)). ). Under Assumptions
for any x. we have
[x)(2)) <(x)]l 20 (y-1)
and
(6)
[Vo(z) VF, (=) - - (=)))) S O01 11-1)
for some (z). (x) defined in (5) Moreover, the bound for [1g - 87 (z))) is right.
Therefore, the PBGD type of algorithms
45 105 proceed by approximating v7 x (x:))
and of R (xa) via gradient descent and updating x. via
Z141 Zt 199t where 9t = vvf(x,v?) + vzg(z,))) veg(z,
(7)

---

Algorithm PBGD Free from value function (PBGD-Free) algorithm
1: Inputs: initial point To, yo: step sizes 7f;; counters T, K
K 1 is common choice
2: for [- 0, 1....... T 1 do
3:
for k = 0, ....,...R
do Vi, = Ve. 17 (r 1o-'Vyl vf V2,k)) V Vog(Ir.
4:
D set Vi,0 vi-1
5: end for
6: Je+1
Thr, where 9r = V=f(Iz,
D. set y/ - V
7:
end for
8: Outputs: (T)
2.2 Negative theoretical results of the PBGD-Free under Lipschitz condition
Although PBGD-type algorithms can achieve the state-of-the-and art complexity O Log(" in their reliance two inner loops can become computationally expensive for large-scale problems. While the overhead is manageable in small-scale settings, may pose practical challenges as the model size grows. Nevertheless, empirical evidence in Figure 2 and real-world applications in Section illustrate that sometimes gives satisfactory results even directly updates T1+1 and V2,1 by
Lt+1 2t vf v?) and Bl,k+1 vi.x (7 ' (2 37,x) Vug(Ee, vlw)) (8)
which we name PBGD-Free algorithm and is summarized Algorithm !1
Although PBGD-Free is computationally efficient by eliminating the inner loop estimates of V (x). the removal of the value function part b(x;) := >(v= g(( (x)) Vag(a, y (x))) in PBGD-Free
introduces non-negligible bias shown in Example To see this, by Taylor's expansion, the omitted
value function part b(xx)) is in the order of
|b<2;))] = >1 e vy (x)) -000) -nmm))-,((())1 (2)
Here, the second term (n (2) = 017,07 1) can be small enough with enlarging following Proposition 1 For general settings where Vayg(1 (I, v (x)) * O, due to the first term and according to Proposition I the bias in (9) is tight (!(1). Therefore, in the general case where Vey9(z, (z, Vr (x)) # 0, the PBGD-Free algorithm only drives the iterates to a neighborhood of the stationary point, which we will formally quantify as follows.
Proposition 2 (Lower bound on asymptotic error). Under Assumptions D [ there exists BLO problem where the iterates generated by PBGD Free (Algorithm [ converge a neighborhood of stationary point with a non-vanishing residual even when choosing step sizes appropriately, i.e.,
( T
T
lim T- T
1 (20)) lim + T-000
Σ
Σ
Wf ((()))) -
e (1,o)
(10)
0
The proof of Proposition is available at Appendix A. Proposition 2 iillustrates that PBGD-Free converges to the stationary point only when the bound for V y v (xx)) (a.k.a (,,)) is small. However, this difficult to guarantee even in scenarios where PBGD-Free effective, such in representation learning based PEFT (3). This motivates us to explore a weaker condition than the small Lipschitz assumption on f(z, :), one that is more likely to hold in practice.
Theoretical Analysis under the (ő, -Flatnness Condition
In this section, will introduce a relaxed condition to replace the widely used Lipschitz condition the UL objective, discuss its use cases, and establish the convergence rate of the PBGD-Free algorithm under this condition.
3.1 A relaxed condition: UL (6, a: -flatnesss and its validation PEFT problem 3
We first introduce relaxed condition that is less restrictive, and therefore more general, than the conventional uniform Lipschitz assumption on fxx
5

---

Empirical vs. Theoretical Bounds
200
max |400 F,00|
max U/ Lx -,
4
2
2
Upper bounds in Lemma
0.5
Upper bounds in Proposition
91
10
12
14
Figure 4: Empirical bounds for [(((z)
Figure 3: Visualization of f(x. y) in Example 2 with de-
(ar)]l and (lxx(x)) - -v (x)]l versus the- oretical upper bounds in Proposition [ and Lemma the illustration of repre-
tails deferred to Appendix [B.2 Colored curves represent f(z,-) .) for different z; dots show (V, fzz My (x))). The upper plot shows (x, .) on a larger scale, and the lower one illustrates the fluctuation around vī (2))
sentation learning PEFT (3). The lower plot shows smaller scale.
Definition ((ő, a:) (tl-ttttsss). Function f(z, -) y - called (6.a))flat with modulus 2 0 at (x) E (x) with 8 2 0, 2 ff D (1))
(x., v)1 S <l)) yll 5 holds for all y-
When 5 = 0 and (2) is replaced by an arbitrary 3/. Definition reduces to the standard Hölder condition. Under Assumption [ the function f(x, satisfies (0, T)-flatness with modulus c = 1..0- However, setting 5 = 0 naturally imposes the constraint
whenever f vf( * 0. Unless otherwise specified, we assume > 0 and > when referring to flatness in the following.
We then discuss the relations of Lipschitz condition in Assumption and the new flatness condition in Definition |
through several observations.
Observation 1. Under the 1 ly.oshholsssss condition of [xx, ) if vI, (x)) 8 then ((, :) is (6, fi)-fltt with some modulus c O11,))-
The proof of Observation is provided in Appendix B.1 It demonstrates that assuming small [f,, v (x))] is stronger than assuming flatness since ε = 8 > å when a > 1. Below, we will show that the flatness condition automatically holds near the LL optimal solution (z).
Observation Under the smoothness condition of the (ő, fillatesss condition holds automati- cally for all y E {y: [f y) - f(x. vg (x)) S 5}.
Since f is continuous and smooth, this observation implies that the flatness condition permits abrupt, unstable changes in the (ejghheigbooroood of y (zr). This demonstrates that the flatness condition relatively mild and further confirms that it is strictly weaker than the small Lipschitz condition, which explicitly requires || , vy (x))]l to be small. Figure3visualize visualize an example that is (3e- -3, 1.1)-flat with modulus e = at vg (1r), but exhibits a sharp change leading to large Lipschitz continuity constant vy v (x)) 1000. The details of Figure 3 are deferred Appendix B.2
Owing the Hölder-alike condition, the following observation shows that outside of the O()) neighborhood, the curvature of the flatness condition is also milder than the Lipschitz condition.
Observation 3. Under (6, ai) fllttteess, the growth rate of f(x -) outside the O()) neighborhood is if (6) < lly xx) I O(1),
[f y) f(, ((,,,(())) yy (+)
[O(1). 10 (0l -)()))1-1).
(11)
fly (=)] > (().
This is obtained by dividing both sides of the flatness inequality by (1) - For small (x) vll- the second term dominates and leads to ((1) bound, which is the same the Lipschitz condition. However, for large || (x) vll. since o >> 1, the bound Olla,, (x) - =1 can be larger than (1)) This observation further demonstrates that the flatness condition relaxes the Lipschitzness of
f(x,,) in Assumption [ Specifically, while Lipschitz continuity would require a uniform bound on the gradient, flatness allows for a higher growth rate of Olly v (==)] For UL. objective fxx with fixed x, given a pre-determined a and modulus c, the constant for flatness condition in Definition can be calculated via
8(z) == max(0, (f vg (x)) - f(x, 8 (x)) (x) - (z
(12)

---

When (x) V2 (z)) > O(1), the last term in 112 dominates and 8(x) can effectively be O. Therefore, together with Observation [ the flatness condition with small ó not only encompasses broader function class than small Lipschitz continuous functions, but is easier to hold in practice. For example, modern loss functions used in deep learning, such as cross-entropy, squared error, or exponential losses, are nonlinear and locally curved. Around y (z), we can write far, v') z O. In such cases, the additive term in (1) vanishes and (zz) is effectively zero. This implies that the flatness condition can hold even when no Lipschitz bound on f(x;,) .) is available, particularly for locally curved objectives. We next illustrate this behavior concretely through a warameter-efficient fine-tuning (PEFT) problem in representation learning.
f(, (xr) + +clyy' yī (1r)] for some > 1 and constant
3.2 The flatness of the representation learning PEFT problem.
In our PEFT framework in (3). the model, which can be any structure (e.g. CNN), is parameterized with (z, y) by (r)() softmax (modele.,.x) response r given input question z. The DPO loss 77) over preference data DDPO. compares outputs TzZ against reference rer via
gives the model's predicted probability for
(r, 3) = IDprol (z.
Σ
log (ar (qa(2, y; 2, Tw. re))),
(13)
where (1,, 15 Tm, Tr) = 3 log (rult) 3 log (ral()
[ed(Tu]
The and re are the preferred and rejected responses to input The SFT loss operates on supervised dataset DsFr through
0.15
02c D.S, 2.5)
0.0
9SFT (2, y) == [DSFT]
Σ (
log (TT.((()FT (14)
0.00
0.00
Figure 5: Comparisons of 8(x) and (x, v, (x)) during PBGD-Free updates. The Lipschitz constant ε max V (z, V (=))1 is large but 8(x)) is small.
Both objectives are differentiable with the following gradients
fDPO = (1 (gg)) VgSFT
VT/Z. (15)
While the Lipschitz constant for this problem large, it satisfies the flatness condition with small 8. To illustrate, we revisit the example Figure 2 see the detailed setting in Appendix C.I As Figure 5 the flatness constant 5(x) < 0.0003 in the blue line is small throughout optimization for 0.5 and = 1.5, despite large Lipschitz constant in red. This confirms that the loss landscape analysis under the Lipschitz condition is not tight, as f,00 remains non-negligible even in local neighborhoods, whereas the flatness condition allows for a tighter analysis. The small 6(x) values along the PBGD-Free trajectory validate that the PEFT problem (3) satisfies the flatness condition, which inspired to establish the enhanced analysis of the PBGD-Free algorithm under the flatness condition. In real-world PEFT problems, e.g. ones in Section 4 0 (xx) in (12) is typically small because the distance between V (2) and (x.) are non-negligible, whereas their impact on foro is marginal.
3.3 Convergence analysis for the PBGD-Free algorithm
As shown in (9), the first term is the major bottleneck of the divergence issue of the PBGI)-Free
algorithm under the Lipschitz condition in Proposition The key to establishing the convergence guarantee for the PBGD-Free algorithm is the tighter bound of [ (a) (x))l and (lő(z) - F, (x) under the flatness condition, compared to the results Lemma [ We highlight the results as follows.
Lemma (Tighter analysis function value gap). Suppose Assumption 2 (ili) holds. For fixed suppose fxr, -) is (8, ai-flat at any y (x) E S (x) with a E (1, 1.5). Then, there exists 72 > 0 such that for 2 ",, have
[()(x) (x))1 =0(r = 5), and (s)())(u))) a (s)(w) 0
-2 2lo
-b) (16)
for any 3g (x) and y E (x()).
The proof of Lemma D is available at Appendix B.3 When 8 is smaller than target accuracy e,
achieving [|x(z) [x) 2x)) O(e) only requires 7 O(e- 2=")) which is
7

---

strictly smaller than the choice of y O à) in previous literature 778 aligns with common practice, where the penalty constant ? does not need be excessively large. For instance, the UL objective in Example
10 45 44].
This also
15 gives desired accuracy, supporting the rule of thumb: 7 Rs 15 is a reasonable choice. In Figure 4 we also show that our bound under the flatness condition in Lemma[]is tighter than the one under the Lipschitz condition in Proposition for the representation learning PEFT (
(10-3, 1.1)- and therefore choosing
Since Lemma D provides a per-iterate bound with fixed x, the next step is to analyze the Lipschitz continuity of the flatness constant (()) with respect to x, enabling a uniform bound across iterations.
Lemma 2 (Lipschitz continuity of flatness constant 5(x)). Suppose Assumption 2 holds. Then fixing some с 2 and a E (1,2), there exists some trajectory of (z) v2 such that the flatness constant of (a, ), 6(x:) defined in (2). is
in
The proof of the Lemma 2 is available in Appendix B.4
However, Lemma I and Lemma 2 only
enable the convergence of PBGD-Free to the stationary point of the penalized objective (z) We next establish the approximate equivalence of the stationary points to the original BLO problem (I)
Lemma 3 (Approximate equivalence of stationary points), Suppose Assumption
2 holds. Let xt
be an e stationary point of (x*) and suppose f(x", is (6. ai)fllat at any Vy (xx) E (xx) with
E 1,, and ā ( Then there exists 7" O(E and yry E +x²(x))) such that for 7 2 y", (x", vny is the (Ee) stationary point of the original BLO problem (
The proof of the Lemma is available in Appendix B.5 which generalizes the definition of stationary
condition for (1) [91 105 and its relations to that of the penalty problem 78 45 105 under flatness
condition instead of Lipschitz continuity in Assumption I In this way, building upon Lemma [ and Lemma 2 the convergence result for PBGD-Free in Algorithm i stated as follows.
Theorem 3 (Convergence of PBGD-Free). Suppose Assumption 2 holds, for all on the trajectory, f(x,,) .) is (8(z)), o-)-fat at all Ug(xz) E Sgy (2x) with the same a E (1, 1.5] and modulus c = =11). For iterations generated by Algorithm [ with K = 1 and step size nj S L where 1p,1 is the smoothness constant of (x)).. and suppose for target accuracy there exists 8 such that + Eno 8(x1) S 8, then by choosing 7 = O(0 -7))))
Σ
(E)(1))) & O(T +8
2(
(17)
The proof of Theorem 3 is provided in Appendix B.6 Here, the smoothness constant 4.g is not scalable with y [1I, therefore leading to a constant step size choice. Theorem B establishes the convergence rate of the fully-single-lop version of PBGD-Free in Algorithm [ The result shows that the algorithm converges the neighborhood of a stationary point for Fz(x). where the stationary gap is controlled by the flatness parameter (5. a). Specifically, for a (8, )-)-fat function with E 1.5).
). ensuring that the suboptimality gap remains small. For instance, for the PEFT problem in 3), 8(x) is often negligible, as per the discussion in Section 3.2 Moreover, the method follows single-loop update scheme, which is computationally more efficient
the convergence error scales as O 2(u
than other fully first-order methods 44 45 105 78 10,, as elaborated in the Appendix [B.7 A
comparison of the proposed algorithm with state-of the-art fully first-order BLO methods is provided in T
4 Numerical Experiments
In this section, we empirically validate our theoretical results through experiments on real-world tasks. In the main paper, will focus the LLM PEFT problem (3). Additional experiments, including
fair representation learning problem on the NLSY-7k dataset 3 80 and BiDORA fine-tuning (68], provided in Appendix C
4.1 Representation learning based LLM PEFT and its flatness
SFT enhances pre-trained L.LMs for downstream task adaptation, whereas DPO aligns them with human preferences. A straightforward way to achieve both goals is to sequentially optimize the
8

---

6.12
SFT Loss
DOMC
Post SFT tuning (e
FISA
0.00
0.0
0.00
DCPS
1LD PEFT (nn3t))
1.5
F2SA
BLO MEFT (4,
01 1.-
2500 5000 7500 0000011500150001/900
10.0
116
16)16.18)
(16,16)
136,16) 146
48
Time (seconds since start)
0.1
y=5
10
y-
15
y=
Figure 7: Train losses vs, time for different algorithms in solving (3) (or bi-objective learning for ALRIGHT)
Figure 6: Ablation study on penalty y and LoRA configuration
35 for PYTHIA-ID (
on LLAMA-3 3-3B [1].
Methods
DPO (TT, (/)
OSET TT. VT)
JDO ( v)
9SFT (TT,
V-PBGD 445
0.818
1.0309
0.8423
0.9533
BOME [105]
0.8332
1.1552
0.8402
0.9842
ALRIGHT [24]
0.8055
0,8656
0.8201
0.7855
PBGD-Free
0.7837
0.8516
0.8088
0.6688
Table 2: Comparison of different algorithms for PEFT LLAMA-3-3B
31
Results show the DPO
Loss J. SFT Loss &. for both the outcome (2r, yr) trained on solving (3 for different methods or
and the outcome (zt,, ?) from Post-SFT-tuning on another dataset with fxee-backbone, using the same dataset fixed time of training for each.
Two objectives. However, this often leads catastrophic forgetting [24], where applying DPO after SFT overwrites task-specific knowledge. To address this, we adopt the bilevel framework (3). which prioritizes SFT the LL to create human preference alignment. This hierarchical formulation effectively optimizes DPO conditioned on near-optimal SFT, thereby preserving downstream task performance. Moreover, this design is natural, as user preferences are generally consistent across tasks due to underlying psychological regularities. Additionally, the proposed BLO framework aligns with the post-SFT paradigm, where DPO is fine-tuned from a pre-trained model and SFT is applied to downstream tasks. In practical settings, is common to fine-tune only a lightweight head while keeping the backbone fixed or lightly updated 67 [06 (2).
reliable base model and applies DPO at the UL to guide the
In this paper, adopt decomposition of LLM into backbone model (e.g., attention weights) and an output head to formulate a BLO PEFT framework (3). Our method conforms to the PEFT practice by allowing the head to specialize in SFT tasks while training the backbone through DPO to capture generalizable preference representations. In our experiments, we adopt the low rank adaptation (LoRA) (35) to the backbone x for PEFT on LLAMA-3-3B [3]] and PYTIIAAI1 (6) using the Dahoas/ -w-rmm--h---mmh hh-rlhf dataset for DPO and the OpenOrca dataset (55) for SFT. Our code is adapted from the bilevel LLM post-tras post-training library sttps://gi h/ggithub.... com PosttLLL/////// BIPOST and experiment details are referred to Appendix C.3 As preliminarily demonstrated in Figure 5 this BLO PEFT problem in (3) features flatness (small 6), which further corroborated by the observation
in experiment that the L.. solution vī (x) and (x:) have fz- distance greater than 1, suggesting
negligible flatness constant 5(x) by 12
4.2 Ablation study and main experimental results for the PEFT problem
In this experiment, we consider evaluating methods on both S1) BLO PEFT learning phase via 3 to obtain a preference backbone æ, and S2) post-SFT tuning on a new dataset with the obtained preference backbone model to verify the representation quality and transferability of the backbone.
We first conduct an ablation study on the PYTHIA-16 1b to test the impact of the penalty constant and LoRA con- figuration on the PBGD-FFL Free method. We report the DPO and SFT loss un- der different settings for both (DT, yr) learned from S1) and (wT, Ø) from S2) in Figure
BLEU Score
Corpus and Senterse BLEU for BLG PEFT autput Sentense fo edit-S Srr-sinnnngg
0.36
0.30
BOME
F2SA
ALRIGHT
PBGD-Free
Figure 8: BLEU-4 Corpus and BLEU-4 Sentence Score (t)
for different algorithms for PEFT on LLAMA-3-3B [1]

---

Trade-off between DPO and SFT under different 7/- According to Figure 6 increasing ? degrades DPO performance while improving SFT for S1), indicating that a larger Y provides better LL optimality. Notably, the SFT improvement beyond 10 is marginal for S1), while the DPO performance significantly deteriorates, suggesting that ? z offers the best balance as our theory predicts.
Faster convergence over BLO baselines and stable training over bi-objective. Since second-order BLO algorithms are inefficient in large-scale LLM training, we consider first-order methods F²SA
45 and BOME [05] as BLO baselines. As shown in Figure PBGD-Free converges faster than the
BLO baselines. We additionally compare with ALRIGHT [24] an effective bi-objective algorithm, to validate the representation capability of BLO PEFT (3) formulation. ALRIGHT [24] exhibits less
stability during training (Figure 77. likely due to alternating between DPO and SFT objectives.
Transferability of preference backbone and strong SFT performance. Compared with S1), PBGD- Free in Figure(6]show enhanced SFT with comparable DPO performance on S2), suggesting it learns a transferable preference backbone x through BLO 3). Table 2 further quantifies these findings for other baselines, demonstrating that PBGD-Free achieves superior DPO and SFT performance. Notably, the backbone model x obtained by PBGD-Free attains the lowest SFT and DPO loss on S2), verifying the transferability of PBGD-Free. To further evaluate the quality of generated output, Figure &8 corroborates the SFT performance using the evaluation metrics BLEU score [65], where our method outperforms all baselines, further justifying its superiority in learning a good representation. More experimental results, including semantic analysis (Table 6 are provided in Appendix C.3
Concluding remarks
In this paper, we propose PBGD- Free, a penalty- based method for efficiently solving the nonconvex BLO problem without solving the value-functios subproblem of (2). We first show that, under general Lipschitz condition, the convergence of PBGD-Free has constant lower bound by the Lipschitz constant, which does not vanish unless the Lipschitz constant is sufficiently small. Motivated by empirical findings in representation learning, we then introduce a Hölder-like condition and prove that, when its constant is sufficiently small, the fully single-loop PBGID-Free algorithm achieves an iteration complexity of O(e-)) We further demonstrate that this Hölder-like condition with a small constant is strictly weaker than the small Lipschitz condition, and we verify this condition in pugresentation-laaning-----
LLM PEFT, fair representation learning, and BiDORA fine-tuning. Numerical experiments in the above problems demonstrate that the PBGD-Fre Free algorithm computationally efficient and can outperform the existing baselines across all three applications.
References
[1] Momin Abbas. Quan Xiao, Lisha Chen, Pun-Yu Chen, and Tianyi Chen. Sharp-maml: Sharpness-aware model-agnostic meta learning. In International conference on machine learning, pages 10-32. 32, 2022.
[2] Armen Aghajanyan, Anchit Gupta, Akshat Shrivastava, Xilun Chen, Luke Zettlemoyer, and Sonal Gupta. Muppet: Massive multi-task representations with pre-finetuning. In Proc. of the Conference on Empirical Methods in Natural Language Processing. 2021.
[3] Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[4] Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation lcarning for imitation learning via bi-level optimization. In International Conference on Machine Learning, pages 367-376. PMLR, 2020.
[5] Guillaume O Berger, P-A Absil, Raphaël M Jungers, and Yurii Nesterov. On the quality of first-order approximation of functions with hölder continuous gradient. Journal of Optimization Theory and Applications, 1 185: 17:3, 2020.
[6] Stella Biderman, Hailey Schoelkopf. Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Breen, Eric Hallahan, Mohammad Áflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning. 2023.
[7] Jérôme Bolte, Edouard Pauwels, and Samuel Vaiter. Automatic differentiation of nonsmooth iterative algorithms. In Advances in Neural Information Processing Systems, 2022.
[8] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. In Advances in Neural Information Processing Systems, virtual, 2020.
10

---

[9] Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends" in Machine Learning, Boston, MA, USA, 2015.
[10] Lesi Chen, Jing Xu, and Jingzhao Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint arXiv:2301 00712, 2023.
[11] Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory, pages 947-980. PMLR, 2024.
[12] Lisha Chen, Sharu Theresa Jose, Ivana Nikoloska, Sangwoo Park, Tianyi Chen, and Osvaldo Simeone. Learning with limited samples meta-learning and applications to communication systems. Foundations and Trends in Signal Processing, 1 2023.
[13] Lisha Chen, Quan Xiao, Ellen Hidemi Fukuda, Xinyi Chen, Kun Yuan. and Tianyi Chen. Efficient first-order optimization on the parcto set for multi-objective learning under preference guidance. arXiv preprint arXiv:2504.0000 02854, 2025.
[14] Tianyi Chen, Yuejiao Sun. Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In Proc. International Conference Artificial Intelligence and Statistics, 2022.
[15] Tianyi Chen, Yuejiao Sun, Wotao Yin. Closing the gap: Tighter analysis alternating stochastic gradient methods for bilevel problems. Advances Neural Information Processing Systems, Virtual, 2021.
[16] Ziyi Chen, Bhavya Kailkhura, and Yi Zhou. A fast and convergent proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization. arXiv preprint arXiv:2003. /6615, 2022.
[17] Kevin Clark, Paul Vicol, Kevin Swersky, and David J Fleet. Directly fine-tuning diffusion models on differentiable rewards. In International Conference on Learning Representations. 2024.
[18] Frank H Clarke. Optimization and nonsmooth analysis. SIAM, Philadelphia, PA, 1990.
[19] Mathicu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems, 2022.
[20] Bill Dolan and Chris Brockett. Automatically constructing corpus of sentential paraphrases. In Third international workshop on poraphrasing (IWP2005), 2005.
[21] Youran Dong, Junfeng Yang. Wei Yao, and Jin Zhang. Efficient curvature- hypergradient approxi- mation for bilevel optimization. arXiv preprint 2555v:2505.02 2025.
[22] Qingkai Fang, Shoutao Guo, Yan Zhou, Zhengrui Ma. Shaolei Zhang, and Yang Feng. Llama-omni Seamless specch interaction with large language models. arXiv preprint arXiv:2409 2409.06666. 2024.
[23] Sheng Fang, Yong-Jin Liu, Wei Yao, Chengming Yu, and Jin Zhang. qnho: quasi-newton meets bilevel optimization. In Proc. International Conference on Learning Representations, 2025.
[24] Heshan Fernando, Han Shen, Parikshit Ram, Yi 7hou, Horst Samulowitz. Nathalie Baracaldo, and Tianyi Chen. Mitigating forgetting in Ilm supervised fine-tuning and preference learning. arXiv preprint arXiv:2410. 15483, 2024.
[25] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In Proc. International Conference on Learning Representations, virtual, 2021.
[26] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning, pages 1165-1173 PMLR, 2017.
[27] 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, pages 1568-1577. PMLR, 2018
[28] Hongchang Gao, Bin Gu, and T'hai. On the convergence of distributed stochastic bilevel optimization algorithus over network. In International conference on artificial intelligence and statistics, pages 9238 9281. PMLR, 2023.
[29] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 2018
[30] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In Proc. International Conference Machine Learning, pages 2232-2241, 2019.

---

[31] Aaron Grattafiori. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The laama 3 herd of models. arXiv preprint arXiv:240.22178. 2024.
[32] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the itcration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748 3758, virtual, 2020.
[33] Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. Advances in Neural Information Processing Systems, New Orleans, LA, 2023.
[34] 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, 33(1 33(1):147-188) 2023.
[35] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen Zhu, Yuanzhi Li, Shean Wang, Lu Wang. Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLRR, 1(2)3, 2022.
[36] Yifan Hu, Jie Wang. Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual stochastic bilevel optimiza- tion. In Proc. Advances in Neural Information Processing Systems, 2023.
[37] Kaiyi Ji Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. arXiv preprint ar0iv:2205. 14224, 2022.
[38] Kaiyi Ji, Junjie Yang. and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882-4892. PMLR, 2021.
[39] Kaiyi Ji, Junjie Yang, and Yinghin Liang, Provably faster algorithms for bilevel optimization and applications to meta-learning. In Advances in Neural Information Processing Systems, 2021.
[40] Liuyua Jiang, Quan Xiao, Victor Tenorio, Fernando Real-Rojas, Antonio Marques, and Tianyi Chen.
A dual-l--ual---siistt penalty approach to bilevel optimization with coupled constraints. In Advances in Neural Information Processing Systems, 2024.
[41] Hamed Karimi, Julie Nutini, and Mark Schmidt. I Linear convergence of gradient and proximal-gradient methods under the Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, pages 795-811, 2016.
condition. In Machine Learning and Knowledge Discovery in
[42] Prashant Khanduri. Siliang Zeng. Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A optimal algorithm for stochastic bilevel optimization via momentumm In Advances in Neural Information Processing Systems, Virtual, 2021.
[43] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. preprint: 14pprin::412.6666 14/2.6980, December 2014.
arXiv
[44] 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, pages 18083-188 13., 2023.
[45] Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference on Learning Representations, 2024.
[46] Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Proc. Advances Neural Information Processing Systems, New Orleans, LA, 2023.
[47] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Association for the Advancement of Artificial Intelligence, pages 7426-7434, virtual, 2022.
[48] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: wtt.:1800000055 2018
[49] Risheng Liu, Jiaxin Gao. Jin Zhang. Deyu Meng. and Zhouchen Lin. Investigating bilevel optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44112):10455-10067, 2021.
[50] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A fulue-function--aal interior- point method for non-convex bi-level optimization. In International conference on machine learning, pages 6882-6892, 2021.
[51] Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Value- senee-fuuntiio-basee sequential minimization for bi-level optimization. IEEE Transactions Puttern Analysis and Machine Intelligence, 2023.
12

---

[52] Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang, Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In Proc. International Conference on Machine Learning, Honolulu, HI, 2023.
[53] Shih-Yang Yang Liu, Chien-Yi Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang- Ting Cheng, and Min-Hung Chen. Dora: Weight-decomposed low-rank adaptation. arXiv preprint arXiv:2402.09855, 2024.
[54] Xu-Hui Liu, Yali Du, Jun Wang, and Yang Yu. On the optimization landscape of low rank adaptation methods for large language models. In Proc. International Conference on Learning Representations, 2025.
[55] Shayne Longpre, Le Hou, Tu Vu. Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoe V Le, Barret Zoph, Jason Wei, et al. The flan collection: Designing data and methods for effective instruction tuning. In Pruc. International Conference on Machine Learning, 2023.
[56] Han Lu, Yichen Xie, Xiaokang Yang, and Junchi Yan. Boundary matters: A bi-level active finetuning method. In Advances in Neural Information Processing Systems, 2024.
[57] Songtao Lu. Tsp: two-sided smoothed primal-dual method for nonconvex bilevel optimization. In Forry-second International Conference on Machine Learning, 2025.
[58] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2): (000))1977-99999 1969,, 2024.
[59] Andrew Maas, Raymond E Daly, Peter Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. Proceedings of the 49th annual meeting of the association for computational linguisties: Human language technologies, pages 142-150, 2011. I.
[60] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pages 2113 2122, Lille, France, 2015.
[61] Pierre Marion, Anna Korba, Peter Bartlett, Mathieu Blondel, Valentin De Bortoli, Arnaud Doucet, Felipe Llinares-Lóue López. Courtney Paquette. and Quentin Berthet. Implicit diffusion: Efficient optimization through stochastic sampling. In International Conference on Artificial Intelligence and Statistics, 2025.
[62] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, Boston, MA, 2013.
[63] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803.02999 2018
[64] Rui Pan, Jipeng Zhang, Xingyuan Pan, Renjie Pi, Xiaoyu Wang, and Tong Zhang, Scalebio: Scalable bilevel optimization for Ilm data reweighting. arXiv preprint arXiv:2406. 19976, 2024.
[65] Kishore Papineni, Salim Roukos, Todd Ward, and Wei- Wei-Jing Zhu. Bleu: a method for automatic evaluation machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311-318, 2002.
[66] leva Petrulionyte. Julien Mairal, and Michael Arbel. Functional bilevel optimization for machine learning. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, 2024.
[67] Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. Adapterfusion: Non-destructive task composition for transfer learning. arXiv preprint arXiv 00247, 2020.
[68] Peijia Qin, Ruiyi Zhang, and Pengtao Xie. Bidora: Bi-level optimization- weighe-decompossed low-rank adaptation. arXiv preprint arXiv:2410.09758, 2024.
[69] Zhen Qin, Zhuqing Liu, Songtao Lu, Yingbin Liang, and Jia Liu. Duct: Decentralized bilevel opti- mization without lower-level strong convexity. In The Thirteenth International Conference on Learning Representations, 2025.
[70] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728-533777 2023.
2023.
[71] Zaccharie Ramzi, Florian Mannel, Shaojie Bai, Jean-Luc Starck, Philippe Ciuciu, and Thomas Moreau. Shine: Sharing the inverse estimate from the forward pass for bi-ee optimization and implicit models. Proc. International Conference on Learning Representations, 2022.
[72] Yi Ren, Shangmin Guo, Wonho Bae, and Danica Sutherland. How prepare your task head for finetuning. In International Conference Learning Representations, 2023.
13

---

[73] Donna S Rothstein, Deborah Carr, and Elizabeth Cooksey, Cohort profile: The national longitudinal survey of youth 1979 (nlsy79). International journal of epidemiology. 48(1):22-22)) 222,, 2019.
[74] Benjamin Scellier and Yoshua Bengio. Equilibrium propagation: Bridging the gap between energy-bascd models and backpropagation. Frontiers in computational neuroscience, 11:24, 2017.
[75] Amirreza Shaban, Ching-An An Cheng, Nathan Hatch, and Byron Boots. Truncated back- paokpprpagatton for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statisfics, pages 1723 1732. PMLR, 2019.
[76] Han Shen, Pin- Yu Chen, Payel Das, and Tianyi Chen. Seal: Safety-enhanced aligned Ilm fine-tuning via bilevel data selection. In International Conference on Learning Representations, 2025.
[77] Han Shen and Tianyi Chen. single-timescale analysis for stochastic approximation with multiple coupled sequences. Advances in Neural Information Processing Systems, 35:17415 17429,, 2022.
[78] Han Shen, Quan Xiao, and Tianyi Chen. On penalty-basee bilevel gradient descent method. In Interna- tional Conference on Machine Learning, Honolulu, HI, 2023.
[79] Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty- methods for bilevel reinforcement learning and RLHF. In International Conference on Machine Learning, Vienna, Austria, 2024.
[80] Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In International Conference on Machine Learning, pages 20156 201775 PMLR, 2022.
[81] Daouda Sow, Kaiyi Ji. Ziwei Guan, and Yingbin Liang. A constrained optimization approach to bilevel optimization with multiple inner minima, arXiv preprint 2rXXi:2203.011223 2022.
[82] Daouda Sow, Kaiyi and Yingbin Liang. On the convergence theory for hessian-free bilevel algorithms. Advances Neural Information Processing Systems, volume 35, pages 4136 4149, 2022.
[83] James H Stock and Francesco Trebbi. Retrospectives: Who invented instrumental variable regression? Journal of Economic Perspectivee, 17(3):177-194, 2003.
[84] Mao Tan, Zhuocen Dai, Yongxin Su, Caixue Chen, Ling Wang, and Jie Chen. Bi-level optimization of charging scheduling of battery swap station based on deep reinforcement learning. Engineering Applications of Artificial Intelligence, 105557, 2023.
[85] Vinzenz Thoma, Barna Pásztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcement learning for incentive alignment. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[86] Paul Jonahaan Lorraine. Fabian Pedregosa, David Duvenaud, and Roger Grosse On implicit bias in overparameterized bilevel optimization. In Proc. International Conference on Machine Learning, 2022.
Jonathan
[87] Xiaoyu Wang. Xuxing Chen, Shiqian Ma, and Tong Zhang. Fully first-order methods for decentralized bilevel optimization. arXiv preprint wwXiv:2410.193111 2024.
[88] Rachel Ward and Tamara Kolda. Convergence of alternating gradient descent for matrix factorization. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2023.
[89] Per-Ake Wedin. Perturbation theory for pscudo-inversee BIT Numerical Mathematics, 13:217-232, 1973.
[90] Quan Xiao and Tianyi Chen. Unlocking global optimality in bilevel optimization: A pilot study, In Proc. International Conference on Learning Representations, 2025.
[91] Quan Xiao, Songtao Lu, and Tianyi Chen. A generalized alternating method for bilevel optimization under the polyak-lojare lojasiewiez condition. Advances in Neural Information Processing Systems, New Orlcans, LA, 2023.
[92] Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating implicit projected sgd and its effi- cient variants for equality-constranne constrained bilevel optimization. In International Conference on Artificial Intelligence and Staristics, 2023.
[93] Quan Xiao, Hui Yuan, AFM Saif, Gaowen Liu, Ramana Kompella, Mengdi Wang, and Tianyi Chen. A first- order generative bilevel optimization framework for diffusion models. arXiv preprint 2502:2500008800 2025.
[94] Di Xie, Jiang Xiong, and Shiliang Pu. All you need beyond good init: for training extremely deep convolutional neural networks with orthonormality and modulation. In Proceedings of the IÉEE Conference on Computer Vision and Pattern Recognition, pages 6176-6185, 2017.
Exploring better solution
14

---

[95] Liyuan Xu, Heishiro Kanagawa, and Arthur Gretton. Deep proxy causal learning and its application to confounded bandit policy evaluation. Advances in Neural Information Processing Systems, 34:26264- 26275, 2021.
[96] Changdi Yang. Pu Zhao, Yanyu Li, Wei Niu, Jiexiong Guan, Hao Tang. Minghai Qin, Bin Ren, Xue Lin, and Yanzhi Wang. Pruning parameterization with li-level optimization for efficient semantic segmentation on the edge. In Proc. of the IEEF/CVF Conference Computer Vision and Pottern Recognition, 2023.
[97] Junjie Yang, Kaiyi Ji, and Yinghin Liang. Provably faster algorithms for bilevel optimization. arXiv preprint arXiv:2106. 04692, June 2021.
[98] Yifan Yang. Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. Tuning-free free bilevel optimization: New algorithms and convergence analysis. In The Thirteenth International Conference on Learning Representations, 2025.
[99] Yifan Yang, Peiyao Xiao, Shiqian Ma, and Kaiyi Ji. First-order federated bilevel learning. In Proc. of the AAAI Conference Artificial Intelligence, volume 39, pages 22029-22033 2025.
[100] Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proximal lagrangian value function approach and gessian-free algorithm. arXiv preprint (ttv:2401.16166 2024.
[101] Can Yaras, Peng Wang. Laura Balzano, and Qing Qu Compressible dynamics in deep overparameterized low-rank lcamiin& & adaptation. In Proc. International Conference on Machine Learning, Vienna, Austria, 2024.
[102] Jane J. Ye. Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM Journal Optimization, 10(4):943-962, 2000.
[103] Jane Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Difference convex algorithms for bilevel programs with applications in hyperparameter selection. Mathematical Programming, 198(2):1583 1616. 2023.
[104] Jane J Ye, Daoli Zhu, and Qiji Jim Zhu. Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM Journal on optimization, 7(2):81-55)) 507, 1997.
[105] Mao Yc, Bo Liu, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made casy: simple first-order approach. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, 2022.
[106] Elad Ben Zaken, Shauli Ravfogel, and Yoav Goldberg, Bitfit: Simple parameter- efficieen fine-tuning for transformer-hasee masked language-models. arXiv preprint arXiv:2106. 10/99, 2021.
[107] Emanuele Zangrando, Sara Venturini, Francesco Rinaldi, and Francesco Tudisco. debora: Efficient bilevel sptimization-basee low-rank adaptation. In The Thirteenth International Conference on Learning Representations, 2025.
[108] Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi- level actor-critic for multi-agent coordination. In Proc. of the AAAI Conference Artificial Intelligence, 2020.
[109] Jingzhao Zhang, Tianxing Hc, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelcrates training A theoretical justification for adaptivity. In Proc. International Conference on Learning Representations, virtual, 2020.
[110) Weipu Zhang, Gang Wang. Jian Sun, Yetian Yuan, and Gao Huang. Storm: Efficient stochastic transformer based world models for reinforcement learning. Advances in Neural Information Processing Systems, 36:271 17721166, 2023.
[111] Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang. and Sijia Liu. Advancing model pruning via bi-level optimization. In Advances in Neural Information Processing Systems, 2022.
[112] Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhiquan Luo. Why transformers need adam: A hessian perspective. In Proc. Advances in Neural Information Processing Systems. Vancouver, Canada, 2024.
[113] Nicolas Zucchet and João Sacramento. Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagation. Neural Computation, 34(12)2309-2346, 2022.
15

---

Supplementary Material for "Beyond Value Functions: Single-Loop Bilevel Optimization under Flatness Conditions"
Table of Contents
Preliminaries
16
A.1
Proof of Proposition
17
B
Improved Analysis under Flatness
17
Proof Observation I.
B.2
Detailed example for Observation
18
3
Proof of Lemma [
18
4
Proof Lemma
19
B.5
Stationary relations under flatness condition
20
B.6
Proof of 3
22
B.7
Additional discussion on singl- loop version of F SA 45
24
Additional Experimental Details
27
Additional details for toy example Figure
27
Representation learning problem on NLSY dalasel 77
27
LLM PEFT problem (3)
27
BiDoRa line-tuning problem
D Broader Impact
31
A Preliminaries
+ g(z, 1). We denote Notations. We define v(x) = min, g(x, =) and (x) min, 7 f(x
u) f-
(z = arg min, g(z, 2). St (z) = arg min, y f(z 1z, y) + g(z, 8). ds(y) == min lly - 2|I.
Definition (Lipschitz Continuity and Smoothness). We say a function f(z y) is l.pssiihhc if ((11,01). (x2, U2)
(1) f(z2, 12)ll S 4 [m1 v1] [r<; vell, If f is differentiable, we say f is -moothh on if f 4,,1 Lipschitz, i.e. V(z1, 31), (x2, y2):
(18)
[ v1) Vzf(222 U2); V fzf((1.v v1) - v 32llll & 11,1l|l=1:11 [1] - [x2 velll- (19)
Definition (PL condition). We say g( 8) satisfies μ Polyak- Lojassewic (PL) condition in y if
V (1, w)ll 2 y) v(x)).
(20)
Lemma 4 (AL Theorem 21). If g(x, y) is Lipschitt smooth and PL in with pg, then it satisfies the error bound (EB) condition with Mg. i.e.
VV v) 2 (ods)(=)()).
(21)
Moreover, it also satisfies the quadratic growth (QG) condition with Mgr i.e.
g(z, v) v(x) > [g
2 ds)(=)(u)
(22)
Conversely, if g( y) is fg,1 Lipschitz smooth and satisfies EB with Mg. then it is PL in with Hg/ Eg
Proposition (Complete version Proposition
77 45
Under Assumption 7 for any x, there
[1F <(=) 50
" - = -,
(23)
Additionally, for any 1i (z) e (z), vx(x) (z),
ds;(m)())) (z)) dsy (v, V on (x))))) = 211.,001111010000000000010 11
(24)
Moreover, for (x) = arg mig (2, =), there
[ VF,(=)] =0 (1
16

---

A.1 Proof of Proposition 2
First of all, Algorithm | can be viewed as biased PBGD algorithm with bias being
| V Vaf xil
V (x), v (x)) (V.g(v, -
20(( V v=,(,,,
Vaf(z (x)) -1
Ve 1
(4,a1l1 v. و
/4.11 7 / ((1,, uz) -00 (9)
(xx)))
where (a) is by plugging in (x, in (). this holds for arbitrary 87 (z), (z((x) as solutions to problems in (5): (b) follows triangle-ines inqquallyy, (c) uses the smoothness of and g: the first term in (d) is obtained by the QG property as ensured by PL condition and smoothness as per Lemma
4 via choosing y (are) arg yE8 lyy vi' and the second term follows Proposition 4 by
choosing Vny (z) arg min (m1) (xx) - z||: and (e) follows the linear convergence result of PL function 41 as v/ is the results from K-step inner update starting at v²- In this way, when taking K sufficiently large, there is ||b,]| & O(IV, (,, (x,))l Ol
Moreover, according to (x( is ((1) smmoohh. Therefore,
5 ()
+
||b.1|
1=0
SO(T O T
IV (. O(T-))(++))))))))))))))))) -(-)))))))))-))))00)000)0000)0)) OlGo). (25)
In this way, for sufficiently large T, Et= (VF 0(1,,))
Next, we will prove the lower bound of Algorithm by constructing a counterexample and show that the upper bound is tight. Consider [xx,y) = x² + 5.03 and g(æ, y) (y - x + 1)2. In this problem, (z) 2z + 1y,0 while (x, (1 - n)),, implying [ (1
2r. Using fixed stepsize 17. Ic+1 I₁ 1734 2(1 7)) || Therefore, for arbitrary small 6 > 0, there exists some To = OIn (In(c-)) (c) such that Algorithm
||2x++1|| 2(1 7)<|=
converges to ||az|| < for all 2 To, whereas Fx, ly.0. In this way, we have
1
(2:)) O(c) + 17.0
(26)
T- To
This indicates 2(17,)) is a tight bound.
B Improved Analysis under Flatness
B.1 Proof of Observation 1
For |yy - (z)) [I 2 1, by the 1,, = 8 Lipschitzness of f(x, y) in y. there is
[| v) v.) S l1,0llv -r -1ollly < at | (oy-)(())) (x)))
(27)
For small [1 - 1,w-,;(x)1 < Taylor's expansion gives
f(x, v) - f(a (x)) =
+ R(x, v)-
(28)
17

---

Here, R(x, y) is remainder. By Contin-Cn Gradient Condition which implied by the smoothness, there exists some 0 I c S 1,,12,, [[(,, w) S clly 2 (1) By Canchy-Schwartz' inequality, there is
[5]. 662] Section 2], a such that
(VV v. (x))1 <|IV , (1))
<b lly 1/ (z)l
< + Ily V (z)ll
(29)
where the last inequality holds as for a, h E 10 and a E (1, 2). there is ab I max (a,b)a b)2 v max(a, b) I a" + bo and here 81/a and |yy y (a) |- The observation therefore, holds.
B.2 Detailed example for Observation 2
The following example visualizes Observation
2
Example 2. We consider the I.I. objective g(r, y) = (y- - x)² and the UL objective
far, v) = -sin(y x) + 2) by x + exp (- (y x=)² sin (100(y =)))
2(0000))²
The LL problem g(z,y) y) is strongly convex in y, with (z) = Therefore, V ff, (z = 1000 is extremely large, which leads to loose upper bound for lly; (z) (z))) or (|((=)))))))))))())))) -F (=))
Lemma 7 However, this problem is (3e-3, 1.1)-flat with 5 at (z) x for E [-10, 10].
As shown in Figure 3 fxx,) exhibits fluctuations around (x) while remaining relatively stable elsewhere. This shows that flatness is weaker than requiring small y
B.3 Proof of Lemma 1
Proof. For any (z) E ST(),, (1) E (x),, there is
+ (o
v(x)
= () u()) S: (x V[ f(2,1, $f 32 (z))
(30)
In this way, according to the definition of Φ(x) and (x), have
[Ø(x)) F,(()] = min =E5;(2)
f(x,2) (f(z, (x)) + (x)) - v(z)))
{(,,1 (f(o,)) (2)) (0 v(z))) 5f(,,1(()) (f(e, (((x))(z)) + U1 // |b - x(())11
-1(((,))())) - flz, v (x))1 - Bly 1, (=))
S <cll)(()) - v, + - - - [1 -,((2)1
2 max a - - 3 +
2 3-a==aa(1 a (/2)((n))))))))))))))))))))))) -. +5= +6= -0:-0000aa000 - +
(31)
Here, (a) holds for arbitrary v (x) E (z) E (x)) by (30): (b) is from the Mg quadratic
growth condition of g(x,,) which is implied by PL according to Lemma 4 via choosing v (x)
arg ming || - (=]] (c) again uses (30 (d) follows the flamess of f(x at (z), (e) is
by formulating the problem as a maximization problem over = = [1)) - vt (rr and (f) is the
solution to this polynomial problem. Therefore, the first part is proved.
18

---

For the second part, as (z, -) + g(x,) :) being μ-PL for > y,, it is also μr y-QG by Lemma In this way, fixed any y > y², for any (x) E (x) and any Vn (z) E (1)), there is
7 (G ((n
( fl v7(()) + ((2,))))))) 2 (0
(32)
Moreover, following steps (d)-(d) as in (1). there is
left of 32 Vz + rg(2 =g(2, - rv(x)) (f (ffe)) (((x ruxx) -(0()) (10o:(/)))(((/())))--0000((----- v(x))
f(,, ([) -=(,, -
<o)ly](0)) (z)) + 2 S (1) (z)
(33)
Combining (32 and the above, there is
clvy - y (=)]l + ? &e
(o
2 2 d (0)((z))
(34)
for any (x) E (x) and (x) E (x) this way, for any (z) (x)), choose (x)
arg min))s;())) Ily Vi [1) there
ad L (x) + ) (1)
(35)
Similarly, for any (x) E (x), choose (z) = arg min ee) ||= Vi (r)]l. there is
(36)
For simplicity, denote x = dsy(a) (x)) (x)) (or r = (s)(2)) (yg (x))), there is
x- 22c 1 + 28 7 10
(37)
As E (1, for f 2 /
2- 12-1 25p 17-1 (o)
(38)
Since la + 666 s 5 2 2 + (6)P) for all 2 (as - is convex), there is
I ===2-aa) - - + +00 1
52 ( -ptan----ttttt 2/ + (2p-1) 1r====a'' o2 v -Ocly I'a + 6b)
(39)
In this way, we can conclude the following to include the scenario that x S V
x 00 x + 5 2).
(40)
B.4
Proof of Lemma 2
Define
8' 8'(x) [1[(,,,; (x))) (1)) (x))
=f (,,,,,,()))) -
clu, 1 (=))
(41)
where the equality is from f(x (z))) 2 s(x, 12 (x)) per 33)) We firstly show that f(x, N7 (x))
f(z v7 and (z) y (1) are both Lipschitz continuous.
19

---

For f(z, vx)) - f(z, v2 according to [1] Lemma F.3), there is
dr
= - /f/e///)))))////////////////////
< E + 1V 1n
y (+))
E (z x. uy (x)) + Ea| VV yag(z, 8 (2)) + Exll
(42)
where the inequality is by the triangle inequality and by denoting
E (x V v=((2,(((0))
E2 Vyl(x,
(z))
(43)
E3 = vo'voo (z)) + V vol( (x)) - V Vug(a, Sy (x))
E4 yzu (xx v. (z)) yag(a, (x)) - V yng( Vy (x))
V
By the smoothness of f. the Lipschitzness of V2g and by Proposition
we know that
| E21l Ell |all = (0>-))
(44)
Additionally, according to we know
1 + v5
|| (ar Dg (x)) + Fa] In this way, by the smoothness of and g. know 117 1 2 S , +1.1 and therefore,
V Vuol (f
|E = 1)
(45)
f(z, - y (z))
0
(46)
Ör
This shows that f(x, v2 (x)) - f(x, vf (x))
Lipschitz-contimuuus.
Fix any æ, denote arbitrary (z) E (z), (z) E (z), then for any x' X, there exists some
(z(2 E (z'), E (z') such that
( (1 cllv5(xx)) (1(x'))1
(0)
20 ||1b - vz)) - -112((x)) (z)
max
(
20(cr-
v1())) (,,(2') vi(a'))
2 (olo--(--)) (² + (1))()) - v((')l
@ - (a-1)) z'll
(47)
where (a) follows the mean value theorem, as 1a is continuous; (b) is from [,)) - 0²
O(> ") and the 1-Lipschitzness of the norm function; (c) uses by knowing that v (a:) and v (I)) are, respectively, T.g. Lipshitp for some constant T.y. T.y (78
and (d) achieved
In this way, we can conclude that 8x(x) is O(cy-(a-1) Lipschitz continuous. As 8(z) is ReLu function works on 8' (z)),, it is also Octy (a (a-1)) 1) Lipschitz continuous.
B.5 Stationary relations under flatness condition
Similar to 91 we first derive the stationary conditions for the original BLO problem under the flatness condition Definition instead of the Lipschitz continuity. Then we prove the stationary equivalence of the penalty problem with the original BLO problem (I).
20

---

B.5.1 Stationary conditions for original BLO problem 1
First, the original BLO problem can be equivalently written as its gradient based constrained form under LL PL condition as follows [005] 91]
min [(r,y), S.T. V v) 0. a.y
(48)
We aim to show that the Karush-Kuhn-TTurrr
conditions (KKT) conditions of 448) are necessary for the global optimality of the original BLO problem (T. thereby serving as its stationary conditions.
Prior works [I04 [02] have discussed that under the calmness condition, the KKT condition is a necessary optimality condition. Similar to [104] [02 [3]. we will prove that the calmness condition holds for 448) for our problem, even under our relaxed assumptions, so that KKT conditions, which our proposed algorithm converges to, are necessary for the optimality in the original BLO problem (I). Notably, the key difference is that the prior works require a global [T] local [33 Lipschitz condition of the upper-level objective. while we prove this under a more relaxed flatness condition of the upper-level objective. This makes the result applicable to a much wider set of problems. We first review the definition of the calmness condition below.
Definition 4 (Calmness, [8, Definition 6.4.1)). Let (x", ,y") ) be the global minimizer of the con- strained problem
min f(x, v) s.t. fe(x, v) = 0.
(49)
where Se tRd - Red and d 2 If there exist positive and M such that for any q E Rdd with lgall S 6 and any [1 v0) (x" yy" >1 S which satisfies fe(x', y²) 0, one has
f(x,, 3/) - f(x", .4" + M |all 2
(50)
then the problem 49 is said to be calm with M and
We will prove a general version for establishing that the KKT conditions of problem (48) serve as the stationary conditions of the BLO problem [. which only requires the UL objective to be continuously differentiable.
Lemma 5. Suppose that g(x,-) satisfies the PL condition and is smooth, and [(x, -) is continuously
differentiable. For the global minimizer (x", of BLO problem in ① (a.k.a (48)), then (48) is calm at its global minimizer (x" yy)), and therefore, the KKT conditions of (48) are the necessary conditions of the global optimality in (T).
Proof. First, for any x, since fzz -) is continuously differentiable, then fax :) is locally Lipschitz continuous around any y/, i.e. there exists a neighborhood of (y') := {y lly s' S c} and constant L max | ff, y)ll < such that f(x -) is Lipschitz continuous with constant over y (y").
Then consider Vq with ||ا|| < e, and Va' E (x*) and y/, s.t. Vug(z' v/) + = 0, then letting Ug Projsg(ar)( and according to Lemma 4 one has
e |لو|| = V, 2/Ill 2 Hylly/ voll
Since (x*, ,y") solves (48) and (x', ;yg) is also feasible (48). one has fxx,,²") S f(x', Mg). Thus,
(a) 2 -illy' - well 2 -Lllll (51)
f(x', - f(x", ,2")"" 1// - f(x', ma)
where (a) is due to the local Lipschitz continuity of f(x,-) with L : max (V
(11 justifies the calmness definition in 50 with M = H9
and
Therefore, under Assumption 2 the smoothness of f(x. implies that f(x. is continuously differentiable so that Lemma 5 holds. Note that Lemma also generalizes the results in [3] by
relaxing the global/local Lipschitz continuity assumption on f(z,) .) via continuously differentiable (ensuring local Lipschitz continuity).
We then aim to prove in Lemma 3 that the stationary point of the penalty reformulation approximately the stationary point of the original BLO problem in ( (i.c., the KKT point of (88 ).
2
21

---

B.5.2
Proof of Lemma 3
Proof. Let x² be the stationary point of the penalty problem (2) then we have (x")(*))] S c.
Then according (5) for Vyy E S (x*) and Vy, E (x"), we have
IV=f(=" U-) + (V V vn) - V v=g(=", ;b)))) Sc VV 24) 7 vgg(",, .B4)) Vug(#" ,bn))l E. We aim prove that (x* 84) is approximately the KKT point of 48 i.e. finite E R
(52a)
(52b)
Vvf (0)f(="',)++) + zyg(æ', 84 y,)w s (cc)
(53a)
VV v4) + vol(a" Uy ur S O(t)
(53b)
VVg((z B2)1l2 v O(e).
(53c)
The approximate LL optimality in (53ch is earned by Lemma] which gives ds;())(1)= O z- + + O = 60.56 27))
when 7 OE 2-0
Therefore, when d s E it holds that
Vv v-)1l² s (o = O(c + _ > O(c)
(54)
where the first inequality is earned by the smoothness condition. Moreover, by Taylor expansion of and letting Vn = yesm l1u, Vgll. holds that
V v==f(x" vz) + 7 vxul 3-) - yo)ll = c O - voll²) < O(e), V V,"" ,14) + V vug("" Vy) - 11 < + O(ly, - -1yl3)) < ((e).
where the last two inequalities are due to 54). Together with (54) and defining w 7(y+ - Vyg with
finite norm ||l|| O(e 3) O S 1, the point (x", Vyy, w) satisfies the approximate KKT
conditions in
B.6 Proof of Theorem 3
In the following, we start with a more general setting where x is bounded in a domain X' and the update of æ is conducted via projected gradient descent.
Denote the gradient approximate g: = V.f (I, v2 ). According to smoothness, we have
1e.1
(7(1441) - (x,) S(V F, (xx) - 9t + 9t, re+1 - xx) +
| - =2ll?
2
S |1411 xell²
[141
xzll2
V (I++1))) - gell|=14111111111111111 xell
2n
1
| - 12112
|2411 - 2rl VF, (2+41) gell
27
4m
|
2z.12 + V (I++1) gill
(55)
4n
where the second inequality uses 7 S 1 (gt. Fz+1 2τ) - 2rl by 9 Lemma 3.1] and Cauchy-Schward inequality; the third applies Young's inequality
For simplicity, denote h(x,y) = y -- y) + g(x, u). v²(x) mingey 1(x,, 1/, vi
arg mingey h(x,, and yi E arg men g(21, v), and the update bias b(x,) = (2()) It-
In this way,
[1b(;;))1 1
x. [ vi > V
(0 v2 ") V Veg(or, (al v2+ 11
(a)
2 V
(It: y.
V
11 + 27 | V2g(z.)77)
Vag(Ee, "\1
(6)
2212 |1411
vil + 00r
2(111)
+ +
22

---

2 4 f/, (h(az, 1211 - My
+ +0(7 2 + +8%)
( 4 12,1 - ()) v/) vn (z1)) 0(7 = + 8%)
(56)
where (a) applies the Young's inequality; (b) follows the smoothness f and Lemma | (c) employs the property of strong convexity; and (d) is by the descent theory for applying projected gradient descent on problems satisfying PL condition, see e.g. 41 Theorem 5].
Plugging 56 in 15). there is
(x+11) Fa( - (1.F)(())))
n 1 17)))(((()))) - v
+ t100 fللمل + 87)
(57)
Moreover, as h(x, is 4A,1 = - ,1,1 + 11,1 -smooth and (x) is Lun,1 = (1 + Lmoothh there is
MF--1, - - (z(+1)
(a) h(r v241) '0 (zt) (ahh(Tr v241) Vo" :t-1- - 221) + 1f(11,1 + +lon,1)
2141 It 1|2
2
71
(
& Man vit1) n² (zt) n1111112211 3/ 111 -h1 -1111 1221,,11 + +(a,,)
1
2
17
(9)
Sh(re: vit1) (xx) + n7.. //100 1197-11
2
112
+
I/411 F++1 1 (2
1|2
+ Lob
Io+1
2x 11
2z
2
(d)
nli,12
(h((22 V ) 0² (xt)) + n
(1,, + (1oh11)
xt112 1|2
<1 +
+
2
2z
(e)
(1 + nl,,1
2 (1 11" (z) (M) - 0² (xt)) +
Nn.11
172,1 + (ph,,
)||
r++t - 2t
V2 > 0.
2z
2
(58)
Here, (a) follows the smoothness of h(x, y) + (x) in x; (b) applies Cauchy-Schwartz inequality and the smoothness of h in y, (c) uses Young's inequality for any O; (d) is from the PL condition of h(, y) in y; (e) is similarly by the descent theory for applying projected gradient descent on h(x,)) :) satisfying PL condition [4 Theorem 5].
In this way, adding c(h(E v241) o (#141) to both side of (5). there is
1x(1+11) + c(h(Er+1, v242)
(x(+1))
<F,(1x) +
7 +
nln11
12(1n.1 + (ooh.)))
Tt+1 - Dee 112
2z
2
17
+ ( (1 + m
hn,12
(xx))) + 10100-200000 + +87).
Mam11
+
2
pr,c"
In this way, choose the following hyper-parameter,
c = 14
2 = 88hn,1
177 < 1
(59)
" S min
nn -nn ())
1n.1"
iee. c 0(1), n 0(1), there is
(z(44))) Fx(x)) + cchh(0411, v4z1) v (2(41))
23

---

Algorithm 2 Fully-single-loop FA 45
without momentum
1: imputs: initial points Wn; step size 7), 77, r7²: counters T.
2: for f 0, 1, 1,.,.., , 1 do
3: update Vi41 yi 110 V 1 vyg(a (t, yt)
4: update Vi+1 y? 17" uv f(r,. vi + V Vgg(z..
5: update 2(+1 2t 79t where Jt V vzf(z, 7V vag(o,z())
6: end for
7: outputs: (or,0?)
s <-8 IVF, c(h(rz, - (x+)) + n000 ---0 + 87).
-0-11
Denote DJ = (x - F3 (xT), D2 (h(x0: - (0 (h(2T: 177) - (xT)). Rearranging and telescoping gives
8(D, + cD2) (x,))l
+ +0
2لا 11
+ +67)
n/
t=0
21a-11 =0(7 + aan
(60)
where the last equality is achieved as (1) and 1y = (1) and by setting 7 0 This confirms that the trajectory 2; stabilizes on average. Moreover, the hyper-parameter choices in reformulate (58). which can be plugged in (56) to obtain
2=
(59
P. t-0 Mag
b 1
7"' -
Σ (h(a vi) - o'(x)) + O 2(m-1)
S SO(T
2(o-1) 1)
(61)
where the last inequality follows by applying Abel's summation formula series Σ a&br where ag = O((1 - 77" ) and K K- 2k by O(T-L + 2(a-1)
In this way, there
Ft (xt - 1) V Fr (2xe)
VF,(()))
Ft (x+
19t syb2)
" 2
41 F1+1
+ 2116.112
(62)
"1
where inequality is by Young's inequality. Therefore,
T-1
1 T
<2
It Tz41
+
|b:112
T
2=
2(o-1)
<0(T
(63)
where the last inequality is obtained by plugging in 660 and
61
S 1.5 and rearranging.
B.7 Additional discussion on fully-single-lop version of F 45
Since momentum updates in F'SA 45) introduce additional memory cost, this section, we look
into the fully-single-lopp version of SA 45 without momentum, i.c. at each iteration t, it updates:
vI+1 - 17 V v (Tt, ye),
and
(64)
v ーリ - 17" (V 5 ff v7) + vyg(o,,)7))
(65)
where 178 111 and 1/² < (1g,1 + + ) are the step sizes. We summarize the algorithm in 9.1
Algorithm 2 present the convergence results in the following theorem.
24

---

Proposition 5. Suppose all assumptions in Proposition 2 loop version of Algorithm 2 with rj
hold. For iterations using the fully-single-
(r gives
1 VF, [=
(66)
Proof. Denote the gradient upproximate 9t Vet( + 7 V=g(z.3(+1) Vag(a,,
According to smoothness, we have
1F11 |x+1 - xell?
(F))) gt + gt, I2+1
xz)
+
2
1
s |11411 =
|
xz212 + |V (1++1)))+1) - gelll114+1111 - xell
2n
1
1
S
24 | - 22112 + 41j
|1t41 - xz 1| + VF (2+41) - gell
7 IIE (1) 2| + n/ V P (T(+1) -ell2
(67)
where the second inequality uses 7) S 1 (gt, J++1 - xz) S - 2 by 9 and
Lemma
inequality; the third applies Young's inequality
Moreover, denote Max, y) f(, y) + g(1,z), y). v²(x) mingey Ma, v). si
arg minyey haxe, v) and vt" arg mingey ( w). by triangle inequality and Young's 's inequality, there is
IVF (2x) gel12
2 2 V V2 v7 V
+2
Ve(xz)]
2 11lu21+1 112 + 1 -f
2
2
- (()) 9.1 7/11
/ (Tt M1+1 -
7/4h
2
2
22, 7/4h
(1 -
212 9.1
(1
(1) - v(x)) u((())
7p
2 (1 (('ma)((((x)0))) - (xx)) + 22
2
21 7/th
(1 17" (g) 2)) uu()))
9.1 7/
2 21,,1 72
(1 7"" "1' )112 + +2 22 (1
(68)
The second to last inequality follows PL condition and the last inequality is by the descent theory for applying projected gradient descent on problems satisfying PL condition, see e.g. [4] Theorem 5].
Plugging (68 in (67). there is
( - F, S 2 (x)
+ uc,
+ ( (("((((("" - (x)))
クー > (11,))("_"")( (² (z.)).
(69)
Moreover, as h(x, v) is 1n,1 - --11// 1 +.,.1- and (x() is Lun = (1,2(1 + L3)-smooth, there is
((1 - (x(+1)
(4) < h(ar, Vin1) - n (xx) + (Vah(ar, vit1) (o Te+-1 - -x1) +
17 + (,n,1)
V (x;))1
2
172 + (.,11)
2 2a Von1) n (xx) + nl. 11 1 (Ix))
VF,(2x))
2
11² (In,1
+ (,r,1)
2h( Vir1) nd (xx) + n/.,1 2 1117-11
v. w
(z,
(x:))1))
2
2
25

---

(d)
nln.12 (h(22,07411) o0(x))) +
[14,1
(ba,1 + (lgh,1)
21 +
+
2
2z
(c)
12,,12 2
2 )(1 77" (1)(,,) v/) (x1)) + Nhn.1
1f + Lpt
S (1
42 0.
2z
2
(70)
Here, (a) follows the smoothness of 1(,; y) + et in x;; (b) applies Cauchy-Schwartz inequality and the smoothness of in yi (c) uses Young's ss inequality for any > O; (d) is from the PL condition of h(,, y) in y, (e) similarly by the descent theory for applying projected gradient descent on
h(z,- -) satisfying PL condition [1 Theorem 5].
Following similar analysis, g(x,, y) is 1.11.....00 -mooohh and v(x) is Lu,1 1, (1 + Lg) -g)-smo there is
((4++1,1211) v((e+1)
Nn.11 <(1 + n2.112 (1 - 11 Nb [g( - v(x+))
+ (f + (1,1) [VPP (71)
2
2x'
In this way, adding c(h(x1+11 v2+11 vh (x)+ and c' (g(g (122)) v(21+1)) to both side of (69,, there is
(Z(411) - Fx(()) + c(((x(11: v2t11 3d (x++1)) + (g( (0(1)4111(+1)) - v((c+1))
1//111
(/1,111 + 1,t
N9.11
(1
+ ( [x)F)(x)))
+ c
+
+ c'
4
2%
2
22
2
+ cc( 17(
11,12
+
)
()
vi 0² -xx)))
2
10,
+ +d(11
17(
1g.12'
+
212
9.1
4
(1-
(o -((x))
pc
In this way, choose the following hyper-parameter,
7p 1/2
= 7H 1
16c1,,1
2' 16d bg11
(72)
178 < !
17 S 1R
pp/(1117 n (1- ug) 47
S min
18o(In.11..a.p a (60((1111o.1) 1 + 2e
"n 4-21 m.1
ie. c, = 0(r), 0 there is
F,((1)1) - (x.) + c(h((141, -0 (x++1)) + (g( vi v(2441))
- - 1 8
[F + c(h((ze, vii - (²(x)) + c' c (g(2), v8 v(xx)).
Denote Dj (20) (xT)) D2 (h(20. vo) n (xo) (h(rr, v/) (b(r)) and
D3 = (g(0o, vg) - v(zo)) (g(2r.yf - v(zr)). Rearranging and telescoping gives
1 T-1
8 (D1 + cD2 + dDa)) = -(-21-1)
IVE (z)) 12
(73)
T
nT
t=0
where the last equality is because c, c' = 0(7), and 11-
The convergence of the fully-single-loop F2SA without momentum hindered by larger 7, which regulates the UL violation rate. While the general case requires =Oie -0.5 as per Lemmal] This shows that the fully-single-lopp version of F²SA, though computationally efficient, suffers from higher international cost.
26

---

C Additional Experimental Details
C.1 Additional details for toy example in Figure
In this section, we provide details for the toy example of PEFT BLO problem in Figure 2 We consider binary classification setting where the model parameters (a, y) consist of the UL variable x and LL variable with 0 E I2a The model implements a ID convolutional network with softmax activation:
class Sof SoftmaxlN Module)
def (self).
hidden mn. Convlld(in_chaneells: out cut_channels=1,
kernel_sizess stride=2, bias=False) self activactio nn. Sof.Sofmmax (dim=1)
self siff_iintt_wet init_
We specify the SFT datasets DSFT = {((1,))) v)}. and the DPO dataset DDPO = {(X2, yu. ye)) in Table 3 The BLO problem is specified in (3), where fDPO consists of DPO loss with 3 1 (70
plus an f2 regularization term (weight 0.01) and JSFT consists negative log-likelihoon loss and
the same regulariztion. The reference model is obtained via learning 9SFr(2, y) (parameterized with (x = - 5.34, y = -9.94)).
We apply our PBGD-Free algorithm in Algorithm in comparison with FSA 45 with 7 15, K inner loop to solve 55. and 5000 outer loop for both algorithms.
Table 3: Dataset specification for toy illustration
Input
Output
Feature
X1
y =
[100, 0.5,
X1
y' = [1.0,0.5, 0.5]
X2
Ye I
0.5.0.5,0.5,0.33
X2
Y/ = 0
1.,
C.2
Representation learning problem on NLSY dataset
77
BLO has proven effective in representation learning for obtaining a joint backbone model that captures unified task features and generalizes well to downstream tasks by only tuning the head 36 80). We test our algorithm on representation learning problem on the National Longitudinal Survey of Youth (NLSY) dataset [73). following the experimental setup in [80]. This problem aims to learn representations to predict normalized income via min fMSE x y: D1) s.t. y E arg min, fMSE(Z (x, y; D2). where D1. D2 datasets partitioned by gender. The representation model, parameterized æ, consists of two fully connected layers (hidden size 200, ReLU activation), and the predictor, parameterized y, is linear classification head.
y 44 95| 83
We compare our fully-single-loop PBGD-Free (with inner iteration K= 1) against FSSA 45 (with K = 2) and the ITD algorithm from (80). following the experimental setup in 80 As shown in Table 4 the performance gap particularly notable in efficiency, where FBGD-Free is over twice as fast as F2SA 45 and more than 30 times faster than the ITD-based approach (80), primarily because it omits the value-function part and the inner loop y (x)) Moreover, PBGD-Free achieves lower MSE than PBGD [44]. This improvement stems from PBGD-Free's ability avoid the bias prpropagttion inherent in PBGD's design. When both algorithms are single-loop (or nearly single-loop for small K 2), PBGD's reliance fixed penalty parameter amplifies initial inner update biases throughout training, slowing convergence, detailed in Appendix B.7 while PBGD-Free eliminates these -ddependent value function terms.
C.3 LLM PEFT problem
General Setup. We evaluate our PEFT framework B3 using the Dahoas/rm-hh-rrl dataset for DPO loss and the OpenOrca dataset for SFT loss. For training, we test one PYTHIA-Ib [6]
27

---

Methods
MSE
Time (s)
FASA [45]
1.9331 = 0.0794
12.33 = 0..44
Implicit [80]
2.1530 + 0.0455
169.69 69 + 0.36
PBGD-Free
1.8916 + 0.1245
5.15 + 0.06
Table 4: Performance results for different training methods on representation learning problem
NLSY-7k Dataset (73). The mean + standard deviation is reported for both the mean MSE and the mean time over 5 random experiments the test dataset.
Method
Avg Memory Used (MB)
Peak Memory Used (MB)
BOME
18834.53
21535.96
F'SA
16213.78
17622.43
ALRIGHT
1603
16107.45
PBGD-Free
16016.94
16180.89
Table Empirical GPU memory usage for each method over 3 epoches of training.
model with 1800 samples for each dataset (batch size 16) and the LLAMA-3-3B (2 model with 4800 samples (batch size 32). Both models are adapted with LoRA (ALPHA 16, RANK 16) and treat LoRA PEFT weights on the attention layers as H. the last layer linear head y. The learning rate is set to 1 x 10-5, using Adam 43 as the optimizer. All experiments were conducted on cluster of NVIDIA A6000 GPUs, each with 40 GB of memory, Training was performed using PyTorch with the DeepSpeed library https: /tt::///tttttt com/ Seapppeeedaa/DeepSpeeee optimize memory usage and distributed training efficiency. We consider time-limited experiment under a consistent computational budget, reflecting real-world constraints where training time is often a critical factor.
to
Algorithm hyperparameter. We use a penalty constant of 7 = 10 for our proposed PBGD- algorithm (Algorithm D with single inner loop (K 1). For the baseline F2SA algorithm || 45). we set 10 with K 3 inner updates for training LLAMA-3-3 3-33 [31), and K 5 for PYTHIA- 1b (6. For the BOME algorithm, we similarly use K 3 and K inner loops, adopting its hyperparameter 17 = 0.5 for calculating the penalty constant, as suggested in [105]. For the ALRIGHT
algorithm (24), we use its default setting of = 0.5 as suggested in literature [24]. Since the
ALRIGHT algorithm in [24] is a bi-objective learning algorithm that does not have the representation
learning capability, we examine it on an alternative formulation miin..yl/Doott
(SFT
Faster training than BLO baselines and more stable over bi-objective. As presented in Figure g when training PYTHIA-Ib (6) on the PEFT problem (3). our PBGD-Free algorithm demonstrates the
fastest convergence compared to the baseline BLO methods FSSA I 451 and BOME [T05), both of which fail to converge within the given time budget. Additionally, PBGD-Free shows greater stability compared to its bi-objective counterpart ALRIGHT (24). Table rreeorrs the average and peak GPU memory consumption over 3 epochs for all compared methods, illustrating that PBGD-Free maintains memory footprint comparable to the baselines.
Better transferability to new task. Figure TO further illustrates the performance of the outputs from BLO PEFT learning (3) in the subsequent post-SFT-tuning phase S2). The BLO baselines (F2SA and BOME (105), D. which did not achieve convergence in the initial PEFT phase due their higher time complexity, tend to sacrifice DPO performance when improving SFT performance during POst-SFT tuning S2). In contrast, PBGD-Free algorithm and its bi-objective counterpart ALRIGHT demonstrate the ability to preserve strong preference alignment (DPO) while conducting SFT training in S2). This shows that the preference backbone learned by both of them can be adapted to new task by fine-tuning only the linear head to achieve strong SFT performance. Notably, the BLO PEFT outputs trained by PBGD-Free achieves better SFT performance with substantially lower SFT loss, highlighting the advantage of the prioritization of SFT in our BLO formulation 3 This structure allows for more powerful SFT tuning head, whereas bi-objective training methods tend to oscillate between potentially confficting objectives, thereby limiting their SFT performance.
[T
45
24
28

---

Example of SFT Evaluation Performance
Human: Generate approximately fifteen-word sentence that describes all this data: Midsum- mer House eatType restaurant; Midsummer House food Chinese; Midsummer House priceRange moderate; Midsummer House customer rating out of 5; Midsummer House near All Bar One
PYTHIА-1b [6]:
BLO-PEFT SA [45)):
BLO-PEFT (PBGD-Free):
Midsummer House staff restaurant priced restaurant restaurant. good-5 star rat- ing. and in All Bar One.
Midsummer House is a restau- rant priced restaurant restau- rant with a 3-5 customer rat- ing. located near All Bar One.
Midsummer House mod- erately priced Chinese restau- rant with a 3/5 customer rat- ing. located near All Bar One.
You will be given a definition of a task first, then some input of the task. This task is about using the specified sentence and converting the sentence to Resource Description Framework (RDF) triplets of the form (subject, predicate, object). The RDF triplets generated must be such that the triplets accurately capture the structure and semantics of the input sentence. The input is a sentence and the output is a list of triplets of the form [subject, predicate, object] that capture the relationships present in the sentence. When a sentence has more than 1 RDF triplet possible, the output must contain all of them. AFC Ajax (amateurs)'s ground is Sportpark De Toekomst where Ajax Youth Academy also play.
Human:
LLAMA-3-3B [31]
BLO-PEFT SA 45
BLO-PEFT (PBGD-Free):
[["AjaxFCC Ajax (amateurs)", "playsGround". "Sportpark De Toekomst"], ["Ajax Youth Academy". "has at". "Sportpark De Toekomst"]]
[["AAaxFCC Ajax (amateurs)". "plays ground", "Sportpark
[["AFC Ajax (amateurs)", "has ground", "Sportpark De Toekomst"), ["Ajax Youth Academy", "plays at", "Sport- park De Toekomst"]]
De Toekomst"), ["Ajax Youth Academy", "has at", "Sport- park De Toekomst"]]
Table 6: Examples of SFT evaluation performance for PYTHIA-16 6 ---M [3 and their corresponding BLO-PEFT B results via our PBGD-Free Algorithm | and basline F'SA marked in red indicates incorrect outputs, orange indicates partially correct outputs that follow some of the instructions, and green indicates fully correct outputs that match the expected instructions.
45 Text
Better SFT performance while maintaining preference learning. As illustrated in Table 6 the outputs generated by PBGD-Free demonstrate more precise and semantically accurate extraction, highlighting its superior SFT performance. In Figure 12 present the loss metries performance throughout post-SFFT-tning phase for LLAMA-3-33 B1 in addition to the results presented in Section 4 We observe that our backbone x trained on BLO PEFT (3) via PBGD-Free retains its lowest DPO rates throughout Post-SFTTtuning. Figure I1 shows the quantitative results of the preference alignment using average reward gap and win rate. Together with Figure g they indicate that the backbone preference model by the PBGD-Free maintains the first-tier DPO performance for preference alignment while enhancing the SFT performance by only fine-tuning the linear head. The slight DPO drop in Figure 11 of PBGD-Free compared with ALRIGHT is because it prioritizes better SET performance, which restricts the feasible search space of representation model optimizing at the UL. However, since the representation evaluation criterion prioritizes strong SFT performance achieved by fine-tuning only the linear head, and treats preference alignment as a secondary goal, PBGD-Free remains the top-performing method. Moreover, according to Figure 7 PBGDD-rees is more stable during the training compared with ALRIGHT. Additionally, Table provides the SFT output comparison given by PBGD-Free and F'SA on PYTHIA-Ib lb (6). LLAMA-3-3B [1I, from which we can see that both methods improve the response quality over the pre-trained model through BLO PEFT 3), while PBGD-Free generates better responses and follows the human instructions well.
6
Higher-rank LoRA enables finding better preference backbone via PBGD-Free. The last 2 columns in Figure [ show that a higher-rank LoRA better preserves DPO with comparable SFT performance. It is likely because higher-rank LoRA provides more over-parameterizztion,, which ensures a more benign optimization landscape for the representation parameter 101 54 and thus enables globally finding a better representation model (90].
29

---

DPO Loss
LONE ELOVAT
390
SFT L
7264
SFT Loss
2-
1000 2000 3000 4000 5000 6000 7000
1000
1200
Time (seconds since start)
Time (secands since start)
Figure 9: Train losses time with STRIDE 50 for different algorithms in solving (3) (or biobjective learning for ALRIGHT (24) on PYTHIA-Ib [6.
Figure 10: Train losses vs. time with STRIDE 50 for different algorithms in Post SFT- tuning phase on PYTHIA-IV lb [6].
Win (xY, yr) Win Rate (Xy, 91
0.5
Augerage Rewandd Gap
DPO Loss
0.85
ROME
0.4
Win Rate (66
0.80
54-
52-
Avg. Relward Gap (X,, X+)
0.2
0.2
SFT Loss
1.5
FICA
50-
Avg. (tr.))
BOME
F25A
ALRIGHT PBGD-Fre Free
0.0
Figure 11: Average Reward Gap (t) and Win Rate (1) for different algorithms for PEFT LLAMMA-3-1 3--33 on [31] with the output (IT, yr) ) via each method in
500
1000 1500 2000 2500 3000 3500 Time (soconds
Figure 12: Evaluation of DPO losses and train SFT loss vs. time with STRIDE = 50 for different algorithms in Post SFT-tuning phase on for PEFT LLAMMA-3- 3-33 [3].
S1) and the outcome (IT, 9) from post-SFT-tuning on another dataset with fxed-backboone in S2).
C.4 BiDoRa fine-tuning problem
One of the recent applications of bilevel optimization lies in the field of Large Language Finetuning. (68] proposed BiDoRa, which considers fine-tuning using DoRa (53) by training on a BLO problem
min ii (m, o" (m1) s.t u² (m) = lir (m, o² (m) + pl((v
(74)
m
where m is the magnitude and is the direction matrix for the low-rank incremental direction, 14 (m, v) and (m, v) are respectively loss functions for fine-tuning training dataset splitting into large and small on proportion 0.66 to 0.67, and R(v) is the Gram regularization loss [94] with constant p taken as les
We conduct experiments on Microsoft Research Paraphrase Corpus (MRPC) dataset 200 and Internet Movie Database (IMDb) in Hugging Face by fine-tuning Bert model [59] We apply fully-single-lopp
versions of PBGD and PBGD-Free in Algorithm I to solve the problem in Section 77 and compare it
with training using DARTS (88) the algorithm used the original BiDoRa algorithm [68], and the
naive results trained on milm,,r ler (m, 2) where by is the combined loss for training dataset including the ones used for both 1t and Iú, for DoRa [53] The experiment is conducted on a single NVIDIA RTX A5000 GPU (24GB) using CUDA 12.2 and NVIDIA driver version 535. 113.11.
As illustrated in Table 7 training BiDoRa using PBGD-Frea in Algorithm achieves the best performance in terms of test accuracy. It is more efficient than training using PBGD cuts the inner loop. Notably, it performs even better than the fully-single-lopp of F2SA 11 with the convergence results in Proposition and Theorem
This is consistent
Methods
MRPC
IMDb
BiDoRa- PBGD-Fre
0.839 + 0.006
0.873 + 0.007
BiDoRa-FPSA
0.820 + 0.014
0.866 + 0.016
BiDoRa-DARTS
DoRa
0.832 = 0.010
0.872 + 0.010
Table 7: Test accuracy (%) on training the finetuning parameters using BiDoRa-PBGD comparison with DARTS [48), the algorithm used in [68], and with directly training DoRa 53 It represents the accuracy mean + standard deviation on 20 random training experiments. The "/" represents didn't
converge in 10 times the time used in training DoRa.
30

---

D
Broader Impact
This paper mainly focuses on developing an efficient BLO algorithm with a theoretical guarantee. By applying the proposed method to representation learning based PEFT and BiDORA, our work contributes to the broader development of parameter efficient LLM fine-tuning. Potential societal impacts include applications in creative content generation, data augmentation, and machine learning- based simulations. While we acknowledge the possibility of unintended uses, we do not identify any specific societal risks that need to be highlighted in this context.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the main contributions, including the development of PBGD--Fres Free, fully first-order, single-loop bilevel optimization algorithm that eliminates value function evaluations. The claims are supported by theoretical analysis and experiments, demonstrating improved convergence and scalability for LLM fine-tuning, aligning well with the paper's core contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The paper discusses limitations related to the reliance flatness conditions, which are critical for the efficiency of the proposed PBGD-Free algorithm. also ac- knowledges the assumption of joint (x, y) dependency in the upper-level objective (i.c.,
Justification:
I (ax, v) # f(w)).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "LLimitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
32

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper provides a complete set of assumptions and detailed proofs for each theoretical result, including clear numbering and cross-referencing in both the main text and supplementary material. The assumptions are explicitly stated alongside theorems, ensuring that the analysis is rigorous and well-supported. Additionally, the main paper includes observations that guide intuition, with full formal derivations available in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The paper provides sufficient details for reproducing the main experimental results, including hyperparameter settings, model architectures, and dataset descriptions. clearly outlines the training procedures, evaluation metrics, and computational resources used, ensuring that the main claims and conclusions can be independently verified. Ad- ditionally, the supplementary material includes further implementation details, enhancing reprodueibility.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
33

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and data required to reproduce the main experimental results of this paper are included in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. cccpppblcc/guiesss httpp///w/c/uuuudd//dduuuuusiiss
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides comprehensive description of the training and test settings for all experiments. We provide key the Appendix, and provide the detailed implementation in supplementary material.
as described in the main paper or in
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
34

---

Answer: [Yes]
Justification: See Section and Appendix C
Guidelines: This paper provides experiment results with multiple rounds of experiments, justifying the statistical significance of the experiments.
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етгог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
See Section C For fair representation learning, we report the total runtime in We report the computation resourees for representation learning based PEFT in Appendix and for BiDoRA fine-tuning.
Justification:
Table 4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The authors obey the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
35

---

10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix D
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release new models and dataset, but utilize the existing ones. We focus on new problem formulation via BLO and proposing efficient algorithms using existing
LLM models and dataset.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite all the code based and datasets we using in Section
36

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release the code through anonymized zip file and provide all the details of training parameters in in Section and Section C
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
37

---

Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
The core method we developed is original and completely without LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy htttps///eaenrpseecc//ooooeeeeep for what should or should not be described.
38


Reviews:
[{"review_id": "0CnmjrR0io", "reviewer": "Reviewer_8EAT", "summary": "This paper addresses the computational inefficiency of bilevel optimization (BLO) algorithms often used in machine learning applications such as fine-tuning large language models (LLMs). Traditional BLO methods typically require expensive Hessian-vector computations or nested loop updates, which are impractical for large-scale problems. To overcome these challenges, the authors propose a computationally efficient, fully single-loop algorithm called PBGD-Free that eliminates the need for lower-level value function evaluations while retaining first-order updates. By leveraging a new flatness (Hölder-alike) condition for the upper-level objective, they provide theoretical guarantees of convergence for their method. Empirical results on parameter-efficient LLM fine-tuning and other bilevel tasks demonstrate that PBGD-Free achieves significant improvements in efficiency while matching or surpassing the accuracy of previous state-of-the-art methods.", "questions": "1. The authors state that the proposed method is more computationally and memory efficient than existing methods. However, no empirical evidence is provided to substantiate this claim. I recommend including results such as (1) convergence versus wall-clock time, and (2) peak memory usage for the proposed method and the baselines.\n\n2. In LLM applications, DPO is typically applied as a post-SFT stage. Employing bi-level optimization in this context is uncommon. Additionally, MT-Bench is often used as a standard testbed under this setting instead of objective value or BLUE scores.\n\n3. Adversarial attack scenarios or mitigating catastrophic forgetting are more common considerations in this area. I strongly encourage the authors to explore and evaluate their approach in these settings.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. This paper presents a novel, single-loop, value-function-free algorithm for bi-level optimization. The authors provide theoretical guarantees of convergence, and the proposed method empirically outperforms existing approaches.\n\n2. The introduction of a new flatness condition to establish the convergence of the algorithm is notable. This condition may also prove valuable for future research in this area.\n\n**Weaknesses**:\n\n1. The paper does not discuss the empirical computational and memory costs in comparison to existing methods. (Please see my comments in Question 1.)\n\n2. The experimental problem formulation does not reflect a typical setting for LLMs. (Please see my comments in Questions 2 and 3.)", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and the constructive review. Our response to your comments follows.\n\n**W1 & Q1. Empirical computational and memory costs. (1) convergence versus wall-clock time, (2) peak memory usage for the proposed method and the baselines.**\n\n| Method        | Avg Memory Used (MB) | Peak Memory Used (MB) |\n| ------------- | -------------------- | --------------------- |\n| BOME      | 18834.53             | 21535.96              |\n| F²SA      | 16213.78             | 17622.43              |\n| ALRIGHT   | 16031.86             | 16107.45              |\n| **PBGD-Free** | **16016.94**     | **16180.89**          |\n\nWe sincerely thank the reviewer for this insightful suggestion.\n\nFor **wall-clock time versus convergence**, we have reported these results in Figures 7 and 9 in Appendix for the PEFT experiments. Our method, PBGD-Free, consistently demonstrates faster convergence and achieves superior final performance compared to the baselines. Additionally, Table 4 presents a summary of efficiency on the NLSY representation learning task, where PBGD-Free attains the best performance with the shortest wall-clock time. We appreciate the reviewer’s attention to this aspect and look forward to further clarifying these results in the revision. \n\nFor **memory costs**, we provide empirical memory usage measurements during the rebuttal period for completeness. The table above summarizes the average and peak GPU memory consumption over 3 epochs for each method. PBGD-Free exhibits a memory footprint comparable to the baselines, underscoring its practical efficiency. Coupled with its superior convergence and performance, this highlights the strengths of our approach. We are grateful to the reviewer for encouraging us to share these valuable insights.\n\n    \n**W2. Motivation and design of experimental setting for LLM PEFT.**\n\nWe thank the reviewer for this insightful question, and the opportunity to clarify the motivation behind our bilevel optimization framework for parameter-efficient fine-tuning (PEFT), introduced in Eq. (3):\n\n- Upper Level: DPO objective, optimizing backbone parameters $x$;\n- Lower Level: SFT objective, optimizing a lightweight linear head $y$.\n\nOur design is motivated by both theoretical considerations and practical needs in LLM deployment, as briefly discussed in Section 4.1 and Appendix C.3. Due to space constraints, we did not expand on these points in the main text, but we re-clarify them here:\n\n(1) It operates in a post-SFT setting, where DPO is fine-tuned from a pretrained model and SFT is applied to downstream tasks. This setup reflects standard practice in LLM deployment, where models are adapted rather than trained from scratch, and human preferences are often shared across downstream tasks. \n\n(2) Bilevel structure is to mitigate the catastrophic forgetting issue in sequentially fine-tuning SFT followed by DPO [24], as DPO may overwrite task-specific knowledge. The hierarchical structure in the bilevel formulation enables optimizing DPO conditioned on a near-optimally learned SFT, helping to preserve downstream task performance. \n\n\n(3) In real-world applications (e.g., industry use cases), it is common to fine-tune only a lightweight head for specific tasks while keeping the backbone fixed or lightly tuned [Pfeiffer et al., 2020] [Zaken et al., 2021]. Our method aligns with this PEFT practice by allowing the head to specialize for SFT tasks, while learning the preference backbone with DPO for generalization and alignment.\n\n\nWe appreciate the reviewer’s suggestion and will revise the manuscript to explicitly highlight these three motivations for using the bilevel framework in PEFT.\n\nReference\n>- Pfeiffer, Jonas, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. \"Adapterfusion: Non-destructive task composition for transfer learning.\" arXiv preprint arXiv:2005.00247 (2020).\n>- Zaken, Elad Ben, Shauli Ravfogel, and Yoav Goldberg. \"Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models.\" arXiv preprint arXiv:2106.10199 (2021).\n\n\n**Q2. MT-Bench is often used as a standard testbed under this setting instead of objective value or BLEU scores.**\n\nWe appreciate the suggestion to use MT-Bench for evaluating alignment. However, we would like to clarify that our use of BLEU is solely for assessing supervised fine-tuning (SFT) quality, not alignment. The BLEU score measures how closely the model’s output matches the reference by evaluating the overlap of words and short sequences (n-grams), providing a standard metric for generation quality. It is a well accepted metrics for SFT performance [Papineni et al., 2002]. BLEU scores and training loss illustrate that our bilevel optimization effectively improves language generation under supervised objectives.\n\nFor alignment, we report the Average Reward Gap (Appendix Fig. 11), computed from a learned reward model. This directly reflects the policy's alignment with implicit preferences. Together with the loss objectives $f_{DPO}$, $g_{SFT}$ , these metrics show that our bilevel framework learns a DPO-aligned model conditioned on near-optimal SFT. Specifically, it shows the best supervised performance across baselines (see BLEU score and $g_{SFT}$ in Table 2, Figure 8), and great DPO alignment. \n\nDue to **the lack of OpenAI API access**, we are unable to run MT-Bench evaluations, which rely on GPT-4-based judgments. We believe our current evaluation setup captures both supervised and alignment perspectives, and we plan to incorporate MT-Bench in future work when resources allow.\n\n**Q3. Consider Catastrophic forgetting and adversarial learning.**\nWe thank the reviewer for the insightful suggestions. In fact, one of our motivations for adopting a bilevel framework is to address challenge of catastrophic forgetting, which is effectively mitigated by the hierarchical structure of the bilevel formulation. See details in Point (2) to W2. \n\nThe focus of this paper is to tackle the technical challenge of solving bilevel optimization problems using a fully single-loop, first-order algorithm — a problem that is notoriously difficult. Our goal is to develop a method with efficient convergence behavior that matches standard gradient descent, while being scalable and practical. To illustrate this, we use LLM fine-tuning as a concrete and motivating application.\n\nWe agree that both catastrophic forgetting and adversarial robustness are compelling application areas for our method and look forward to exploring them in future work.\n\nWe thank the reviewer again for recognizing the contribution and novelty of our work. We hope our responses help address any remaining concerns and further highlight the strength of our results. We would be grateful if the reviewer could take these clarifications into account during the final evaluation and consider a higher score."}, {"review_id": "n6mkp0pp7S", "reviewer": "Reviewer_txG5", "summary": "The paper proposes a method called PBGD-Free for bilevel optimization under a flatness condition. Compared with prior methods such as F$^2$SA that needs to solve two lower-level problems of the same condition number, the PBGD-Free only solves one, which make it more efficient in practice. Another benefit of the flatness condition is that it allows using single-loop updates,  while prior works without this condition requires $O(\\log \\epsilon^{-1})$ number of inner loops.", "questions": "See the weakness part.", "limitations": "See the weakness part.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength** Each claim in the paper is well-supported by examples, theorems and experiments. The paper introduces a novel method that is more efficient in practice and provide conditions when the method can converge.\n\n**Weakness** \n\n1. The story of the article is self-consistent, but it doesn't completely convince me. For example, maybe I can come up with another simple explanation: in practice especially neural network training experiments, the network is over-parameterized such that $g^\\ast(x)= 0 $. Consequently, the penalty function $ f(x,y) + \\gamma (g(x,y) - g^\\ast(x))$ is equivalent to  $f(x,y) + \\gamma (g(x,y) $. Therefore, you can also skip the inner loop to approximate $g^\\ast(x)$. I think my story is also self-consistent and can be supported by experiments. \n\n2. I can not understand the necessity of using bilevel optimization in LLM PEFT experiments. Why could the bilevel PEFT be better than the standard PEFT training? I think it is still very uncommon to use bilevel optimization in PEFT.\n\n3. The parameter setting of $\\gamma = \\Omega(\\delta^{-\\frac{2-\\alpha}{\\alpha }}) $ in Line 810 is not correct. For instance, if $\\delta=0$ then such a setting indicates that $\\gamma = +\\infty$. I think the parameters from Line 810 to 817 should be checked, although I believe the final result is still correct. \n\n4. (Minor) The reference [36] by Feihu Huang et al., is flawed, and I think it should be removed from the citations.", "was_revised": true, "final_justification": "I have raised the score to 4.", "rebuttal": "We thank the reviewer for recognizing that \"each claim in the paper is well-supported by examples, theorems and experiments\", and for providing insightful suggestions. Our response for your comments follows:\n\n**W1. Whether the problem can be explained via $f+\\gamma g$ while $v(x)=\\min_y g(x,y)=0$?** \n\nWe thank the reviewer for this insightful observation. Indeed, in certain **over-parameterized settings**, where the lower-level (LL) objective $g(x, y)$ can be minimized to zero for any $x$, the bilevel problem reduces to optimizing $f(x, y) + \\gamma g(x, y)$.\n\nHowever, this condition does **not generally hold** in practical scenarios such as **PEFT**. In PEFT, the LL variable $y$ typically represents a **lightweight linear head**, rather than a highly over-parameterized module. As a result, $\\min_y g(x, y)$ will not achieve zero (or constant).\n\nIn fact, **the flatness assumption can still hold even when the LL problem is not over-parameterized**. This subtle but important point is emphasized and formally discussed in Section 3.1 of our paper.\nTo further understand this, we conducted a follow-up experiment based on the PEFT setup described in Appendix C.1. This example is non-overparameterized with only 2 variables, and directly minimizing $f + \\gamma g$ led to a solution that was more than 5 units away (in Euclidean distance) from the bilevel solution. Although we are unable to include plots in this rebuttal, we hope this observation helps illustrate the necessity of preserving the bilevel structure in non-overparameterized cases like PEFT. However, this example features flatness, as discussed in Section 3.1, while our PBGD-Free algorithm leads to convergence to bilevel solution.\n\nMoreover, directly omitting the value function $v(x)$ when it is zero leads to a different algorithm than ours. PBGD-Free updates $x$ using $\\nabla\\_{x} f(x, y^{\\star}\\_{\\gamma} (x))$,\nwhereas the latter uses $\\nabla\\_{x} f(x, y^{\\star}\\_{\\gamma} (x))$ + $\\gamma \\nabla\\_{x} g(x, y^{\\star}\\_{\\gamma} (x))$. \nFor analyzing the convergence of PBGD-Free, $v(x) = 0$ is insufficient, as discarding the  $\\gamma \\nabla\\_{x} g(x, y^{\\star}\\_{\\gamma} (x))$ term introduces an ${\\cal O}(1)$ error. \n\n**W2. Why using Bilevel in LLM PEFT and what is its benefit over standard PEFT?**\n\nWe thank the reviewer for this insightful question and the opportunity to clarify the motivation and the benefit behind our bilevel optimization framework for parameter-efficient fine-tuning (PEFT), introduced in Eq. (3):\n\n- Upper Level: DPO objective, optimizing backbone parameters $x$;\n- Lower Level: SFT objective, optimizing a lightweight linear head $y$.\n\nOur design is motivated by both theoretical considerations and practical needs in LLM deployment, as briefly discussed in Section 4.1 and Appendix C.3. Due to space constraints, we did not expand on these points in the main text, but we re-clarify them here:\n\n(1) It operates in a post-SFT setting, where DPO is fine-tuned from a pretrained model and SFT is applied to downstream tasks. This setup reflects the standard practice in LLM deployment, where models are adapted rather than trained from scratch, and human preferences are often shared across downstream tasks. \n\n(2) The bilevel structure is to mitigate catastrophic forgetting commonly observed in traditional PEFT pipelines. Sequential fine-tuning, where first applying SFT and then DPO—DPO updates, can inadvertently overwrite task-specific knowledge acquired during SFT [24]. Our bilevel formulation mitigates this by optimizing the DPO objective (UL) while conditioning on a near-optimal SFT solution (LL). This hierarchical structure helps preserve downstream task performance by maintaining task-specific adaptations in the head, while guiding backbone updates toward better preference alignment.\n\n(3) In real-world applications (e.g., industry use cases), it is common to fine-tune only a lightweight head for specific tasks while keeping the backbone fixed or lightly tuned [Pfeiffer et al., 2020] [Zaken et al., 2021]. Our method aligns with this PEFT practice by allowing the head to specialize for SFT tasks, while learning the preference backbone with DPO for generalization and alignment.\n\nWe appreciate the reviewer’s suggestion and will revise the manuscript to explicitly highlight these three motivations for using the bilevel framework in PEFT.\n\nReference\n>- Pfeiffer, Jonas, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. \"Adapterfusion: Non-destructive task composition for transfer learning.\" arXiv preprint arXiv:2005.00247 (2020).\n>- Zaken, Elad Ben, Shauli Ravfogel, and Yoav Goldberg. \"Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models.\" arXiv preprint arXiv:2106.10199 (2021).\n\n**W3. The parameter setting of $\\gamma={\\cal O}(\\delta^{-\\frac{2-\\alpha}{\\alpha}})$ in Line 810. If $\\delta = 0$ such indicates $\\gamma = \\infty$.**\n\nWe thank the reviewer for the detailed review and insightful comment. In practice, we do not need to take $\\delta = 0$, as we only aim to achieve a target accuracy $\\epsilon > 0$. Specifically, to guarantee $\\epsilon$-stationarity, we only need to choose $\\delta^{\\frac{2(\\alpha - 1)}{\\alpha}} = \\epsilon$, i.e. select $\\delta = \\epsilon^{\\frac{\\alpha}{2(\\alpha - 1)}}$. This leads to $\\gamma = {\\cal O}(\\delta^{-\\frac{2 - \\alpha}{\\alpha}}) = {\\cal O}(\\epsilon^{-\\frac{2 - \\alpha}{2(\\alpha - 1)}})$.\n\nThis approach aligns with standard non-asymptotic analyses in optimization, where parameters are chosen to ensure convergence to an $\\epsilon$-stationary point for some small (but usually nonzero) $\\epsilon$. We acknowledge that our original presentation may have been unclear, and we will revise the text to explicitly reflect this dependency and avoid potential misunderstandings.\n\n**W4. (Minor) The reference [36] by Huang et al., is flawed, and should be removed.**\n\nWe thank the reviewer for pointing that out. We will remove it.\n\nWe sincerely thank the reviewer for acknowledging the strengths of our empirical results and for the thoughtful questions that allowed us to clarify key theoretical points. We hope our detailed responses help resolve the remaining concerns, and we would be grateful if the reviewer could take them into consideration when finalizing their evaluation and possibly consider a higher score."}, {"review_id": "18jeYmHY4D", "reviewer": "Reviewer_gkxV", "summary": "Due to the nested problem structure, most existing algorithms require either the Hessian vector calculation or the nested loop updates, which are computationally inefficient in large language model (LLM) fine-tuning. Building upon the fully first-order penalty-based approach, this paper proposes an efficient value function-free (PBGD-Free) algorithm that eliminates the loop of solving the lower-level problem and admits fully single-loop updates.", "questions": "1. In Table 1, what do $d_x$ and $d_y$ represent?\n\n2. Has Definition 1 been previously used in the literature? If so, relevant citations should be provided.\n\n3. Observation 2 should explicitly state the smoothness conditions imposed on $f$.\n\n4. In Lemma 3, the notation $x^*$ always denotes the optimal solution, which may cause ambiguity. A distinct notation should be introduced. Moreover, Additionally, the range $\\alpha\\in (1,1.5]$ appears restrictive—does this hold for all functions, or could $\\alpha = 2$ be feasible?\n\n\n5. The algorithm should be reformulated as a single-loop structure, eliminating the dependence on $K$.\n\n6. In line 279, what is $l_F^{-1}$?\n\n\n7. In Equation (17), can $\\delta$ be made arbitrarily small? If not, the algorithm’s output accuracy would remain fixed regardless of $T$, which is undesirable.\n\n\nIf the author can provide sufficient reasons or evidence to prove the effectiveness of the proposed algorithm and the adopted assumptions, I'm willing to increase my score.", "limitations": "See **Weaknesses** and **Questions**.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**: 1. This paper proposes PBGD-Free, a computationally efficient fully-single-loop, value-function-free, first-order algorithm.\n\n2. This paper introduces a Holder-alike condition to describe the flatness of $f$, which relaxes the standard $l_{f,0}$-Lipschitz continuity assumption when $l_{f,0}$ is small.\n\n3. This paper is well-written.\n\n4. The figures in this paper look very good, for example, Figure 2.\n\n\n**Weaknesses**: 1. Assumption 2 imposes a Lipschitz condition on $\\nabla^2 f$, which appears overly restrictive. Standard requirements in the literature typically do not necessitate such an assumption.\n\n2. Furthermore, the $\\mu$-PL condition imposed on $c f(x,y) + g(x,y)$ in Assumption 2 seems excessively strong, as the PL condition for the sum of functions is rarely encountered in prior work. Additionally, the dynamic nature of $c$ further complicates the satisfaction of this condition. While the authors argue that the PL condition is weaker than strong convexity, they should provide more concrete examples to substantiate this claim, particularly when $g$ lacks strong convexity.\n\n3. The format of references is not consistent.", "was_revised": true, "final_justification": "The author's response addressed all of my concerns, and I have no further questions.", "rebuttal": "We thank the reviewer for recognizing our contribution and presentation. Our response to your comments follows.\n\n**W1-2. Assumption on: Lipschitz condition on hessians of $f$ and $g$; PL condition (Assumption 2) for the sum of functions $cf+g$ for small $c$. How PL is weaker than SC. examples?** \n\nWe thank the reviewer for raising these important points. We explained the feasibility of the assumptions in Line 147-150. All asumptions in Assumption 2 are traditional in Bilevel literature  [11, 15, 19, 28, 33, 38, 45, 74].\n\nThe Lipschitz condition on Hessians of $f$ and $g$ is standard in literature [45, 11, 19] and used to establish that the smooth constant $l_{F,1}$ of $F_\\gamma$ is ${\\cal O}(1)$ independent from $\\gamma$. This condition enables us to choose step sizes and to prove convergence rates. Even if this assumption is relaxed, convergence still holds under appropriately chosen step sizes $\\eta = {\\cal O}(1/\\gamma)$.\n\nPL condition is strictly weaker than assuming strong convexity. Specifically, all strongly convex functions satisfy the PL inequality, the converse is not true. For example, $f(x,y) = \\frac{1}{2} (x - 2 \\sin(y))^2$ is known to satisfy the PL condition but is not strongly convex, illustrating this gap.\n\nMoreover, assuming that $c f + g$ satisfies PL for sufficiently small $c$ is a commonly adopted assumption in bilevel literature [45, 74, 11]. This assumption is crucial for the existence of the nested gradient $\\nabla \\phi(x)$. This assumption is weaker than strongly convexity. For example, $g(y)=(y^2-1)^2$ is non-convex but PL, $f(y)=-y^2$ is non-convex, and $cf(y)+g(y)$ is 4-PL for all $c\\leq 0.25$.\n\n**W3. (Minor) Format of references is not consistent.** \n\nThank you for pointing this out. We will correct the reference formatting to ensure consistency in the revised version.\n\n**Q1. $d_x$ and $d_y$ in table 1**\n\n$d_x$ and $d_y$ are dimension for variable $x$ and $y$. It is firstly introduced in Line 19. We will make it more explicit in the revision.\n\n**Q2. Is Def 1 in previous literature?**\n\n**No, Definition 1 is novel and introduced in this work.** We designed it specifically to support our goal of developing the first efficient, first-order, single-loop bilevel algorithm with convergence guarantees. This definition captures a mild (see observation 1-3) and practically verifiable condition (see the calculation rule in (12)). It holds in many real-world settings, such as the PEFT scenario discussed in Section 3.1. \n\nImportantly, Definition 1 plays a key role in enabling our theoretical guarantees and serves as a foundation for what we believe is a promising first step toward solving bilevel problems efficiently in this regime. Additionally, the assumption on flatness condition with small $\\delta$ is mild for deep-learning problems, as we later elaborated in response to your Q7. \n\nWe appreciate the opportunity to clarify this contribution and will highlight it in the revised version.\n\n**Q3. (Minor) Observation 2 should explicitly state the smoothness conditions imposed on $f$**\nWe thank the reviewer for pointing this out. We will correct this to \"Under the $l_{f,1}$-smoothness condition of $f(x,\\cdot)$\" to make it more clear.\n\n**Q4. In Lemma 3, $x^*$ may cause ambiguity; $\\alpha \\in (1,1.5]$ may be strong.**\n\nWe appreciate the reviewer’s careful reading. Regarding the notation $x^*$, we intended it to denote a stationary point rather than a global optimum. While this usage is common in optimization literature, we acknowledge that it may cause ambiguity. We will revise the notation or clarify its meaning explicitly in the text to avoid confusion.\n\nRegarding the range $\\alpha \\in (1, 1.5]$, this condition arises from the flatness assumption on $f(x^*, \\cdot)$, and reflects a trade-off between the regularity of the function near the lower-level optimum and the convergence guarantees needed in bilevel optimization. Specifically, larger $\\alpha$ and smaller $\\delta$ imply flatter behavior around the optimum, which leads to a more restrictive conditions on $f$. \n\nNotably, the ideal case of $\\delta = 0$ (pure Hölder continuity) can only be achieved if $\\alpha \\leq 1$ or $\\nabla_y f(x, y_g^*(x)) =0$, as dictated by the textbook with Hölder continuity theory [Section 5.1; Evans, 1993]. To accommodate $\\alpha > 1$, we introduce a relaxed flatness condition in Definition 1 by allowing $\\delta > 0$. In this formulation, a larger $\\delta$ (e.g., $\\delta = 2$) reflects a tighter or more restrictive requirement on the behavior of $f$, while the range $\\alpha \\in (1, 1.5]$ remains moderate. In this way, although larger $\\alpha$ is feasible, it is not needed.\n\nReference\n>- Evans, Lawrence C. Partial differential equations. Vol. 19. American mathematical society, 1993.\n\n**Q5. The algorithm is single-loop, and the dependence of $K$ should be removed.**\n\nWe agree that in both our implementation and experiments, we use $K = 1$, and this is sufficient for the setting considered in this work. We have annotated this choice in Algorithm 1 to make it clear.\n\nWe chose to retain the inner-loop presentation because it facilitates the derivation of our theoretical results, particularly the negative result in Proposition 2. This structure allows for a direct comparison with classical bilevel approaches based on value function gradients, and helps highlight the contrast between our method and such approximations.\n\nWe will revise the presentation slightly to clarify that $K = 1$ is the default in our setting.\n\n**Q6. What is $l_{F}^{-1}$ in line 276?**\n\nThe notation $l_{F,1}$ is the smoothness constant of $F_\\gamma(x)$. It is not scalable with $\\gamma$, i.e. ${\\cal O}(1)$, according to [11]. We will clarify this. \n\n**Q7. Can $\\delta$ in eq.(17) be arbitrarily small?**\n\nWe appreciate the reviewer’s thoughtful question. In our convergence analysis, the parameter $\\delta$ captures the degree of flatness of the upper-level objective around the lower-level solution $y^*(x)$, and it directly influences how closely our algorithm converges to a true stationary point. Indeed, if $\\delta$ is not sufficiently small, convergence may only occur within a neighborhood of the stationary point.\n\nTo directly answer the reviewer’s question:\n> **$\\delta$ is generally very small (usually 0) in real-world deep learning problems.**\n\nWe support this claim both theoretically (in Observations 1–3) and empirically (PEFT example in Section 3.1, 4; more experiments in Appendix C). We elaborate further here.\n\nTo recap, the flatness parameter $\\delta$ defined in Definition 1 is a generalized upper bound from a standard Hölder-type inequality:\n\n$|f(x, y^*(x)) - f(x, y')| \\leq c \\|y' - y^{\\star}(x)\\|^\\alpha + \\delta(x), \\forall y.$\n\nWhen $\\delta = 0$, classical Hölder theory \\[Evans, 1993] implies that this inequality can only hold for $\\alpha \\leq 1$ or for $\\nabla_y f(x, y) = 0$. Thus, to accommodate higher-order decay $\\alpha > 1$, which is crucial for convergence analysis, we relax to allow $\\delta > 0$.\n\nTo further elaborate, consider the behavior of $\\delta(x)$ under different local structures of $f(x, y)$. Here, we consider local strucuture as $y_\\gamma$ is controled by $\\gamma$ to be close to $y_g$.\n\n* **Negative result on locally linear** case: If $f(x, y) \\approx f(x, y^{\\star}(x)) + \\langle \\nabla_y f(x, y^{\\star}(x)), y - y^{\\star}(x) \\rangle$, then $\\delta(x) := \\max_{y'} \\| \\nabla_y f(x, y^{\\star}(x))\\|\\|y' - y^{\\star}(x)\\| - c \\|y' - y^{\\star}(x)\\| ^\\alpha = \\max_{z\\geq 0}  \\| \\nabla_y f(x, y^{\\star}(x))\\| z- c z^\\alpha=  \\frac{\\alpha - 1}{\\alpha} \\alpha^{-\\frac{1}{\\alpha -1}} \\| \\nabla_y f(x, y^{\\star}(x))\\|$, choosing $c =\\| \\nabla_y f(x, y^{\\star}(x))\\|$.\n\nSo although $\\delta(x)$ can be artitrarily small when $\\alpha\\rightarrow 1$ even if $\\| \\nabla_y f(x, y^{\\star}(x))\\|$ is not small. When we plug this into eq.(17), the residual will be $\\| \\nabla_y f(x, y^{\\star}(x))\\|^{\\frac{2(\\alpha-1)}{\\alpha}} (\\frac{1}{\\alpha})^{\\frac{2}{\\alpha}}(1-\\frac{1}{\\alpha})^{2(1-\\frac{1}{\\alpha})}\\leq \\| \\nabla_y f(x, y^{\\star}(x))\\|^{\\frac{2(\\alpha-1)}{\\alpha}}$, which yields constant error. This is consistent with our negative Example 1, but is still tighter than the ${\\cal O}(\\| \\nabla_y f(x, y^{\\star}(x))\\|^2)$ bound for large $\\| \\nabla_y f(x, y^{\\star}(x))\\|$ under traditional Lipschitzness Assumption 1. \n\n* **Our focus on locally curved** case: However, for most of **deep learning problem**, using losses e.g. cross entropy, $\\ell_2$ loss, exponential, etc, are hardly linear: $f(x, y) \\approx f(x, y^{\\star}(x)) + {\\cal O}(\\|y - y^{\\star}(x)\\|^\\alpha), \\quad \\alpha > 1$, then $\\delta(x)= {\\cal O}(\\|y - y^{\\star}(x)\\|^\\alpha) - c\\|y - y^{\\star}(x)\\|^\\alpha$ **naturally becomes 0**.\n\n**Practical deep learning loss landscapes are highly non-linear and rarely locally linear in the parameter space.** Our PEFT example in Section 3.1, 4 and Observations 1–3 show that the flatness condition with **small $\\delta(x)$ is consistently satisfied** across a variety of tasks and models.\n\nWe would also like to emphasize the **fundamental difficulty** of the bilevel optimization setting considered in our paper. Earlier work either require double loop [40, 44, 45, 50, 73, 74, 100] or suffers higher computational complexity [15, 28, 33, 39, 42, 47, 78] (or both). Designing efficient **first-order** and **fully single-loop algorithm** with convergence guarantees is an open challenge. To the best of our knowledge, our work is the **first to address this challenge**, via proposing a mild and verifiable flatness condition.\nWe respectfully invite the reviewer to **reconsider** the contribution in light of this clarification. We will revise the manuscript to make this point clearer, highlighting both the theoretical intuition and the empirical justification in realistic deep learning contexts. Thank you again for highlighting this subtle and important issue."}, {"review_id": "ZEpJHDoFmW", "reviewer": "Reviewer_z3Zu", "summary": "This paper proposes PBGD-Free fully single-loop algorithm for bilevel optimization problems that avoids costly value-function computations.  PBGD-Free simplifies the process by removing the need to solve the inner optimization problem at every iteration. The authors show that while the method may fail to converge under standard Lipschitz assumptions, introducing a relaxed flatness condition—modeled by a H\\o lder-like inequality—ensures convergence to near-optimal solutions. They theoretically establish that under this flatness condition, PBGD-Free achieves favorable iteration complexity and low memory costs. Extensive experiments on parameter-efficient fine-tuning (PEFT) of LLMs demonstrate that PBGD-Free matches or outperforms state-of-the-art baselines in both accuracy and efficiency, validating the proposed theoretical framework.", "questions": "1. Line 38, it would be clearer if the authors explained what the smoothness constant refers to. Do they mean the Lipschitz constant of the gradient?\n2. Line 42 $F$ should be $\\tilde F$?", "limitations": "yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. This work proposes a relaxed assumption for Lipschitz continuity and provides a convergence analysis. \n2. The method empirically performs well.\n\nWeakness: \n1.  The paper is not very clearly written. DPO and its notations are not clearly introduced. For example, it would be clearer if the meanings of $x$ and $y$ in the model were explicitly specified. Additionally, it is unclear what $\\sigma$ represents in equation (13), and how $\\nabla f_{\\text{DPO}}$ is derived.\n2. The assumption on $\\delta$ in the flatness condition is strong. It requires $\\delta$ to be smaller than $\\epsilon$ to allow for a smaller choice of $\\lambda$. More importantly, Theorem 3 requires $\\delta(x_t)$ to be summable over $t$. If $T$ goes to infinity, then $\\delta(x_T)$ must tend to zero.\n4.  The complexity analysis still reveals that the proposed method may not converge. In the main result, Theorem 3, the proposed method includes an extra term in the complexity bound that depends on $\\delta$. Therefore, although the experiments show promising empirical results, the method lacks theoretical convergence guarantees, which makes it less satisfactory.", "was_revised": true, "final_justification": "My key concern about the delta is addressed.", "rebuttal": "We thank the reviewer for the thoughtful evaluation and for recognizing our contributions, including the relaxed assumption and strong empirical results. Some concerns appear to stem from misinterpretations, and we appreciate the opportunity to clarify these points. Our responses follow below.\n\n**W1. DPO notation not clearly introduced: meaning of x,y in (3); what $\\sigma$ is in eq.(13); how $\\nabla f_{DPO}$ is derived**\n\nThe decomposition of LLM model parameter $(x, y)$ in Eq.(3) is introduced in Section 3.1 and further contextualized in Section 4.1. Specifically, $x$ denotes the parameters of the pretrained LLM backbone, while $y$ corresponds to a lightweight, fine-tunable head (e.g., a linear layer). This type of decomposition is standard in LLM literature [Pfeiffer et al., 2020] [Zaken et al., 2021]. While it is discussed in the text, we agree that presenting it more explicitly earlier when introducing Eq.(3) would aid readability. We will revise the manuscript accordingly.\n\nIn Eq.(13), $\\sigma(\\cdot)$ refers to the sigmoid function, commonly used in DPO-based losses [66]. The gradient $\\nabla f_{\\text{DPO}}$ is derived in a standard manner by differentiating the DPO loss with respect to the model parameters $(x, y)$ according to [66], leveraging the softmax-based parameterization \n$$\n\\pi_{x,y}(r | z) := \\text{softmax}(\\text{model}_{x,y}(z))_r.\n$$\n\nWe follow the same conventions and setup as in the original DPO formulation in [66].\n\nWe appreciate the reviewer’s suggestions and will revise the manuscript to clarify these notations earlier in the paper to improve readability.\n\nReference\n>- Pfeiffer, Jonas, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. \"Adapterfusion: Non-destructive task composition for transfer learning.\" arXiv preprint arXiv:2005.00247 (2020).\n>- Zaken, Elad Ben, Shauli Ravfogel, and Yoav Goldberg. \"Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models.\" arXiv preprint arXiv:2106.10199 (2021).\n\n\n**W2. The flatness condition is strong. $\\delta < \\epsilon$ required for small $\\lambda$. Theorem 3 requires $\\delta(x_t)$ to be summable over $t$.**\n\nWe thank the reviewer for raising this important point. Since we did not mention “small $\\lambda$” in our paper as suggested by the reviewer, we assume the reviewer is referring to the requirement for small $\\delta$ in our convergence analysis. \n\nIndeed, if $\\delta$ is not sufficiently small, convergence may only occur within a neighborhood of the stationary point. However,\n\n> **Flatness with small $\\delta$ is NOT strong. Usually $\\delta \\approx 0$ in real-world deep learning problems (our focus).**\n\nWe support this claim both theoretically (in Observations 1–3) and empirically (PEFT example in Section 3.1, 4; additional experiments in Appendix C). We elaborate further here.\n\nTo recap, the flatness parameter $\\delta$ defined in Definition 1 is a generalized upper bound from a standard Hölder-type inequality:\n\n$|f(x, y^*(x)) - f(x, y')| \\leq c \\|y' - y^{\\star}(x)\\|^\\alpha + \\delta(x), \\forall y.$\n\nWhen $\\delta = 0$, classical Hölder theory \\[Evans, 1993] implies that this inequality can only hold for $\\alpha \\leq 1$ or for $\\nabla_y f(x, y) = 0$. Thus, to accommodate higher-order decay $\\alpha > 1$, which is crucial for convergence analysis, we relax to allow $\\delta > 0$.\n\nTo further elaborate, consider the behavior of $\\delta(x)$ under different local structures of $f(x, y)$. Here, we consider local strucuture as $y_\\gamma$ is controled by $\\gamma$ to be close to $y_g$.\n\n* **Negative result on locally linear** case: If $f(x, y) \\approx f(x, y^{\\star}(x)) + \\langle \\nabla_y f(x, y^{\\star}(x)), y - y^{\\star}(x) \\rangle$, then $\\delta(x) := \\max_{y'} \\| \\nabla_y f(x, y^{\\star}(x))\\|\\|y' - y^{\\star}(x)\\| - c \\|y' - y^{\\star}(x)\\| ^\\alpha = \\max_{z\\geq 0}  \\| \\nabla_y f(x, y^{\\star}(x))\\| z- c z^\\alpha=  \\frac{\\alpha - 1}{\\alpha} \\alpha^{-\\frac{1}{\\alpha -1}} \\| \\nabla_y f(x, y^{\\star}(x))\\|$, choosing $c =\\| \\nabla_y f(x, y^{\\star}(x))\\|$.\nSo although $\\delta(x)$ can be artitrarily small when $\\alpha\\rightarrow 1$ even if $\\| \\nabla_y f(x, y^{\\star}(x))\\|$ is not small. When we plug this into eq.(17), the residual will be $\\| \\nabla_y f(x, y^{\\star}(x))\\|^{\\frac{2(\\alpha-1)}{\\alpha}} (\\frac{1}{\\alpha})^{\\frac{2}{\\alpha}}(1-\\frac{1}{\\alpha})^{2(1-\\frac{1}{\\alpha})}\\leq \\| \\nabla_y f(x, y^{\\star}(x))\\|^{\\frac{2(\\alpha-1)}{\\alpha}}$, which yields constant error. This is consistent with our negative Example 1, but is still tighter than the ${\\cal O}(\\| \\nabla_y f(x, y^{\\star}(x))\\|^2)$ bound for large $\\| \\nabla_y f(x, y^{\\star}(x))\\|$ under traditional Lipschitzness Assumption 1. \n\n* **Our focus on locally curved** case: However, for most of **deep learning problem**, using losses e.g. cross entropy, $\\ell_2$ loss, exponential, etc, are hardly linear: $f(x, y) \\approx f(x, y^{\\star}(x)) + {\\cal O}(\\|y - y^{\\star}(x)\\|^\\alpha), \\quad \\alpha > 1$, then $\\delta(x)= {\\cal O}(\\|y - y^{\\star}(x)\\|^\\alpha) - c\\|y - y^{\\star}(x)\\|^\\alpha$ **naturally becomes 0**.\n\n**Practical deep learning loss landscapes are highly non-linear and rarely locally linear in the parameter space.** Our PEFT example in Section 3.1, 4 and Observations 1–3 show that the flatness condition with **small $\\delta(x)$ is consistently satisfied** across a variety of tasks and models.\n\n\nRegarding Theorem 3, it might be a **misunderstanding**. In fact, we **DO NOT** require $\\delta(x_t)$ to be summable. Rather, we only require the **average** $\\frac{1}{T} \\sum_{t=0}^{T-1} \\delta(x_t)$ to be small, which does not necessarily imply $\\delta(x_T)\\rightarrow 0$ when $T$ goes to infinity. For example, consider a sequence where $\\delta(x_t) = 1$ when $t = 2^n$ for integer $n$, and $\\delta(x_t) = 1/t$ otherwise. This sequence is **not summable**, and $\\delta(x_T)$ **does not** converge to zero. However, the average remains small because the majority of $\\delta(x_t)$ values are small. This is a rather mild condition and is aligned with practical use. \n\n\nWe would also like to emphasize the **fundamental difficulty** of the bilevel optimization setting considered in our paper. Earlier work either require double loop [40, 44, 45, 50, 73, 74, 100] or suffers higher computational complexity [15, 28, 33, 39, 42, 47, 78] (or both). Designing efficient **first-order** and **fully single-loop algorithm** with convergence guarantees is an open challenge. To the best of our knowledge, our work is the **first to address this challenge**, via proposing a mild and verifiable flatness condition.\n\n\nWe respectfully invite the reviewer to **reconsider** the contribution in light of this clarification. We will revise the manuscript to make this point clearer, highlighting both the theoretical intuition and the empirical justification in realistic deep learning contexts. Thank you again for highlighting this subtle and important issue.\n\n\n**W3. The complexity analysis shows the algorithm may not converge.**\n\nThis might be a **misunderstanding**. The algorithm can converge depending on the flatness of the objective function. Please refer to the answer for **W2**.\n\n**Q1 (minor). Explain the smoothness constant in line 38.**\n\nWe appreciate the reviewer’s attention to detail. Yes, the “smoothness constant” refers to the Lipschitz constant of the gradient of the corresponding objective function. We will clarify this terminology in the revision.\n\n**Q2 (minor). Typo: $F$ should be $\\tilde{F}$**\n\nThank you for catching this typo. We confirm that it should be $\\tilde{F}$, and we will correct it in the revised version.\n\n\nWe hope these clarifications help resolve the concerns and offer a clearer view of our contributions. We would be grateful if the reviewer could take our responses into account when reassessing the paper and consider the possibility of raising the score."}]

Author rebuttal:

Meta-review: The authors define a new average flatness condition and, under this condition, provide an algorithm, with a convengence guarantee, for bilevel non-convex optimization. The reviewers found strength in the results; the condition was natural and the problem very important (e.g. useful for llm optimization). Technical details were discussed at length, but no major outstanding concerns remained. Some concerns about implementability of the algorithm were resolved, and the authors were convinging in their arguments of practicality of the algorithm. Considering that the proposed method has been motivated in a few independent ways -- theoretically and practically -- I think it will be a vaulable addition to the community.
Decision: Accept (poster)