REVIEW 4 major objections 3 minor 1 cited by
On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
T0 review · 4 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict New and likely correct result, but the proof has a locatable gap and the abstract overstates the assumptions. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section B.3, Lemma 5.3, Eqs. (19)-(20)] 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.
- [Abstract and Section 2, Assumption 2.1(i)] 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 4, Eq. (16); Section 2] 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.
- [Appendix A.2, Theorem 3.2 and Remark 5.1] 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.
minor comments (3)
- [Appendix A.1, proof of Lemma 3.1] 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 6, Figure 2] 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 6] There is a typo in the heading 'T oy Example'; it should read 'Toy Example'.
Circularity Check
No circularity: the discrete-time DBGD guarantee is proved from stated assumptions; self-citations are not load-bearing.
full rationale
The central claim is derived end-to-end: Lemma 5.1 uses smoothness and the subproblem's KKT conditions; Lemma 5.2 uses only Assumption 2.1(i); Lemma 5.3 combines them; Theorem 5.5 telescopes an explicit potential with explicit η and β, yielding the stated rates. Definition 3.1 is a first-order stationarity notion for the equivalent constrained problem and is not defined in terms of algorithm iterates, fitted constants, or the paper's own results. No parameter is fitted to data, and no prediction is a renamed input. Self-citations appear only in related-work comparisons or as alternative-instance remarks, not as load-bearing justification. The bounded-gradient assumption and the division by ∥∇g(x_k)∥² in (16) are important correctness/scope concerns but are not circularity: they make the result conditional, while the derivation does not presuppose the conclusion.
Assumptions & free parameters
free parameters (3)
- Step size eta =
1 / (L K^{1/(3+p)})
- Barrier hyperparameter beta =
K^{-p/(3+p)}
- Trade-off exponent p =
arbitrary p >= 0
assumptions (5)
- domain assumption Global bounded gradient of f: ||nabla f(x)|| <= G_f for all x (Assumption 2.1(i)).
- domain assumption f is L_f-smooth and g is L_g-smooth on R^n (Assumption 2.1(ii) and (iii)).
- domain assumption f* and g* are finite (Assumption 2.1 preamble).
- ad hoc to paper The iterates never hit ||nabla g(x_k)|| = 0; otherwise formula (16) divides by zero.
- domain assumption Local error bound Assumption 3.1, used only for Theorem 3.2.
Cite this review
Pith. "Pith review of On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization." pith.science (2026). https://pith.science/paper/YCP45VHD
@misc{pith2026250723155,
author = {Pith},
title = {Pith review of: On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/YCP45VHD}},
note = {Machine review of arXiv:2507.23155}
}
abstract
In this paper, we study the problem of solving a simple bilevel optimization problem, where the upper-level objective is minimized over the solution set of the lower-level problem. We focus on the general setting in which both the upper- and lower-level objectives are smooth but potentially nonconvex. Due to the absence of additional structural assumptions for the lower-level objective-such as convexity or the Polyak-{\L}ojasiewicz (PL) condition-guaranteeing global optimality is generally intractable. Instead, we introduce a suitable notion of stationarity for this class of problems and aim to design a first-order algorithm that finds such stationary points in polynomial time. Intuitively, stationarity in this setting means the upper-level objective cannot be substantially improved locally without causing a larger deterioration in the lower-level objective. To this end, we show that a simple and implementable variant of the dynamic barrier gradient descent (DBGD) framework can effectively solve the considered nonconvex simple bilevel problems up to stationarity. Specifically, to reach an $(\epsilon_f, \epsilon_g)$-stationary point-where $\epsilon_f$ and $\epsilon_g$ denote the target stationarity accuracies for the upper- and lower-level objectives, respectively-the considered method achieves a complexity of $\mathcal{O}\left(\max\left(\epsilon_f^{-\frac{3+p}{1+p}}, \epsilon_g^{-\frac{3+p}{2}}\right)\right)$, where $p \geq 0$ is an arbitrary constant balancing the terms. To the best of our knowledge, this is the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in general nonconvex simple bilevel problems.
Figures
Forward citations
Cited by 1 Pith paper
-
Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization
SDBPG and its penalty/variance-reduced variants achieve the first explicit (ε_f, ε_g)-stationarity rates for stochastic nonconvex simple bilevel problems by regularizing unbounded dual multipliers.
Reference graph
Works this paper leans on
-
[1]
Computing a non- negative matrix factorization–provably
[AGKM12] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Anku r Moitra. “Computing a non- negative matrix factorization–provably”. In: Proceedings of the forty-fourth annual ACM symposium on Theory of computing . 2012, pp. 145–162 (page 11). [BGMST16] Ernesto G Birgin, JL Gardenghi, Jos´ e Mario Mart´ınez, Sandra A Santos, and Ph L Toint. “Evaluation comple...
arXiv 2016
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.