{"id":"5d2a45fc-f3ff-4aac-a899-df85631a9cba","arxiv_id":"2507.23155","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For smooth possibly nonconvex simple bilevel problems, dynamic barrier gradient descent reaches an approximate joint stationary point in O(max(epsilon_f^{-(3+p)/(1+p)}, epsilon_g^{-(3+p)/2})) iterations.","lead":"This paper proves a new worst-case speed guarantee for a simple algorithm that balances the upper-level goal of a bilevel problem against staying near the set that minimizes the lower-level goal. It is the first discrete-time guarantee of this kind for fully nonconvex problems, though the proof has gaps that need repair.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed 'general' nonconvex guarantee rests on the global bounded-gradient assumption on f (Assumption 2.1(i)); without it Lemma 5.2 collapses, so the abstract should state this caveat.","rationale":"I read the complete proof. The square-root step in Lemma 5.3 flagged by the prior reader is actually correct: adding 2Δg/(Lgη^2) to both sides of (19), defining S_k, and applying Lemma 5.4 does yield (21). I therefore do not rest the concern on that algebra. The real bottleneck is Assumption 2.1(i), which is used exactly once to bound λ_k and cannot be relaxed within the current potential argument. Because the abstract claims generality beyond previous results and does not mention bounded ∇f, this is a load-bearing scope issue. The theorem itself is a valid conditional result, so the verdict remains conditional rather than reject.","tokens_in":21522,"tokens_out":26635,"duration_ms":281367,"concrete_test":"Re-derive the proof of Lemma 5.3 with G_f replaced by G_K := max_{0≤k≤K} ∥∇f(x_k)∥ and check whether the potential bound in Theorem 5.5 remains O(1/K) with constants independent of K. If the bound acquires a G_K factor or otherwise fails to telescope, Assumption 2.1(i) is essential, and the abstract's 'general nonconvex' claim must be qualified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is that the advertised 'general nonconvex' claim is only proved under Assumption 2.1(i), the global bound ∥∇f(x)∥ ≤ G_f. That bound enters at Lemma 5.2, where it alone gives λ_k ≤ β + G_f/∥∇g(x_k)∥. Lemma 5.3 and Theorem 5.5 then use this to dominate the term λ_k∥∇g(x_k)∥^2 in (17) by β∥∇g(x_k)∥^2 + G_f∥∇g(x_k)∥, which is what makes the potential argument close. If f is only L-smooth with inf f > -∞ — the standard smooth nonconvex setting the abstract invokes — no such finite G_f exists in general (quadratics, f(x)=sin(x^2), many smooth losses), so Lemma 5.2 cannot even be stated. The theorem is correct as a conditional statement, but the abstract's 'general nonconvex simple bilevel problems' and the 'first complexity result' framing overstate the class of problems covered: the result requires a global gradient bound on the upper-level objective, not merely smoothness. A secondary formal gap is that (16) divides by ∥∇g(x_k)∥^2, with no assumption ruling out ∥∇g(x_k)∥ = 0, so the update itself is undefined at a lower-level stationary point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the simple bilevel problem min_x f(x) subject to x in argmin g(z), where both f and g are smooth and potentially nonconvex. It introduces a first-order stationarity notion, the (epsilon_f, epsilon_g)-stationary point of Definition 3.1, requiring the existence of lambda >= 0 such that ||nabla g(x)||^2 <= epsilon_g and ||nabla f(x) + lambda nabla g(x)||^2 <= epsilon_f. The authors analyze a discrete-time variant of dynamic barrier gradient descent (DBGD) with the choice phi(x) = beta ||nabla g(x)||^2, leading to the closed-form multiplier lambda_k in Eq. (16). Under Assumption 2.1, which includes a global bounded-gradient condition on f, they claim that the method reaches an (epsilon_f, epsilon_g)-stationary point in O(max(epsilon_f^{-(3+p)/(1+p)}, epsilon_g^{-(3+p)/2})) iterations, with p >= 0 a free trade-off parameter. The paper also relates its stationarity metric to scaled and unscaled KKT conditions and to a gradient-based reformulation, and reports numerical experiments on a toy problem and a matrix factorization problem.","tokens_in":21794,"tokens_out":14859,"duration_ms":158695,"significance":"If the proof issues identified below are fixed, the paper would provide a genuinely useful first discrete-time non-asymptotic joint stationarity guarantee for nonconvex simple bilevel optimization. The stationarity metric is sensible and is supported by a local characterization in Lemma 3.1 and by connections to existing KKT-type conditions. The analysis is parameter-free in the sense that no constants are fitted to data, and the claimed rates are explicit. The numerical experiments, while limited, illustrate the qualitative advantage of the barrier scheme over fixed-penalty baselines. The main reservations concern a load-bearing algebraic slip in the central convergence lemma and an overstatement of the problem class covered by the assumptions; both appear fixable without changing the overall approach.","major_comments":[{"comment":"The displayed inequality (19) does not follow from (17)-(18) and Lemma 5.2 with the constants as written. Substituting (18) into the bound obtained from Lemma 5.2 gives a square-root term of the form 2 G_f sqrt(beta) sqrt(Delta g_k/eta + (L_g/2) eta ||d_k||^2), not 2 sqrt(beta G_f) sqrt(Delta g_k/eta + (L_g/2) eta ||d_k||^2). Consequently, Eq. (20) should contain G_f sqrt(beta) sqrt(2 L_g eta) sqrt(S_k), and Lemma 5.4 then yields the term 2 beta G_f^2 L_g eta that appears in Eq. (21). As printed, the passage from (19) to (20) to (21) is internally inconsistent: with the printed sqrt(beta G_f), the square of the linear coefficient would be 2 beta G_f L_g eta, not 2 beta G_f^2 L_g eta. Because Lemma 5.3 and its consequence (21) are the engine of the potential-function argument in the proof of Theorem 5.5, this algebraic slip is load-bearing. The correction appears local, but the constants in Lemma 5.3, Eq. (20), Eq. (21), and Theorem 5.5 must be re-verified after the fix.","section":"Section B.3, Lemma 5.3, Eqs. (19)-(20)"},{"comment":"The abstract and the contribution statement in Section 1 describe the result as covering general nonconvex simple bilevel problems with smooth objectives, but the theorem is proved only under the additional global uniform bound ||nabla f(x)|| <= G_f (Assumption 2.1(i)). This assumption is not merely technical: Lemma 5.2 uses it to control lambda_k by beta + G_f / ||nabla g(x_k)||, and the potential argument in Lemma 5.3 and Theorem 5.5 then relies on that control. Many standard smooth nonconvex objectives, including quadratics and functions such as f(x) = sin(x^2), have unbounded gradients on R^n, so the proved statement covers a strictly narrower class than the abstract's 'general nonconvex simple bilevel problems'. The abstract and contributions should either state this assumption explicitly or temper the 'general' claim.","section":"Abstract and Section 2, Assumption 2.1(i)"},{"comment":"The algorithm is not well-defined when ||nabla g(x_k)|| = 0, because Eq. (16) divides by ||nabla g(x_k)||^2, and Lemma 5.2 also divides by ||nabla g(x_k)||. No assumption in Section 2 rules out an iterate lying exactly at a stationary point of the lower-level objective. Since Theorem 5.5 quantifies over the iterates generated by (15)-(16), the statement presupposes a non-vanishing lower-level gradient that is not part of the assumptions. Please add an explicit non-vanishing-gradient provision or a stopping rule that handles ||nabla g(x_k)|| = 0, and state how the guarantee is affected in that case.","section":"Section 4, Eq. (16); Section 2"},{"comment":"The proof of Theorem 3.2 contains an unjustified algebraic step. The inequality before the last gives 2 lambda L_H ||x_hat - x^*||^2; combined with Assumption 3.1 this yields at most 2 lambda L_H c^2 ||nabla g(x_hat)||^2 <= 2 lambda L_H c^2 epsilon_g, i.e., O(lambda epsilon_g), not the printed O(lambda ||nabla g(x_hat)|| epsilon_g). Thus the stated form of Theorem 3.2 is not established as written. Consequently, the claim in Remark 5.1 that the DBGD multiplier yields epsilon_p = O(epsilon_f + epsilon_g) in Theorem 3.2 is also not justified on the basis of the displayed proof; the corrected bound would involve lambda epsilon_g (or a sqrt(epsilon_g) factor once lambda is bounded by 1/||nabla g||). This is a secondary theorem rather than the main complexity result, but it should be repaired or restated.","section":"Appendix A.2, Theorem 3.2 and Remark 5.1"}],"minor_comments":[{"comment":"In the converse direction of the proof, the square roots in the stationarity definition are lost: from the lemma's conditions one obtains ||nabla g(x_hat)|| <= (1+delta) sqrt(epsilon_g) and ||nabla f(x_hat)|| <= (1+delta) sqrt(epsilon_f), not the displayed estimates with epsilon_g and epsilon_f without square roots. The argument remains valid after restoring the square roots.","section":"Appendix A.1, proof of Lemma 3.1"},{"comment":"The sub-captions in Figure 2 appear to be mislabeled: the main text describes panels (a)-(d) as reporting ||nabla g||^2, ||nabla_perp f||^2, g, and f, while the figure captions read 'f1' and 'f2'. These labels should be corrected.","section":"Section 6, Figure 2"},{"comment":"There is a typo in the heading 'T oy Example'; it should read 'Toy Example'.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The algebraic error in Lemma 5.3 appears to be a genuine but local slip: the corrected constant G_f sqrt(beta) preserves the structure of the argument and the final rates. The more substantive issue is that the advertised problem class is narrower than the abstract suggests because of Assumption 2.1(i). I do not see evidence of circularity or fitted constants; the main obstacle is tightening the written proof and calibrating the claims to the assumptions. If the authors fix the derivation and qualify the abstract, the paper could become acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper has a real new result and a proof that is probably right, but the write-up has a few concrete problems that need fixing before the claim is established.\n\nWhat's new: GLL21 analyzed DBGD only in continuous time, and Hsi+24 only gave a lower-level rate for BLOOP. This paper gives the first discrete-time non-asymptotic complexity for joint upper/lower stationarity in general nonconvex simple bilevel problems. The rate O(max(eps_f^{-(3+p)/(1+p)}, eps_g^{-(3+p)/2})) with a tunable p is plausible. The trick of using a potential function that lets the multiplier lambda_k be unbounded because it only enters as a coefficient of ||grad g||^2 is genuinely nice. The related-work discussion is careful and the claims about prior work check out.\n\nThe soft spots are specific and locatable. The biggest one is the assumption gap: the abstract says 'general nonconvex simple bilevel problems', but Assumption 2.1(i) requires a global bound on ||grad f||. That bound is load-bearing. Lemma 5.2 uses it to get lambda_k <= beta + G_f/||grad g(x_k)||, and without it the potential argument in Theorem 5.5 does not close. Quadratics and many other smooth nonconvex losses have unbounded gradients, so the advertised generality overstates the class covered.\n\nSecond, the proof of Lemma 5.3 as displayed does not match the argument in B.3. The printed inequality (19) appears to miss a term under the square root; if the intended inequality is ||d_k||^2 <= 2(...)/eta + 2 sqrt(beta G_f) sqrt(Delta g_k/eta + L_g/2 eta ||d_k||^2), then B.3 goes through and (20) follows cleanly. Given the 'implicit inequality' comment, I think it is a typesetting error rather than a fatal flaw, but as written a referee cannot verify the step.\n\nThird, the multiplier formula (16) divides by ||grad g(x_k)||^2. If the lower-level gradient vanishes at an iterate, the update is undefined. This is easy to patch by treating that case separately, but it is currently unflagged. There is also a minor notational slip in the converse half of Lemma 3.1, where sqrt(eps_g) and sqrt(eps_f) are needed but eps_g and eps_f appear.\n\nThe experiments are honest small-scale illustrations, nothing overclaimed.\n\nBottom line: the central result is new, the proof strategy is sound in outline, and the gaps are repairable. I'd send this to peer review with the expectation of major revisions. I wouldn't cite the current arXiv version in my own work until the proof is cleaned up.","headline":"New and likely correct result, but the proof has a locatable gap and the abstract overstates the assumptions.","tokens_in":22360,"tokens_out":7576,"would_cite":false,"duration_ms":70839,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a barrier gradient descent variant reaches joint stationarity in general nonconvex simple bilevel optimization, with a complexity of $O(\\max(\\epsilon_f^{-(3+p)/(1+p)}, \\epsilon_g^{-(3+p)/2}))$ iterations.","keywords":["simple bilevel optimization","nonconvex optimization","stationary point","dynamic barrier gradient descent","iteration complexity","first-order method","smooth nonconvex"],"falsifier":"Take the one-dimensional instance $f(x)=\\sin^2 x$ and $g(x)=x^2/2$, start at $x_0=1$, and run (15)-(16) with the theorem's choices $\\eta = (L_f+L_g)^{-1}K^{-1/(3+p)}$ and $\\beta = K^{-p/(3+p)}$. Record the best iterate's $\\|\\nabla g\\|^2$ and $\\|\\nabla f+\\lambda\\nabla g\\|^2$ over a grid of $K$; if either metric ever decays materially slower than the polynomial rates $O(K^{-2/(3+p)})$ and $O(K^{-(1+p)/(3+p)})$ predicted by (22)-(23), Theorem 5.5 would be contradicted.","tokens_in":21281,"feed_emoji":"🎯","tokens_out":16716,"duration_ms":180965,"temperature":0.7,"pith_summary":"Minimizing an upper-level objective over the set of minimizers of a lower-level objective is a simple bilevel problem, and when both functions are smooth and nonconvex, global optimality is out of reach. This paper targets a first-order stationarity notion instead: a point where the lower-level gradient is small and no local move improves the upper objective without degrading the lower one. The paper proves that a practical variant of dynamic barrier gradient descent reaches such an $(\\epsilon_f, \\epsilon_g)$-stationary point in $O(\\max(\\epsilon_f^{-(3+p)/(1+p)}, \\epsilon_g^{-(3+p)/2}))$ iterations for any $p \\ge 0$. A sympathetic reader should care because this is the first discrete-time complexity result giving joint stationarity guarantees for both levels in general nonconvex simple bilevel problems, whereas earlier guarantees were continuous-time or only for the lower level.","feed_headline":"First joint stationarity rate for nonconvex bilevel optimization","feed_subtitle":"At p=1 this is O(max(ε_f^{-2}, ε_g^{-2})) iterations with no convexity or PL condition needed.","key_machinery":"The carrying object is the potential function $G_k = \\tfrac12\\|d_k\\|^2 + \\tfrac{\\beta}{L_g \\eta}\\|\\nabla g(x_k)\\|^2$, where $d_k = \\nabla f(x_k) + \\lambda_k \\nabla g(x_k)$ is the actual update direction. The obstacle is that $\\lambda_k$ can diverge near a lower-level stationary point, since Lemma 5.2 only gives $\\lambda_k \\le \\beta + G_f/\\|\\nabla g(x_k)\\|$; the paper circumvents the need for a uniform bound on $\\lambda_k$ by combining descent inequalities for $f$ and $g$ so that $\\lambda_k$ appears only multiplied by $\\|\\nabla g(x_k)\\|^2$, a product that vanishes as the lower-level gradient shrinks. An implicit inequality for $\\|d_k\\|$ is resolved by the scalar bound $x \\le A + B\\sqrt{x} \\Rightarrow x \\le 2A + B^2$, and telescoping the potential over $K$ steps yields the two-rate guarantee of Theorem 5.5.","core_discovery":"The paper's central claim is that the update $x_{k+1} = x_k - \\eta(\\nabla f(x_k) + \\lambda_k \\nabla g(x_k))$, with $\\lambda_k$ chosen by the barrier rule in (16), finds an $(\\epsilon_f, \\epsilon_g)$-stationary point in the stated iteration bound. More precisely, for smooth possibly nonconvex $f$ and $g$ with globally bounded $\\nabla f$, using step size $\\eta = 1/((L_f+L_g)K^{1/(3+p)})$ and barrier parameter $\\beta = K^{-p/(3+p)}$, there is an iterate $k^*$ whose lower-level gradient and update direction satisfy the explicit bounds (22) and (23). The paper also establishes that its stationarity definition is equivalent to a local no-improvement property, and that it implies the unscaled approximate KKT conditions of the reformulated constrained problem, so the output of the method is a genuine first-order certificate rather than an artifact of the analysis.","pith_inferences":["An editor's extension: the global bound on $\\|\\nabla f\\|$ is the assumption most likely to limit applicability; a local or along-trajectory bounded-gradient condition might preserve the argument while covering quadratics and other standard smooth losses.","An editor's extension: the closed form of $\\lambda_k$ divides by $\\|\\nabla g(x_k)\\|^2$, so an implementation needs a rule for iterates that land exactly on a stationary point of $g$; the finite-time guarantee avoids this only because exact hits have probability zero in generic runs.","An editor's extension: Theorem 3.2 suggests a route to second-order certificates—any $(\\epsilon_f, \\epsilon_g)$-stationary point is an approximate KKT point of the gradient reformulation under a local error bound, so the same first-order method could be paired with Hessian checks to certify that stronger stationarity."],"forward_implications":["Balancing the two tolerances with $p=1$ gives an $O(\\max(\\epsilon_f^{-2}, \\epsilon_g^{-2}))$ iteration bound for $(\\epsilon_f, \\epsilon_g)$-stationarity.","The guarantee holds without convexity, without a Polyak–Łojasiewicz condition, and without constraint qualifications on the lower-level problem.","The output point is certified locally: neither $g$ can be decreased by more than the tolerance, nor $f$ decreased without increasing $g$.","This is the first discrete-time, non-asymptotic guarantee in this setting that covers the upper-level objective as well as the lower-level gradient norm."],"supporting_citations":[{"why":"introduces the DBGD framework and its continuous-time analysis, which this paper extends to discrete time","marker":"[GLL21]"},{"why":"prior stochastic method for nonconvex simple bilevel problems that gives only a lower-level rate, defining the gap this paper closes","marker":"[Hsi+24]"},{"why":"source of scaled approximate KKT conditions used to position the new stationarity metric","marker":"[CGT14]"},{"why":"source of unscaled approximate KKT conditions that the paper's stationarity notion implies","marker":"[BGMST16]"},{"why":"provides the $(\\epsilon_p,\\epsilon_d)$-KKT metric of the gradient reformulation to which Theorem 3.2 connects the new metric","marker":"[XLC23]"},{"why":"convex simple bilevel method whose lower-level linearization is a special case of the DBGD subproblem, motivating the nonconvex extension","marker":"[JAMH23]"}],"fun_headline_variants":["First joint stationarity guarantee for nonconvex bilevel problems","Barrier descent achieves joint stationarity in nonconvex bilevel","Polynomial-time joint stationarity for nonconvex bilevel objectives","New algorithm finds stationary points in nonconvex simple bilevel","Dynamic barrier gradient descent guarantees joint stationarity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof must have a finite number $G_f$ such that $\\|\\nabla f(x)\\| \\le G_f$ at every point of the space; if the upper-level gradient is unbounded, the bound on $\\lambda_k$ and the whole potential-function argument no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["First joint stationarity guarantee for nonconvex bilevel problems","Barrier descent achieves joint stationarity in nonconvex bilevel","Polynomial-time joint stationarity for nonconvex bilevel objectives","New algorithm finds stationary points in nonconvex simple bilevel","Dynamic barrier gradient descent guarantees joint stationarity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000509,"raw_usage":{"total_tokens":2547,"prompt_tokens":1083,"completion_tokens":1464,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":699,"completion_tokens_details":{"reasoning_tokens":1380}},"tokens_in":699,"tokens_out":1464,"duration_ms":11547,"temperature":1.0,"reasoning_tokens":1380,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:02:22.269266+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the one-dimensional instance $f(x)=\\sin^2 x$ and $g(x)=x^2/2$, start at $x_0=1$, and run (15)-(16) with the theorem's choices $\\eta = (L_f+L_g)^{-1}K^{-1/(3+p)}$ and $\\beta = K^{-p/(3+p)}$. Record the best iterate's $\\|\\nabla g\\|^2$ and $\\|\\nabla f+\\lambda\\nabla g\\|^2$ over a grid of $K$; if either metric ever decays materially slower than the polynomial rates $O(K^{-2/(3+p)})$ and $O(K^{-(1+p)/(3+p)})$ predicted by (22)-(23), Theorem 5.5 would be contradicted.","supporting_citations":[],"review_version":1}