pith. sign in

arxiv: 2606.20534 · v1 · pith:Q2V6B6MCnew · submitted 2026-06-18 · 🧮 math.OC

On Second-Order Methods for Bilevel Optimization

Jiawen Bi , Jiaxiang Li , Mingyi Hong , Shuzhong Zhang This is my paper

Pith reviewed 2026-06-26 15:46 UTC · model grok-4.3

classification 🧮 math.OC
keywords bilevel optimizationcubic regularized Newtonsecond-order stationary pointssingle-loop algorithmoracle complexitynonconvex-strongly-convexhypergradient
0
0 comments X

The pith

A single-loop cubic regularized Newton method achieves the optimal O(ε^{-1.5}) oracle complexity for finding second-order stationary points in nonconvex-strongly-convex bilevel optimization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops second-order methods for bilevel optimization where the upper level is nonconvex and the lower level is strongly convex. It first presents a double-loop baseline using cubic regularized Newton that attains the optimal outer rate but needs repeated lower-level solves. Then it introduces a single-loop variant that performs one lower-level gradient step and one Newton step on the hypergradient per iteration, proving the same optimal deterministic total complexity. This matters because bilevel problems arise in machine learning hyperparameter tuning and design, and efficient second-order methods can find better stationary points than first-order alternatives. The approach avoids the inefficiency of nested loops while maintaining convergence guarantees.

Core claim

The central claim is that a single-loop cubic regularized Newton method, which combines one lower-level gradient step with one Newton step for the hypergradient, achieves an overall deterministic O(ε^{-1.5}) total oracle complexity for finding an ε-SOSP of the hyperfunction in unconstrained NCSC bilevel optimization, and this is the first such deterministic single-loop method with the optimal rate.

What carries the argument

The single-loop cubic regularized Newton algorithm that interleaves one gradient step on the lower-level problem with a Newton step using the hypergradient.

If this is right

  • The method reaches the optimal deterministic rate without repeated inner solves at each outer iteration.
  • It applies to the unconstrained nonconvex-upper strongly-convex-lower bilevel setting.
  • Certain intuitive modifications to the single-loop update can break the convergence guarantee.
  • The double-loop cubic regularized Newton baseline also meets the optimal outer rate but incurs higher inner computation cost.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If strong convexity of the lower level is relaxed, the hyperfunction may lose the smoothness needed for the cubic rate to hold.
  • The single-loop structure might extend to stochastic bilevel settings provided inner gradient accuracy can still be controlled with one step.
  • In hyperparameter optimization tasks the method could locate higher-quality stationary points than first-order bilevel solvers at comparable total cost.
  • Practical implementations would need to verify whether the required hyper-Hessian accuracy is attainable with the fixed one-step inner update on real problems.

Load-bearing premise

The lower-level problem is strongly convex and the hyperfunction satisfies standard smoothness conditions so that the cubic regularization framework works once hypergradient and hyper-Hessian oracles reach sufficient accuracy.

What would settle it

A numerical test on a simple bilevel instance where the single-loop method with exactly one inner gradient step per iteration fails to reach an ε-SOSP in O(ε^{-1.5}) total gradient and Hessian-vector product calls.

Figures

Figures reproduced from arXiv: 2606.20534 by Jiawen Bi, Jiaxiang Li, Mingyi Hong, Shuzhong Zhang.

Figure 1
Figure 1. Figure 1: f(xk, yk) (left) and g(xk, yk) (right) versus the outer-loop iteration [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: lower level updates of SLCRN and the Newton-update variant. On the right hand side, if [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison between Algorithm 2 and PBO, BO. We start from 4 different initial points x0 in each replication. The x-axis represents the outer loop iteration number, and the y-axis represents the upper level function value f(xk, yk) − Φ ∗ . References J. Bolte, Q.-T. Le, E. Pauwels, and S. Vaiter. Bilevel gradient methods and morse parametric qualification. arXiv preprint arXiv:2502.09074, 2025. (Cited on pa… view at source ↗
read the original abstract

Bilevel optimization is an indispensable modeling tool for modern machine learning and engineering design. However, the theory and practice for finding second order stationary points in the context of bilevel optimization still remain largely unsettled. Even for bilevel optimization with strongly convex lower-level problem, the hyperfunction it induces is in general nonconvex. Although the Cubic Regularized Newton methods (CRN) famously achieve the optimal $\mathcal{O}(\varepsilon^{-1.5})$ SOSP (second-order stationary point) rate in single-level optimization, it is unclear how to control the accuracy of the hypergradient and hyper-Hessian computations in the context of applying the second-order methods to bilevel problems in order for the overall process to be efficient. In this paper, we set out to answer this question. In particular, we first formulate a double loop CRN baseline that achieves the optimal outer rate but requires repeated lower level solves. Next, we propose a single loop cubic regularized Newton algorithm that combines one lower-level gradient step with one Newton step for the hypergradient, and prove an overall deterministic $\mathcal{O}(\varepsilon^{-1.5})$ total oracle complexity, which is optimal. In addition, we illustrate that some intuitively simple modifications of our method may fail to hold up the convergence result. To the best of our knowledge, this is the first deterministic single loop method for unconstrained NCSC (non-convex upper-level and strongly convex lower-level) bilevel optimization setting that achieves the $\mathcal{O}(\varepsilon^{-1.5})$ optimal convergence rate for finding an $\varepsilon$-SOSP of the hyperfunction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript addresses second-order stationary point finding for bilevel optimization in the NCSC setting (non-convex upper level, strongly convex lower level). It first presents a double-loop cubic-regularized Newton baseline that achieves the optimal outer rate but requires repeated lower-level solves. It then proposes a single-loop variant that performs one lower-level gradient step plus one Newton step on the hypergradient, claiming to prove a deterministic total oracle complexity of O(ε^{-1.5}) for an ε-SOSP of the hyperfunction. The paper also shows that certain intuitive modifications of the single-loop scheme fail to preserve the rate.

Significance. If the single-loop complexity analysis is correct, the result would be significant: it would supply the first deterministic single-loop method attaining the optimal O(ε^{-1.5}) rate for second-order points in unconstrained NCSC bilevel optimization, together with an explicit demonstration that simple modifications break the guarantee.

major comments (1)
  1. [Proof of the single-loop complexity result (likely §4 or §5)] The central O(ε^{-1.5}) claim for the single-loop method rests on showing that the hypergradient and hyper-Hessian approximation errors induced by a single lower-level gradient step remain small enough (relative to the cubic regularization radius and target ε) at every outer iteration. The abstract states that a proof exists but supplies no derivation details, explicit inner-loop accuracy schedules, or error-bound translation from outer requirements to the single gradient step; without these, it is impossible to verify whether the deterministic total-oracle bound continues to hold under only strong convexity and standard smoothness.
minor comments (1)
  1. [Introduction / Notation] The acronym NCSC is introduced in the abstract but would benefit from an explicit parenthetical expansion on first use in the main text for readers unfamiliar with the bilevel literature.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting the need for greater transparency in the single-loop complexity analysis. We agree that the current manuscript would benefit from expanded derivation details to make the error control fully verifiable.

read point-by-point responses

  1. Referee: [Proof of the single-loop complexity result (likely §4 or §5)] The central O(ε^{-1.5}) claim for the single-loop method rests on showing that the hypergradient and hyper-Hessian approximation errors induced by a single lower-level gradient step remain small enough (relative to the cubic regularization radius and target ε) at every outer iteration. The abstract states that a proof exists but supplies no derivation details, explicit inner-loop accuracy schedules, or error-bound translation from outer requirements to the single gradient step; without these, it is impossible to verify whether the deterministic total-oracle bound continues to hold under only strong convexity and standard smoothness.

    Authors: We agree that the proof presentation requires additional explicit steps. In the revised version we will insert a new subsection (tentatively §4.3) that (i) states the precise accuracy requirement on the single lower-level gradient step as a function of the current cubic radius and target ε, (ii) derives the resulting hypergradient and hyper-Hessian error bounds under the standard strong-convexity and smoothness assumptions, and (iii) shows how these bounds are absorbed into the cubic-regularized Newton analysis without degrading the O(ε^{-1.5}) total-oracle complexity. The inner-loop schedule will be stated explicitly rather than left implicit. revision: yes

Circularity Check

0 steps flagged

No circularity: standard complexity proof for new single-loop algorithm

full rationale

The paper derives an O(ε^{-1.5}) oracle complexity for its proposed single-loop cubic-regularized Newton method by applying the standard CRN framework to the hyperfunction after establishing oracle accuracy via one lower-level gradient step plus one Newton step on the hypergradient. This is a conventional deterministic convergence analysis under strong convexity of the lower level and smoothness of the hyperfunction; the rate follows from the cubic regularization theory once the approximation errors are controlled, without any fitted parameters, self-definitional quantities, or load-bearing self-citations that reduce the claimed result to its inputs by construction. The result is self-contained against external benchmarks in nonconvex optimization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard smoothness and strong-convexity assumptions for the bilevel problem plus the existence of sufficiently accurate hypergradient and hyper-Hessian oracles; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • domain assumption Lower-level problem is strongly convex; hyperfunction is twice differentiable with Lipschitz continuous derivatives up to order three.
    Invoked to ensure the hyperfunction admits a well-defined second-order stationary point and that cubic regularization applies once oracle accuracy is controlled.

pith-pipeline@v0.9.1-grok · 5821 in / 1539 out tokens · 15728 ms · 2026-06-26T15:46:56.130686+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages · 2 internal anchors

  1. [1]

    Bolte, Q.-T

    J. Bolte, Q.-T. Le, E. Pauwels, and S. Vaiter. Bilevel gradient methods and morse parametric qualification.arXiv preprint arXiv:2502.09074, 2025.(Cited on page 4.) L. Brotcorne, M. Labb´ e, P. Marcotte, and G. Savard. A bilevel model for toll optimization on a multicommodity transportation network.Transportation science, 35(4):345–358, 2001.(Cited on page...

    work page arXiv 2025

  2. [2]

    Colson, P

    (Cited on page 1.) B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization.Annals of operations research, 153(1):235–256, 2007.(Cited on page 1.) D. di Serafino, G. Toraldo, and M. Viola. A gradient-based globalization strategy for the newton method. InInternational Conference on Numerical Computations: Theory and Algorithms, pages 177–...

    2007

  3. [3]

    (Cited on page 1.) C. Fang, Z. Lin, and T. Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pages 1192–1234. PMLR, 2019.(Cited on page 5.) C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. InInternational conference on machine learning, pages 1126–113...

    2019

  4. [4]

    Franceschi, P

    URL https://api.semanticscholar.org/CorpusID:8026824.(Cited on page 4.) L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperpa- rameter optimization and meta-learning. InInternational conference on machine learning, pages 1568–1577. PMLR, 2018.(Cited on pages 1 and 4.) 17 R. Ge, F. Huang, C. Jin, and Y. Yuan. Escap...

    2018

  5. [5]

    Approximation Methods for Bilevel Programming

    URL https: //arxiv.org/abs/1802.02246.(Cited on pages 2, 4, and 6.) S. Ghadimi, H. Liu, and T. Zhang. Second-order methods with cubic regularization under inexact information.arXiv preprint arXiv:1710.05782, 2017.(Cited on page 6.) C. He, B. Jiang, Y. Jiang, C. Zhang, and S. Zhang. History-aware adaptive high-order tensor regularization.arXiv preprint arX...

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  6. [6]

    URL https: //arxiv.org/abs/2301.01716.(Cited on page 4.) L. Luo, Y. Li, and C. Chen. Finding second-order stationary points in nonconvex-strongly-concave minimax optimization.Advances in Neural Information Processing Systems, 35:36667–36679, 2022.(Cited on page 3.) D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through...

    work page arXiv 2022

  7. [7]

    arXiv preprint arXiv:2506.08164 , year=

    Springer Science & Business Media, 2013.(Cited on page 24.) Y. Nesterov and B. T. Polyak. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1):177–205, 2006.(Cited on pages 2, 4, and 5.) H. Reisizadeh, J. Jia, Z. Bu, B. Vinzamuri, A. Ramakrishna, K.-W. Chang, V. Cevher, S. Liu, and M. Hong. Blur: A bi-level op...

    work page arXiv 2013

  8. [8]

    URL https://arxiv.org/abs/2302.05185.(Cited on page 1.) H. Shen, Q. Xiao, and T. Chen. On penalty-based bilevel gradient descent method.Mathematical Programming, pages 1–51, 2025.(Cited on page 4.) 19 A. J. Silv´ erio, R. D. S. Couto, M. E. M. Campista, and L. H. M. K. Costa. A bi-objective optimization model for segment routing traffic engineering.Annals...

    work page arXiv 2025

  9. [9]

    Tripuraneni, M

    URLhttps://api.semanticscholar.org/CorpusID:247004593.(Cited on page 1.) N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M. I. Jordan. Stochastic cubic regularization for fast nonconvex optimization.Advances in neural information processing systems, 31, 2018.(Cited on page 4.) C. Tu, P. Ye, W. Lin, H. Ye, C. Yu, T. Chen, B. Li, and W. Ouyang. Efficient a...

    2018

  10. [10]

    URL https://api.semanticscholar.org/CorpusID:55844116.(Cited on page 10.) Z. Wang, Y. Zhou, Y. Liang, and G. Lan. A note on inexact condition for cubic regularized newton’s method.arXiv preprint arXiv:1808.07384, 2018.(Cited on pages 5, 8, 9, 10, and 24.) W. Xian, F. Huang, and H. Huang. Escaping saddle point efficiently in minimax and bilevel optimizatio...

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  11. [11]

    (Cited on page 1.) S. Zeng, C. Li, A. Garcia, and M. Hong. When demonstrations meet generative world models: A maximum likelihood framework for offline inverse reinforcement learning.Advances in Neural Information Processing Systems, 36, 2024.(Cited on page 1.) C. Zhang, D. Ge, B. Jiang, and Y. Ye. Drsom: A dimension reduced second-order method and prelim...

    work page arXiv 2024

  12. [12]

    By the residual stopping criterion and the µg-strong convexity of g(xk,· ), we have ∥yk,Nk −y ∗(xk)∥ ≤ 1 µg ∥∇yg(xk, yk,Nk)∥ ≤δ k

    Using the triangle inequality and the initializationy k,0 =y k−1,Nk−1, we have ∥yk,0 −y ∗(xk)∥=∥y k−1,Nk−1 −y ∗(xk)∥ ≤ ∥y k−1,Nk−1 −y ∗(xk−1)∥+∥y ∗(xk−1)−y ∗(xk)∥ ≤δ k−1 +L y,1∥sk∥. By the residual stopping criterion and the µg-strong convexity of g(xk,· ), we have ∥yk,Nk −y ∗(xk)∥ ≤ 1 µg ∥∇yg(xk, yk,Nk)∥ ≤δ k. Moreover, since g(xk,· ) is Lg,2-smooth, the...

    2013