REVIEW 2 major objections 5 minor 34 references
Sequential QCQP for Bilevel Optimization with Line Search
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A single-loop, tuning-free algorithm solves a relaxed bilevel problem with anytime feasibility and O(1/k) convergence.
desk verdict A genuinely new discrete-time single-loop bilevel algorithm with a clean O(1/k) proof, but the coercivity assumption behind the proof is violated by the paper's own synthetic example, so the theory outruns the experiments. 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 load-bearing object is the quadratically constrained quadratic program (QCQP) used for the search direction, together with the barrier-style line search. The QCQP has a closed-form solution: $\Delta$ z is the projection of -nabla f(z) onto a ball with center c = -nabla h(z)/(2w) and radius r = $\sqrt$(||nabla h(z)/(2w)||^2 - (alpha_b/w)(h(z)-$epsilon^{2}$)). This projection interpretation is what makes the method cheap and tuning-free. The line search combines a standard sufficient-decrease condition on f with the discrete control-barrier condition (8), and the proof of a uniform step-size lower bound t_min = min{ $\beta$ 2(1-alpha_ls)/L_f, $\beta$ gamma/alpha_b, $\beta$ 2w/L_h, t_max } is what converts local Lipschitz information into a convergence rate.
What would settle it
Take g(x,y)=1/2||Hy-x||^2 with an invertible square matrix H. Then h(x,y)=||H^T(Hy-x)||^2 vanishes on the affine set y=$H^{{-1}}$x, so the sublevel set {h <= $epsilon^{2}$} is unbounded and Assumption 4 is violated. Running Algorithm 1 on this example (or any problem with h flat along an unbounded manifold) would show whether the uniform step-size lower bound and O(1/k) rate still hold without coercivity; a single counterexample where ||$\Delta$ z_k|| fails to decay would settle the dependence on Assumption 4.
Extended reading notes
Core claim
The central claim is that the relaxed bilevel problem min f(x,y) subject to h(x,y)=||nabla_y g(x,y)||^2 <= $epsilon^{2}$ can be solved by a discrete-time safety-filtered gradient method. The search direction solves min_Delta z 1/2 ||$\Delta$ z + nabla f(z)||^2 subject to nabla h(z)^T $\Delta$ z + alpha_b(h(z)-$epsilon^{2}$) <= -w||$\Delta$ z||^2, with w>0. The quadratic tilting term makes the direction strictly inward-pointing when h(z)=$epsilon^{2}$, avoiding the stagnation that a direct QP discretization suffers near the boundary. A backtracking line search enforces both sufficient decrease of f and the discrete barrier condition h(z+t $\Delta$ z)-$epsilon^{2}$ <= (1-gamma)(h(z)-$epsilon^{2}$), which together give a uniformly positive step size t_min. The paper proves that for every K, h(z_K) <= $epsilon^{2}$ and (1/K) sum_{k=0}^{K-1} ||$\Delta$ z_k||^2 <= (f(z_0)-f*_epsilon)/(alpha_ls t_min K), so ||$\Delta$ z_k|| tends to 0 and every limit point satisfies the KKT conditions of the relaxed problem.
Load-bearing premise
The proof that iterates stay bounded and that uniform Lipschitz constants exist rests on Assumption 4: the squared lower-level gradient norm h(z) must grow to infinity as ||z|| grows; if h stays bounded on an unbounded set, that argument has no basis.
Editorial extensions
If this is right
- Anytime feasibility: after one feasible initialization, every subsequent iterate satisfies the lower-level stationarity condition within tolerance epsilon^2, so the method never requires an inner solver to restore feasibility.
- O(1/k) ergodic rate: the average of ||Delta z_k||^2 over the first K steps shrinks as (f(z_0)-f*_epsilon)/(alpha_ls t_min K); in particular the step norms tend to zero and any convergent subsequence reaches a KKT point of (2).
- Single-loop, closed-form per-iteration cost: each direction is a projection onto a ball, so the method scales to high-dimensional bilevel problems without Hessian inversion or hypergradient estimation.
- Every KKT point of the relaxed problem is an epsilon-KKT point of the stationary-seeking formulation, so solving (2) gives a controlled approximation to the original bilevel problem.
Reading between the lines
- The coercivity assumption on h is the hinge. For g(x,y)=1/2||Hy-x||^2 with invertible H, h vanishes on the affine manifold y=H^{-1}x, which is unbounded, so Assumption 4 fails; the paper's own synthetic benchmark is such a case. If coercivity is relaxed, the boundedness argument behind Lemma 1 and Theorem 2 may need a different mechanism.
- The same QCQP-with-tilting idea could be applied to any single-constraint smooth optimization problem where the constraint gradient can vanish at the boundary; the closed-form projection onto a ball gives a cheap safety filter for generic constrained gradient methods.
- A natural testable extension is to replace the fixed w with an adaptive schedule, since the experiments show larger w slows lower-level convergence; the theory only requires w>0 and a uniform t_min bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a single-loop algorithm for bilevel optimization by solving a relaxed single-level problem (2), in which the lower-level optimality condition is replaced by the constraint h(z)=||∇_y g(z)||^2 ≤ ε^2. At each iteration the search direction is obtained from a convex QCQP with a closed-form projection solution, and the step size is chosen by a backtracking line search enforcing both an Armijo descent condition (7) and a discrete control-barrier safety condition (8). The authors prove anytime feasibility, an O(1/k) ergodic convergence rate for ||Δz_k||^2 (Theorem 2), and that limit points of convergent subsequences are KKT points of (2) (Proposition 2). Numerical experiments on a synthetic quadratic lower-level problem and on a data-hyper-cleaning task are reported.
Significance. If the convergence result holds, the paper offers a useful alternative to hypergradient and penalty-based bilevel methods: the search direction has a closed form, the algorithm is single-loop, and the line search provably maintains lower-level feasibility while ensuring upper-level descent. The proof structure is transparent, with an explicit QCQP projection formula and a clear descent/safety decomposition. The authors also provide code, which strengthens reproducibility. However, the main convergence theorem relies on a global coercivity assumption (Assumption 4) that is not satisfied by the paper's own numerical examples, so the central claim is not actually validated by the presented experiments. The limit-point argument in Proposition 2 also invokes a converse of Theorem 1(iv) that the theorem does not state. These issues are load-bearing and require revision.
major comments (2)
- [Appendix C, Proposition 2 and Theorem 1(iv)] Assumption 4 (coercivity of h) is the basis for the boundedness of the iterates, which is used in Lemma 1 to obtain uniform Lipschitz constants L_f and L_h and in Proposition 2 to extract a convergent subsequence. The paper's own synthetic example in §III-A violates this assumption: for g(x,y)=1/2||Hy-x||^2 with invertible H, h(z)=||H^T(Hy-x)||^2 vanishes on the affine manifold y=H^{-1}x, which is unbounded in (x,y). Hence the sublevel set {z : h(z) ≤ ε^2} is unbounded and Assumption 4 is false. A similar failure occurs in the DHC task: taking y=0 and letting the corruption weights x_i tend to -∞ makes ∇_y g tend to 0 while ||z||→∞. Consequently, the uniform step-size lower bound t_min, the O(1/k) rate in Theorem 2, and the limit-point claim in Proposition 2 are not justified for the reported experiments. The manuscript needs either a weaker replacement for coercivity that the examples satisfy, or boundedness/global-Lipschitz assumptions that are explicitly verified, or a discussion that the numerical results are outside the theoretical scope.
- [Lemma 1, proof of lower bound] Proposition 2 concludes that a limit point z̄ is a KKT point of (2) because G(z̄)=0 and Theorem 1(iv) states that a KKT point of (2) yields Δz=0. This is the converse of what is needed. Theorem 1(iv) as written only gives one direction; the converse is in fact true (Δz=0 together with the QCQP KKT conditions implies the KKT conditions of (2)), but it is not stated or proved. Since the proposition is the result that establishes the stationarity of limit points, the manuscript should state and prove the 'if and only if' version, or provide a separate argument that G(z)=0 implies z is a KKT point of (2).
minor comments (5)
- [§III-B, Figures 3-4] The abstract and conclusion describe the method as 'tuning-free' and 'requires no hyperparameter tuning,' but Algorithm 1 depends on the user parameters w, ε, α_b, γ, α_ls, β, and t_max. Please clarify what is meant by tuning-free, or soften this claim.
- [Table I] The notation 'p=0.1' and 'p=0.25' in the figure legends and text is not defined in the manuscript; it presumably denotes the corruption rate in the DHC task. Please define it.
- [Lemma 1 proof] In Table I, the 'LL' column entries 'SC (g)', 'PL (g)', and 'PL (h)' are cryptic; the distinction between assumptions on g and on h=||∇_y g||^2 should be explained in the table caption or text.
- [Throughout] In the proof of Lemma 1, the sentence 'condition (8) ensures that h(z_{k+1}) < ε^2 (if h(z_0) < ε^2)' is slightly inaccurate: (8) only guarantees ≤, and strict inequality holds only when h(z_k) < ε^2 and γ>0. This is a minor wording issue, but it should be corrected.
- [Throughout] The manuscript contains several typos and minor formatting issues, including 'Liptchitz' in Remark 5, unicode math artifacts such as '⇐ ⇒' and 'ϵ-KKT' inconsistencies, and a citation with a raw LaTeX macro in the reference [19]. A careful proofreading pass would improve readability.
Circularity Check
No significant circularity: the discrete algorithm, the QCQP direction, and the line-search convergence proof are self-contained; the self-citations are contextual and not used as proof inputs.
full rationale
Algorithm 1's convergence proof is derived directly from the QCQP's KKT conditions (Theorem 1), the Armijo condition (7), and the discrete-time barrier condition (8). The step-size lower bound in Lemma 1 is obtained by applying the descent lemma to grad f and grad h under the stated Lipschitz and coercivity assumptions; no parameter is fitted to data and then reported as a prediction. The ergodic bound in Theorem 2 is a standard telescoping-sum consequence of the descent inequality and the uniform step-size lower bound. The continuous-time framework in [23] motivates the QCQP and line-search design, and [32] provides a supplementary epsilon-KKT equivalence in the extended appendix, but neither is used as a proof ingredient for the discrete convergence theorem, and the theorem does not assume its own conclusion. The concern that the synthetic example may violate Assumption 4 is a correctness or assumption-validity issue, not a circularity: it challenges whether the hypotheses hold for a particular experiment, not whether the derivation reduces to its inputs.
Assumptions & free parameters
free parameters (7)
- w (tilting parameter) =
1e-1, 1e-2, 1e-3 in experiments
- epsilon (feasibility tolerance) =
0.1 or 0.5 in experiments
- alpha_b =
0.1 in experiments
- gamma =
0.1 in experiments
- alpha_ls =
0.1 in experiments
- beta =
0.5 in experiments
- t_max =
1 in experiments
assumptions (7)
- domain assumption Assumption 1: f is continuously differentiable with locally Lipschitz gradient
- domain assumption Assumption 2: g is twice continuously differentiable with locally Lipschitz second derivatives
- domain assumption Assumption 3: nabla_y g(z) is not in the null space of [nabla^2_yx g, nabla^2_yy g]^T whenever nabla_y g(z) != 0
- domain assumption Assumption 4: h is coercive
- standard math KKT theory and Slater's condition for convex QCQPs
- standard math Descent lemma for smooth functions
- standard math Bolzano-Weierstrass theorem
Cite this review
Pith. "Pith review of Sequential QCQP for Bilevel Optimization with Line Search." pith.science (2026). https://pith.science/paper/VWDZC4Z2
@misc{pith2026250514647,
author = {Pith},
title = {Pith review of: Sequential QCQP for Bilevel Optimization with Line Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/VWDZC4Z2}},
note = {Machine review of arXiv:2505.14647}
}
read the original abstract
Bilevel optimization involves a hierarchical structure where one problem is nested within another, leading to complex interdependencies between levels. We propose a single-loop, tuning-free algorithm that guarantees anytime feasibility, i.e., approximate satisfaction of the lower-level optimality condition, while ensuring descent of the upper-level objective. At each iteration, a convex quadratically-constrained quadratic program (QCQP) with a closed-form solution yields the search direction, followed by a backtracking line search inspired by control barrier functions to ensure safe, uniformly positive step sizes. The resulting method is scalable, requires no hyperparameter tuning, and converges under mild local regularity assumptions. We establish an O(1/k) ergodic convergence rate in terms of a first-order stationary metric and demonstrate the algorithm's effectiveness on representative bilevel tasks.
Reference graph
Works this paper leans on
-
[32]
Perturbed Gradient Descent via Convex Quadratic Approximation for Nonconvex Bilevel Optimization
N. Abolfazli, S. Sharifi, M. Fazlyab, and E. Y . Hamedani, “Perturbed gradient descent via convex quadratic approximation for nonconvex bilevel optimization,” arXiv preprint arXiv:2504.17215 , 2025
work page Pith review arXiv 2025
-
[1]
Bilevel programming for hyperparameter optimization and meta-learning,
L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, “Bilevel programming for hyperparameter optimization and meta-learning,” in International Conference on Machine Learning , pp. 1568–1577, PMLR, 2018
work page 2018
-
[2]
Value function based difference-of-convex algorithm for bilevel hyperparameter selection problems,
L. L. Gao, J. Ye, H. Yin, S. Zeng, and J. Zhang, “Value function based difference-of-convex algorithm for bilevel hyperparameter selection problems,” in International conference on machine learning , pp. 7164– 7182, PMLR, 2022
work page 2022
-
[3]
Bilevel optimization for planning through contact: A semidirect method,
B. Landry, J. Lorenzetti, Z. Manchester, and M. Pavone, “Bilevel optimization for planning through contact: A semidirect method,” in The International Symposium of Robotics Research , pp. 789–804, Springer, 2019
work page 2019
-
[4]
Fast uav trajectory optimization using bilevel optimization with analytical gradients,
W. Sun, G. Tang, and K. Hauser, “Fast uav trajectory optimization using bilevel optimization with analytical gradients,” IEEE Transactions on Robotics, vol. 37, no. 6, pp. 2010–2024, 2021
work page 2010
-
[5]
Bilevel Optimization for Real-Time Control with Application to Locomotion Gait Generation
Z. Olkin and A. D. Ames, “Bilevel optimization for real-time con- trol with application to locomotion gait generation,” arXiv preprint arXiv:2409.12366, 2024
work page Pith review arXiv 2024
-
[6]
Hyperparameter optimization with approximate gradient,
F. Pedregosa, “Hyperparameter optimization with approximate gradient,” in Proceedings of the 33nd International Conference on Machine Learning (ICML), 2016
work page 2016
-
[7]
Generic methods for optimization-based modeling,
J. Domke, “Generic methods for optimization-based modeling,” in Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , pp. 318–326, 2012
work page 2012
Show all 34 references
-
[8]
Approximation methods for bilevel program- ming,
S. Ghadimi and M. Wang, “Approximation methods for bilevel program- ming,” arXiv preprint arXiv:1802.02246 , 2018
2018 arXiv
-
[9]
Bilevel optimization: Convergence analysis and enhanced design,
K. Ji, J. Yang, and Y . Liang, “Bilevel optimization: Convergence analysis and enhanced design,” in International Conference on Machine Learning , pp. 4882–4892, 2021
2021
-
[10]
Truncated back- propagation for bilevel optimization,
A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, “Truncated back- propagation for bilevel optimization,” in The 22nd International Con- ference on Artificial Intelligence and Statistics , pp. 1723–1732, PMLR, 2019
2019
-
[11]
On the iteration complexity of hypergradient computation,
R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, “On the iteration complexity of hypergradient computation,” in International Conference on Machine Learning , pp. 3748–3758, PMLR, 2020
2020
-
[12]
Big hype: Best intervention in games via distributed hypergradient descent,
P. D. Grontas, G. Belgioioso, C. Cenedese, M. Fochesato, J. Lygeros, and F. D ¨orfler, “Big hype: Best intervention in games via distributed hypergradient descent,” IEEE Transactions on Automatic Control , 2024
2024
-
[13]
A primal-dual-assisted penalty approach to bilevel optimization with coupled constraints,
L. Jiang, Q. Xiao, V . M. Tenorio, F. Real-Rojas, A. G. Marques, and T. Chen, “A primal-dual-assisted penalty approach to bilevel optimization with coupled constraints,” arXiv preprint arXiv:2406.10148 , 2024
2024 arXiv
-
[14]
A primal-dual approach to bilevel optimization with multiple inner minima,
D. Sow, K. Ji, Z. Guan, and Y . Liang, “A primal-dual approach to bilevel optimization with multiple inner minima,” arXiv preprint arXiv:2203.01123, 2022
2022 arXiv
-
[15]
On penalty-based bilevel gradient descent method,
H. Shen and T. Chen, “On penalty-based bilevel gradient descent method,” in International Conference on Machine Learning , pp. 30992–31015, PMLR, 2023
2023
-
[16]
Penalty method for inversion-free deep bilevel optimization,
A. Mehra and J. Hamm, “Penalty method for inversion-free deep bilevel optimization,” in Asian conference on machine learning , pp. 347–362, PMLR, 2021
2021
-
[17]
Bome! bilevel optimization made easy: A simple first-order approach,
B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu, “Bome! bilevel optimization made easy: A simple first-order approach,” Advances in neural information processing systems , vol. 35, pp. 17248–17262, 2022
2022
-
[18]
A fully first-order method for stochastic bilevel optimization,
J. Kwon, D. Kwon, S. Wright, and R. D. Nowak, “A fully first-order method for stochastic bilevel optimization,” in International Conference on Machine Learning , pp. 18083–18113, PMLR, 2023
2023
-
[19]
Global convergence of arbitrary-block gradient methods for generalized polyak- {\L} ojasiewicz functions,
D. Csiba and P. Richt ´arik, “Global convergence of arbitrary-block gradient methods for generalized polyak- {\L} ojasiewicz functions,” arXiv preprint arXiv:1709.03014 , 2017
2017 arXiv
-
[20]
Control barrier function based quadratic programs for safety critical systems,
A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” IEEE Transactions on Automatic Control , vol. 62, no. 8, pp. 3861–3876, 2016
2016
-
[21]
Orthog- onal directions constrained gradient method: from non-linear equality constraints to stiefel manifold,
S. Schechtman, D. Tiapkin, M. Muehlebach, and E. Moulines, “Orthog- onal directions constrained gradient method: from non-linear equality constraints to stiefel manifold,” in The Thirty Sixth Annual Conference on Learning Theory , pp. 1228–1258, PMLR, 2023
2023
-
[22]
Control barrier function-based design of gra- dient flows for constrained nonlinear programming,
A. Allibhoy and J. Cort ´es, “Control barrier function-based design of gra- dient flows for constrained nonlinear programming,” IEEE Transactions on Automatic Control , 2023
2023
-
[23]
Safe gradient flow for bilevel optimization,
S. Sharifi, N. Abolfazli, E. Y . Hamedani, and M. Fazlyab, “Safe gradient flow for bilevel optimization,” arXiv preprint arXiv:2501.16520 , 2025
2025 arXiv
-
[24]
Practical considerations for discrete-time implementations of continuous-time control barrier function-based safety filters,
L. Brunke, S. Zhou, M. Che, and A. P. Schoellig, “Practical considerations for discrete-time implementations of continuous-time control barrier function-based safety filters,” in 2024 American Control Conference (ACC), pp. 272–278, IEEE, 2024
2024
-
[25]
Nesterov,Lectures on convex optimization , vol
Y . Nesterov,Lectures on convex optimization , vol. 137. Springer, 2018
2018
-
[26]
Discrete control barrier functions for safety-critical control of discrete systems with application to bipedal robot navigation.,
A. Agrawal and K. Sreenath, “Discrete control barrier functions for safety-critical control of discrete systems with application to bipedal robot navigation.,” in Robotics: Science and Systems , vol. 13, pp. 1–10, Cambridge, MA, USA, 2017
2017
-
[27]
Robust safety under stochastic uncertainty with discrete-time control barrier functions,
R. K. Cosner, P. Culbertson, A. J. Taylor, and A. D. Ames, “Robust safety under stochastic uncertainty with discrete-time control barrier functions,” arXiv preprint arXiv:2302.07469 , 2023
2023 arXiv
-
[28]
MNIST handwritten digit database,
Y . LeCun, C. Cortes, C. Burges, et al. , “MNIST handwritten digit database,” 2010
2010
-
[29]
Forward and reverse gradient-based hyperparameter optimization,
L. Franceschi, M. Donini, P. Frasconi, and M. Pontil, “Forward and reverse gradient-based hyperparameter optimization,” in International conference on machine learning , pp. 1165–1173, PMLR, 2017
2017
-
[30]
A moving balls approximation method for a class of smooth constrained minimization problems,
A. Auslender, R. Shefi, and M. Teboulle, “A moving balls approximation method for a class of smooth constrained minimization problems,” SIAM Journal on Optimization , vol. 20, no. 6, pp. 3232–3259, 2010
2010
-
[31]
Augmented lagrangians with constrained subproblems and convergence to second-order stationary points,
E. G. Birgin, G. Haeser, and A. Ramos, “Augmented lagrangians with constrained subproblems and convergence to second-order stationary points,” Computational Optimization and Applications , 2018
2018
-
[33]
Abbott, Understanding analysis
S. Abbott, Understanding analysis. Springer, 2015
2015
-
[34]
R. G. Bartle and D. R. Sherbert, Introduction to real analysis , vol. 2. Wiley New York, 2000
2000
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.