{"id":"10ef31fd-ad3f-4e5c-b698-0df49ffb2f36","arxiv_id":"2507.20400","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A new first-order single-loop bilevel algorithm called PBGD-Free is claimed to converge in O(epsilon^-1) under a flatness condition, but its key proof step leans on the Lipschitz assumption it claims to avoid.","lead":"This paper proposes a single-loop, first-order algorithm for bilevel optimization that skips the costly lower-level solve, and claims convergence under a new flatness condition. The practical promise is cheaper large-model fine-tuning, but the central convergence proof has a gap that the included counterexamples do not repair.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's proof substitutes the Lipschitz-based O(gamma^-1) distance bound for the flatness-based Lemma 1 bound; with delta not forced small, the Lipschitz regularity of delta(x) (and of the value-function smoothness used in Theorem 3) is unsupported.","rationale":"The reader's weakest-assumption identification is the same core gap: Lemma 2's proof borrows the Lipschitz-based O(gamma^{-1}) distance estimate from Proposition 1, while the flatness condition only supplies Lemma 1's weaker bound, whose delta-dependent term ruins the claimed O(c gamma^{-(alpha-1)}) Lipschitz constant. I agree with the reader that the central theoretical contribution is not established as written. I would add one precision: for alpha in (1,1.5], the pure flatness term gamma^{-1/(2-alpha)} is in fact smaller than gamma^{-1}, so the real obstruction is the delta^{1/2} gamma^{-1/2} term. A secondary but related gap is that the proof of Theorem 3 itself relies on the smoothness of v_h with l_{vh,1}=l_{h,1}(1+L_y^gamma), i.e., on a Lipschitz selection of y_gamma^*(x), which is never proved under flatness and is only arguably supplied by the flawed Lemma 2. I credit the paper's useful negative result in Proposition 2, the fixed-x analysis in Lemma 1, and the extensive LLM experiments; these are real contributions but do not repair the proof gap in the main convergence theorem. Since the reader's verdict was already REJECT and my concern supports that verdict, I recommend no change to the verdict.","tokens_in":35025,"tokens_out":16380,"duration_ms":171204,"concrete_test":"Re-derive Appendix B.4, replacing every use of Proposition 1's O(gamma^{-1}) bound on ||y_g^*(x)-y_gamma^*(x)|| with Lemma 1's bound O(gamma^{-1/(2-alpha)} + delta^{1/2} gamma^{-1/2}). In particular, recompute inequality (51)(b) and the E_i bounds in (47)-(50). If the resulting Lipschitz constant of delta(x) contains c delta^{(alpha-1)/2} gamma^{-(alpha-1)/2} (i.e., is not O(c gamma^{-(alpha-1)}) when delta=Theta(1)), then Lemma 2 fails as stated. Then check whether Eq. (62)'s l_{vh,1}=l_{h,1}(1+L_y^gamma) bound can be established without that Lipschitz constant; if not, Theorem 3's descent argument is unsupported. An equivalent numerical companion is to compute sup_{x,h}|delta(x+h)-delta(x)|/|h| for Example 2 with gamma=15 and compare it with O(c gamma^{-(alpha-1)}).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 3 is the O(epsilon^{-1}) single-loop convergence under (delta,alpha)-flatness. Lemma 1 gives the fixed-x control ||y_g^*(x)-y_gamma^*(x)|| = O(gamma^{-1/(2-alpha)} + delta^{1/2} gamma^{-1/2}). This is compatible with the average-delta assumption in Theorem 3. The load-bearing problem is the next regularity step. Lemma 2 claims delta(x) is O(c gamma^{-(alpha-1)})-Lipschitz in x. Its proof in Appendix B.4 bounds the derivative of f(x,y_g^*)-f(x,y_gamma^*) and the alpha-power of ||y_g^*-y_gamma^*|| by invoking Proposition 1's O(gamma^{-1}) distance estimate. Proposition 1 is proved under Assumption 1 (lf,0-Lipschitz upper-level), which is exactly the assumption the flatness condition is meant to replace. Under flatness alone, Lemma 1's distance bound contains delta^{1/2} gamma^{-1/2}; when delta=Theta(1), this is O(gamma^{-1/2}) or larger for alpha close to 1, not O(gamma^{-1}). The pure gamma^{-1/(2-alpha)} term is actually smaller than gamma^{-1}, so the obstruction is specifically the delta-dependent term. Replacing Proposition 1 with Lemma 1 in (51) and in the E_i bounds (47)-(50) yields a Lipschitz constant of order c delta^{(alpha-1)/2} gamma^{-(alpha-1)/2}, not c gamma^{-(alpha-1)}. Moreover, the proof of Theorem 3 in Appendix B.6 needs v_h(x)=min_y(gamma^{-1}f+g) to be smooth with l_{vh,1}=l_{h,1}(1+L_y^gamma), requiring a Lipschitz selection x -> y_gamma^*(x); the manuscript gives no proof of this under flatness, and Lemma 2 is the only place such regularity is argued. The theorem's proof therefore does not close on the stated assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PBGD-Free, a fully single-loop first-order penalty-based method for nonconvex bilevel optimization that updates the upper-level variable x using only ∇_x f(x,y), thereby avoiding inner-loop estimation of the lower-level solution and Hessian computation. The authors first show, via Example 1 and Proposition 2, that under the standard Lipschitz assumption on f(x,·) the method converges only to a Θ(l_{f,0}^2) neighborhood of a stationary point. They then introduce a (δ,α)-flatness condition on f(x,·), argue that it is satisfied by a representation-learning LLM PEFT problem, and claim in Theorem 3 that under this condition Algorithm 1 with K=1 reaches an ε-stationary point of the penalized problem in O(ε^{-1}) iterations. The appendix contains proofs of Lemmas 1-3, a stationary-point equivalence result, and experiments on LLM PEFT, fair representation learning, and BiDoRA fine-tuning.","tokens_in":35535,"tokens_out":8826,"duration_ms":85240,"significance":"If the flatness-based analysis were correct, the paper would make a useful contribution: it identifies a concrete computational bottleneck in penalty-based bilevel methods, gives a clean negative result showing that PBGD-Free fails under Lipschitzness, and proposes a landscape condition tailored to representation-learning PEFT. Lemma 1's improved γ-exponent over Proposition 1 is a genuine insight, and the empirical flatness measurements in Figure 5 connect the theory to the application. However, the central convergence result is not established as written: the proof of Lemma 2 silently invokes the Lipschitz-based bound of Proposition 1, which is exactly the assumption the flatness program was meant to replace, and Theorem 3's parameter choice is inconsistent with the proof in Appendix B.6. Because the advertised O(ε^{-1}) single-loop guarantee rests on these two load-bearing points, the positive contribution is currently unsupported.","major_comments":[{"comment":"Lemma 2's proof is not self-consistent with the flatness setting. The bound ∥E_i∥=O(γ^{-1}) at (48) and the distance estimate ∥y_g^*(x)-y_γ^*(x)∥=O(γ^{-1}) at (51)(b) both invoke Proposition 1, which is proved under Assumption 1's Lipschitz continuity. Under the flatness hypothesis alone, Lemma 1 gives only O(γ^{-1/(2-α)}+δ^{1/2}γ^{-1/2}); for δ=Θ(1), or more generally δ>γ^{-1}, the δ^{1/2}γ^{-1/2} term is asymptotically larger than γ^{-1}. Consequently the claimed O(cγ^{-(α-1)}) Lipschitz constant for δ(x) is not established, and the later use of a Lipschitz selection y_γ^*(x) and of the smoothness of v_h in the proof of Theorem 3 is unsupported.","section":"Appendix B.4, Eqs. (48) and (51)"},{"comment":"The stated choice of γ in Theorem 3 does not match the proof. The theorem says γ=O(ε^{-(2-α)/2}), while the proof sets γ=O(δ^{-(2-α)/α}) before Eq. (64) to obtain the final O(T^{-1}+δ^{2(α-1)/α}) bound. With the stated γ, the δγ term in (60) becomes δ ε^{-(2-α)/2}, which is not O(δ^{2(α-1)/α}). Thus the theorem as stated is not what is proved; the authors need to state the correct relation between ε, δ, and γ, or revise the theorem.","section":"Theorem 3 and Appendix B.6, Eq. (64)"},{"comment":"The claimed O(ε^{-1}) complexity to a necessary stationary condition of the original problem requires more than the displayed bound. Theorem 3 only bounds the average squared gradient of the penalized objective Fγ by O(T^{-1}+δ^{2(α-1)/α}). To turn this into an ε-stationary guarantee one needs δ ≤ ε^{α/(2(α-1))}, and Lemma 3 separately requires δ≤O(ε^{α/2}) at the limit point. These smallness conditions on δ are not stated in Theorem 3, and the experimental validation in Figure 5 reports absolute values of δ (around 3×10^{-4}) rather than δ relative to a target accuracy ε. Without them, the result establishes convergence only to a δ-dependent neighborhood, not the advertised ε-stationary point of the original bilevel problem.","section":"Theorem 3 and Lemma 3"},{"comment":"The telescoping argument that closes the descent inequality relies on the smoothness constant l_{vh,1}=l_{h,1}(1+L_y^γ) of the lower-level value function v_h(x)=min_y h(x,y), which in turn requires a Lipschitz selection x↦y_γ^*(x) with constant independent of γ. The manuscript cites [11] for this fact, but [11] works under the Lipschitz assumption Assumption 1. Under flatness alone, Lemma 1's distance bound is not sufficient to produce such a selection, and Lemma 2, which could have supplied part of this regularity, is itself unproven as noted above. This is a structural gap in the proof of the main theorem.","section":"Appendix B.6, Eqs. (60)-(62)"}],"minor_comments":[{"comment":"Assumption 1 is stated as a one-sided Lipschitz condition at y_g^*(x), while Definition 2 in Appendix A defines global Lipschitz continuity; the relationship between the two should be clarified.","section":"Section 2.1, Assumption 1"},{"comment":"The definition of δ(x) depends on the chosen selections y_g^*(x) and y_γ^*(x); the manuscript should specify how these selections are made so that δ(x) is well-defined. Also, (45) defines δ'(x) without the max with 0, and the sentence 'δ(x) is a ReLU function' is too terse.","section":"Eq. (12) and Appendix B.4, Eq. (45)"},{"comment":"The reference list contains duplicated numbering, e.g., [27] and [69] appear twice; those entries should be cleaned up.","section":"References"},{"comment":"The claimed O(ε^{-1}) complexity should be qualified in the table and concluding remarks as convergence to an ε-stationary point of the penalized objective under an additional δ-smallness condition, since Theorem 3 as written only gives a δ-dependent neighborhood.","section":"Table 1 and Section 5"}],"recommendation":"reject","confidential_remarks":"The core issue is not a matter of presentation: the proof of the key regularity lemma, Lemma 2, uses Proposition 1, which is the Lipschitz-based result that the flatness condition was introduced to replace. This makes the main theorem, Theorem 3, unproven under the stated assumptions. The inconsistency between the γ choice in the theorem statement and the proof is also load-bearing. I do not see a local fix that preserves the paper's central claim without either adding a new smoothness or Lipschitz assumption on the value function or substantially weakening the advertised rate; hence rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nTwo things to know before you read it. First, this paper has a genuinely new idea: drop the value-function term from penalty-based bilevel optimization, yielding a fully single-loop, Hessian-free algorithm called PBGD-Free. It also introduces a (δ,α)-flatness condition on the upper-level objective that relaxes the standard Lipschitz assumption, and it documents a clean counterexample (Proposition 2) showing that under Lipschitz continuity the method provably fails unless the upper-level gradient is small. Second, the main theoretical claim — O(ε^{-1}) convergence under flatness — is not actually proven as written. The gap sits in Lemma 2, and it is load-bearing.\n\nWhat the paper does well: the counterexample in Proposition 2 is tight and instructive; the flatness definition is mild, well-motivated by the PEFT landscape, and Figure 5 gives a concrete instance where δ(x) is small along the trajectory even though the local Lipschitz constant is large. The experimental section is substantial — PEFT on Pythia-1B and Llama-3B, plus fair representation learning and BiDoRA — and PBGD-Free is consistently faster than F2SA and BOME while matching or beating their accuracy. That part is real and useful.\n\nThe soft spot, in proportion: Lemma 1 gives the fixed-x bound ||y_g^*(x)-y_γ^*(x)|| = O(γ^{-1/(2-α)} + δ^{1/2}γ^{-1/2}). Lemma 2, whose proof is in Appendix B.4, needs δ(x) to be Lipschitz in x, and the proof invokes Proposition 1's O(γ^{-1}) estimate. Proposition 1 is proved under Assumption 1, the Lipschitz condition. Under flatness alone, when δ does not vanish, Lemma 1's bound is O(γ^{-1/2}) or worse, so the Lipschitz continuity of δ(x) is not established. Theorem 3 also requires smoothness of v_h(x) with a constant involving the Lipschitz constant of the selection x ↦ y_γ^*(x); no proof of this under flatness is provided. This is a genuine hole in the proof architecture, not a typo. It may be repairable by adding an explicit Lipschitz assumption on δ(x) or on the selection, but that is not what the paper states.\n\nThe citation pattern looks fair, and the paper engages honestly with the prior penalty-based literature. My overall take: the algorithm and empirical findings deserve a serious referee, but the central theorem is not proven. As a referee I would reject as written and ask for a repaired proof or a corrected statement with the needed regularity assumptions. If that can be done, this becomes a solid contribution.\n\nRecommendation: send to peer review, not desk reject, but expect heavy revision.","headline":"Interesting algorithm and a genuinely new flatness condition, but the central theorem has a load-bearing proof gap: Lemma 2 silently replaces the flatness bound with the very Lipschitz-based bound the paper set out to avoid.","tokens_in":36055,"tokens_out":2696,"would_cite":true,"duration_ms":28677,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C26","90C46"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single-loop, Hessian-free bilevel algorithm reaches ε-stationarity in O(ε^{-1}) iterations when the upper objective is (δ,α)-flat with small δ.","keywords":["bilevel optimization","single-loop algorithm","penalty method","flatness condition","Polyak–Łojasiewicz condition","first-order optimization","parameter-efficient fine-tuning","value function"],"falsifier":"Take the paper's Example 2 (or a smoothed version of it) with γ = 15, compute δ(x) via (12) on a grid of x, and measure sup_{x≠x'} |δ(x)-δ(x')|/||x-x'||; if this exceeds O(c $γ^{{-(α-1)}}$) while δ stays small, then Lemma 2 fails and Theorem 3's bound cannot be expected—averaged gradient norms over PBGD-Free runs should plateau above O($δ^{{2(α-1)/α}}$).","tokens_in":34835,"feed_emoji":"⚡","tokens_out":11705,"duration_ms":105382,"temperature":0.7,"pith_summary":"The paper aims to show that the lower-level loop of penalty-based bilevel optimization can be dropped entirely—updating both variables once per iteration with first-order gradients only—once the upper-level objective is flat in the lower-level variable near the lower-level solution set. It proves that PBGD-Free, its single-loop algorithm, drives the averaged squared gradient norm of the penalized objective below O($T^{{-1}}$ + $δ^{{2(α-1)/α}}$) under a (δ,α)-flatness condition, reaching an ε-stationary neighborhood in O($ε^{{-1}}$) iterations when the flatness parameter δ is small. It also shows that under the standard Lipschitz assumption the same update provably stalls at a constant-radius neighborhood, so flatness is exactly the new condition that makes the single-loop scheme converge. The motivation is computational: in large-model fine-tuning, nested loops and Hessian computations are the main bottleneck.","feed_headline":"One-step bilevel update converges in O(1/ε) steps for flat losses","feed_subtitle":"Drop the inner value loop: first-order updates reach ε-stationarity in about 1/ε steps on flat upper losses.","key_machinery":"The load-bearing object is the (δ,α)-flatness of f(x,·) at y_g^*(x): |f(x,y_g^*(x))-f(x,y)| ≤ c||y_g^*(x)-y||^α + δ for all y, with α∈(1,1.5]. It replaces the l_{f,0}-Lipschitz bound by a subquadratic growth bound plus a small offset δ, and it does the argument's work by producing tighter estimates of how far the lower-level solution of the penalized problem sits from the true one: Lemma 1 gives ||y_g^*(x)-y_γ^*(x)|| = O($γ^{{-1/(2-α)}}$ + $δ^{{1/2}}$$γ^{{-1/2}}$) instead of the Lipschitz-based O(l_{f,0}$γ^{{-1}}$). The proof then combines these estimates with the PL-condition structure of the penalized lower objective and a Lyapunov descent argument in x that telescopes because δ(x) is claimed to be Lipschitz in x (Lemma 2); the result is the averaged gradient bound of Theorem 3.","core_discovery":"PBGD-Free updates the lower variable once (K=1) by gradient descent on the penalized lower objective $γ^{{-1}}$f+g and then updates x by ∇_x f(x_t, y^γ_{t+1})—dropping the \"value function\" term γ(∇_x g(x, y^γ)-∇_x g(x, y^g)) that standard PBGD computes by an inner loop. The paper's central claim (Theorem 3) is that if Assumption 2 holds and f(x_t,·) is (δ(x_t), α)-flat at the lower-level solution set for all iterates, with the same α∈(1,1.5] and average δ(x_t) ≤ δ, then choosing γ = O($ε^{{-(2-α)/2}}$) yields (1/T)Σ_{t=0}^{T-1} ||∇F_γ(x_t)||^2 ≤ O($T^{{-1}}$ + $δ^{{2(α-1)/α}}$). Thus the algorithm reaches an ε-stationary neighborhood of the penalized problem in O($ε^{{-1}}$) iterations with no Hessian and no inner loop. Lemma 1 sharpens the approximation gap to ||φ-F_γ|| = O($γ^{{-α/(2-α)}}$ + δ), and Lemma 3 says the penalized stationary points are approximately stationary for the original bilevel problem, so the authors read the theorem as a positive answer to whether skipping the value-function loop is justified when the upper landscape is flat.","pith_inferences":["If flatness is as prevalent in alignment landscapes as the paper's fine-tuning measurements suggest, the same single-loop scheme should transfer to other bilevel fine-tuning settings, e.g., diffusion-model reward tuning or data reweighting; the practical check is to monitor δ(x_t) along the trajectory.","The theory yields a concrete diagnostic: compute δ(x_t) from (12) during training; when it stays below the target ε, K=1 should be enough, and any accuracy gap to double-loop baselines would indicate the flatness assumption is failing rather than the loop count.","The hinge is Lemma 2: if δ(x) is not Lipschitz in realistic landscapes, the theorem collapses to the O(l_{f,0}^2) neighborhood of Proposition 2, so an empirical measurement of the variation of δ along trajectories would settle the practical reach of the result."],"forward_implications":["With small δ, PBGD-Free solves a nonconvex bilevel problem at O(ε^{-1}) iterations and O(1) per-iteration cost, using only first-order gradients: no Hessian-vector products and no nested lower-level loop.","The penalty parameter only needs to grow like ε^{-(2-α)/2}, so moderate values such as γ≈10–15 (the range used in the paper's experiments) are theoretically justified, and the tradeoff between the preference-alignment loss and the supervised fine-tuning loss observed when γ grows is a predicted side effect.","Lemma 3 transfers stationarity from the penalized problem to the original bilevel problem, so the x found by the single-loop method is an approximate stationary point of the original formulation, not merely of the penalty.","Under the standard Lipschitz assumption, Proposition 2 shows the same algorithm can only reach a $\\Theta(l_{f,0}^2)$ neighborhood; flatness is therefore what separates convergence from stalling in the paper's examples."],"supporting_citations":[{"why":"The penalty reformulation F_γ and the PBGD update template that PBGD-Free modifies; also the baseline V-PBGD.","marker":"[73]"},{"why":"The F2SA penalty method and its analysis of smoothness of F_γ and inner-loop requirements that this paper's single-loop version removes.","marker":"[44]"},{"why":"The improved hypergradient analysis showing F_γ is O(1)-smooth, which Theorem 3's constant step size uses.","marker":"[11]"},{"why":"The BOME first-order bilevel method that provides the stationary-condition formulation for PL lower-level problems and a comparison baseline.","marker":"[99]"},{"why":"The PL-condition machinery: quadratic growth, error bound, and linear convergence of gradient descent on PL functions, used throughout Lemmas 1–3 and Theorem 3.","marker":"[40]"},{"why":"The pseudo-inverse perturbation bound used in Lemma 2 to show the flatness constant δ(x) is Lipschitz in x.","marker":"[84]"},{"why":"The Hölder-continuous gradient condition used in Observation 1 to derive (δ,α)-flatness from smoothness.","marker":"[5]"}],"fun_headline_variants":["Single-loop bilevel method skips inner loop on flat losses","Flat losses let bilevel optimization run one step per iteration","No Hessian, no inner loop: PBGD-Free converges in O(1/ε)","Flat upper landscapes make single-loop bilevel convergence possible","Fast bilevel fine-tuning without value-function inner loop"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs the flatness constant δ(x) to change only proportionally to how far x moves along the trajectory; if δ(x) can jump sharply when x moves a little, the descent inequality that yields Theorem 3 does not close.","fun_headline_variants_meta":{"raw":{"variants":["Single-loop bilevel method skips inner loop on flat losses","Flat losses let bilevel optimization run one step per iteration","No Hessian, no inner loop: PBGD-Free converges in O(1/ε)","Flat upper landscapes make single-loop bilevel convergence possible","Fast bilevel fine-tuning without value-function inner loop"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1440,"prompt_tokens":1020,"completion_tokens":420,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":333}},"tokens_in":636,"tokens_out":420,"duration_ms":3887,"temperature":1.0,"reasoning_tokens":333,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:44:15.147885+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's Example 2 (or a smoothed version of it) with γ = 15, compute δ(x) via (12) on a grid of x, and measure sup_{x≠x'} |δ(x)-δ(x')|/||x-x'||; if this exceeds O(c $γ^{{-(α-1)}}$) while δ stays small, then Lemma 2 fails and Theorem 3's bound cannot be expected—averaged gradient norms over PBGD-Free runs should plateau above O($δ^{{2(α-1)/α}}$).","supporting_citations":[{"cited_title":"On penalty-based bilevel gradient descent method","cited_arxiv_id":null,"evidence_quote":"The penalty reformulation F_γ and the PBGD update template that PBGD-Free modifies; also the baseline V-PBGD."},{"cited_title":"On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation","cited_arxiv_id":null,"evidence_quote":"The F2SA penalty method and its analysis of smoothness of F_γ and inner-loop requirements that this paper's single-loop version removes."},{"cited_title":"Bome! bilevel optimization made easy: A simple first-order approach","cited_arxiv_id":null,"evidence_quote":"The BOME first-order bilevel method that provides the stationary-condition formulation for PL lower-level problems and a comparison baseline."},{"cited_title":"Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition","cited_arxiv_id":null,"evidence_quote":"The PL-condition machinery: quadratic growth, error bound, and linear convergence of gradient descent on PL functions, used throughout Lemmas 1–3 and Theorem 3."},{"cited_title":"Perturbation theory for pseudo-inverses","cited_arxiv_id":null,"evidence_quote":"The pseudo-inverse perturbation bound used in Lemma 2 to show the flatness constant δ(x) is Lipschitz in x."}],"review_version":2}