acceptodds
Under review as a conference paper at ICLR 2027

To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

Abstract

Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.e., the lower-level objective function is assumed to be, at least, convex). While the LLSC/LLGC assumptions render more tractable algorithmic design and theoretical analysis, they are too rigid to encompass many machine learning problems in practice. The limitations of LLSC/LLGC assumptions in BLO motivate us to investigate solving the BLO problem in the general lower-level nonconvex (LLNC) settings, which remains in its infancy. In the literature on LLNC-BLO, most of the existing works either require additional structures in the lower-level objective function for tractable theoretical analysis, or adopt the first-order stationarity reformulation as a lower-level surrogate problem, which is inherited from the LLSC/LLGC settings but could lose their effectiveness in the LLNC setting. To bridge this gap, in this work, we propose to reformulate the nonconvex lower-level problem using a second-order stationarity-based surrogate, the solution of which guarantees a local optimal solution at the lower level. Based on this reformulation, we propose the PROBE (Perturbed gradient algorithm for bilevel problem) and show that it overcomes the limitations of prior works by probing and escaping lower-level saddle points. We theoretically prove that PROBE achieves a finite-time convergence rate of , where denotes iterations. To our knowledge, this work is the first to establish the finite-time convergence rate guarantee for achieving lower-level second-order stationary solutions in general LLNC-BLO. Our experiments on both a large language model-based data curation task and a meta-learning task also show that PROBE outperforms state-of-the-art methods.

Primary area:
optimization
Keywords:
Bilevel optimization, non-convexity, second-order stationarity.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_TJfZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies an important problem in bilevel optimization and proposes an interesting algorithmic framework based on second-order stationarity. The technical development is non-trivial, and the convergence analysis appears carefully constructed. However, I have concerns about the paper's main contribution and positioning. The claim that the work provides a fundamentally new solution to general nonconvex lower-level bilevel optimization is not sufficiently supported given the recent progress in LLNC-BLO. The proposed SOSP surrogate is a meaningful technical direction, but its novelty relative to existing formulations and its practical significance are not convincingly demonstrated.

Critical strengths

The observation that first-order stationarity is insufficient to distinguish local minima from saddle points in nonconvex lower-level problems is important. The proposed SOSP-based surrogate provides a principled way to incorporate curvature information into the lower-level solution concept.

Critical weaknesses
  1. The novelty relative to recent LLNC-BLO literature is unclear. The main claimed contribution is the use of second-order stationarity as a lower-level surrogate for general nonconvex bilevel optimization. However, recent works have already moved beyond traditional convex/FOSP-based formulations by considering meaningful lower-level solution concepts, local solution behavior, and nonconvex lower-level structures. For example, recent approaches based on Moreau-envelope reformulations and correspondence-driven formulations have already addressed important limitations of FOSP-based LLNC-BLO methods. In particular, correspondence-driven approaches consider algorithmically generated lower-level solutions and use second-order optimization techniques to handle nonconvex lower-level behavior. The paper does not provide a sufficiently detailed comparison explaining why the proposed SOSP surrogate is fundamentally different from these recent directions. The distinction appears to be mainly in the specific formulation and algorithmic implementation rather than a clearly new problem perspective. This weakens the central novelty claim of the paper.

  2. The theoretical guarantee relies on assumptions whose practical relevance is unclear. The proposed approach relies on second-order stationarity to avoid saddle points. However, the implication from SOSP to local minimum requires additional structural assumptions, such as strict saddle properties. While these assumptions are standard in some nonconvex optimization settings, their validity in modern deep learning models is not established. Therefore, the paper's motivation that SOSP resolves the lower-level optimization difficulty may be stronger than what is actually supported by the theory. A clearer discussion of the gap between the theoretical surrogate and practical deep learning landscapes would be needed.

  3. The experiments do not sufficiently validate the claimed mechanism. The experiments mainly compare the final upper-level objective performance against existing LLNC-BLO algorithms. While the results show that PROBE performs competitively, they do not directly evaluate whether the algorithm indeed escapes lower-level saddle points more effectively.

Questions for authors

Recent LLNC-BLO works have proposed alternatives to FOSP-based formulations, including Moreau-envelope based approaches and correspondence-driven formulations. Could the authors provide a more detailed comparison explaining the fundamental differences between these methods and the proposed SOSP-based surrogate?

Is the proposed SOSP formulation mainly motivated as a computational surrogate, or does it aim to approximate the true lower-level local/global optimum? Under what practical conditions can the authors justify that an SOSP solution is sufficient for the original bilevel problem?

The theoretical results rely on strict saddle assumptions to connect SOSP with local minima. Do the authors have empirical evidence that the lower-level problems arising in their applications approximately satisfy this property?

Can the authors provide additional experiments directly measuring whether PROBE escapes saddle points more effectively than existing methods?

Reviewer_NUUaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies bilevel optimization with general nonconvex lower-level objectives, where first-order stationarity-based surrogates may admit undesirable saddle points. To address this limitation, the authors propose a second-order stationarity-based surrogate that excludes strict saddle points and targets lower-level local minima under the strict-saddle assumption.

Based on this formulation, the authors develop PROBE, which integrates several existing techniques: perturbed gradient descent (Jin et al., 2017) to escape lower-level saddle points, local quadratic regularization to ensure Hessian invertibility, and conjugate-gradient-based implicit differentiation for upper-level hypergradient estimation.

The paper establishes a finite-time convergence rate of O(T−2/5)O(T^{-2/5}) under the proposed augmented stationarity metric. Experiments on LLM data curation and meta-learning tasks report favorable performance compared with several existing bilevel optimization methods.

Critical strengths
  1. The paper is clearly written and well organized, making the motivation and proposed methodology easy to follow.

  2. The proposed second-order stationarity-based surrogate improves upon first-order stationarity by excluding strict saddle points at the lower level. The paper also provides a finite-time convergence analysis for the proposed method.

  3. The experiments include LLM fine-tuning with a LoRA PEFT on 3B-parameter model, demonstrating the potential applicability of the proposed method to relatively large-scale machine learning problems.

Critical weaknesses
  1. The algorithmic novelty appears limited, as the proposed method mainly integrates existing techniques into bilevel optimization. The practical need for explicit saddle-point escaping is also unclear, since gradient descent with random initialization already avoids strict saddles under suitable conditions. Furthermore, the method is restricted to unconstrained lower-level problems, and extending it to even simple box constraints may be nontrivial.

  2. The proposed surrogate does not guarantee global lower-level optimality, and the convergence result concerns an augmented stationarity metric rather than the original bilevel problem. Moreover, the overall computational complexity, including increasing inner-loop iterations and conjugate-gradient steps, is not clearly discussed.

  3. The literature discussion on page 2 is somewhat difficult to follow, as methods under PL conditions, bounded domains, and general nonconvexity are discussed together. A clearer comparison table, with additional details in the appendix, would help distinguish their assumptions and limitations.

  4. The supplementary material contains only one Python file (main_PROBE.py), without the baseline implementations. Moreover, the provided code appears to contain several issues:

    • The weighted cross-entropy loss applies dataset weights after averaging the loss, rather than weighting individual samples.
    • The dataset labeling uses len(template_tra[0]) instead of len(templates[0]), potentially assigning incorrect dataset labels.
    • The causal language-model loss uses unshifted logits and labels, which may lead to incorrect next-token prediction training.

    These issues raise concerns about the reproducibility and reliability of the experimental results, particularly the surprisingly poor performance of PBGD.

Questions for authors
  1. The supplementary code appears to contain issues in dataset labeling, weighted cross-entropy, and causal language-model loss alignment. Could the authors verify these implementations and provide the baseline code? In particular, PBGD performs surprisingly poorly in Figure 2. Could shorter inner loops (e.g., 1, 5, or 10 steps) and properly tuned penalties improve its performance? Comparisons with more recent first-order bilevel methods (inner 1 step), such as PBGD-Free (Jiang et al., 2025), F²BA (Chen et al., 2025), would help assess the practical advantages of PROBE, particularly its computational efficiency.

  2. Could the authors provide direct evidence that existing methods are trapped at lower-level strict saddle points? In Figures 2 and 6, some baselines achieve low lower-level losses but poor upper-level performance, which does not necessarily indicate saddle-point trapping. Comparisons with randomly initialized or stochastic GD would be helpful.

  3. In Appendix B, the quadratic regularization center changes across outer iterations. How does the analysis account for this change and possible switching between local minima? The proof also appears to require a lower-bounded objective, which is not explicitly assumed.

  4. Do the experimental settings satisfy the assumptions required by the theoretical analysis? For example, the meta-learning experiment uses ReLU activations, while the LLM experiment involves minibatch training. Moreover, the experiments use fixed inner-loop lengths and regularization parameters, unlike the theoretical schedules. Could the authors clarify how the convergence guarantees apply to these settings?

Reviewer_iwDoOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies bilevel optimization with nonconvex lower-level objectives. The authors argue that first-order stationarity is insufficient in this setting, since the lower-level solution may be a saddle point rather than a local minimum. To address this issue, they propose PROBE, which combines perturbed gradient descent for finding approximate lower-level second-order stationary points with regularized implicit differentiation for the upper-level update. The paper claims an O(T−2/5)O(T^{-2/5}) convergence rate under general smoothness assumptions and reports experiments on LLM data curation and meta-learning.

Critical strengths
  1. The paper addresses an important limitation of existing bilevel optimization methods.

  2. Combining perturbed gradient descent with regularized hypergradient estimation is a reasonable approach.

Critical weaknesses
  1. My main concern is Definition 3 and its relationship to the original bilevel objective. The authors introduce a regularized implicit hypergradient and argue that reducing the regularization parameter allows the resulting metric to approach the desired stationarity condition. I do not think this follows from Assumption 1.

In particular, consider $ g(x,y)=\psi(y-x),\quad f(x,y)=\sin(x-y), $ where $ \psi(s)=\frac{s^4}{1+s^2}+\frac{3s^4}{1+s^4}. $

This lower objective is smooth, genuinely nonconvex, and has the unique global minimizer (y=x). Its gradient and Hessian satisfy the required Lipschitz conditions. Since there are no nonminimum stationary points, the strict-saddle condition is also satisfied.

The true bilevel objective is F(x)=f(x,x)=0F(x)=f(x,x)=0, so every feasible point is optimal. However, at (y=x), both (g_{yy}) and (g_{xy}) vanish. Consequently, the regularized hypergradient in Section 4 equals (f_x=1), independently of how small the regularization parameter becomes.

This problem also persists for approximate lower-level solutions. Near the minimizer, ψ′(s)=O(s3)\psi'(s)=O(s^3) and ψ′′(s)=O(s2)\psi''(s)=O(s^2). Under the schedule ϵt=σt4/ρ\epsilon_t=\sigma_t^4/\rho used in Theorem 2, the lower-level accuracy implies a displacement of order O(σt4/3)O(\sigma_t^{4/3}). The corresponding augmented Hessian is O(σt8/3)O(\sigma_t^{8/3}), while μt=Θ(σt)\mu_t=\Theta(\sigma_t). Therefore, the regularized hypergradient approaches 1 rather than 0.

This seems inconsistent with the claimed convergence of Π(xt,yt)\Pi(x_t,y_t) to zero. I would like the authors to explain whether an additional nondegeneracy assumption is intended or whether the convergence metric needs to be modified.

  1. In Section 4, the augmented lower-level problem is regularized around an approximate SOSP. In Algorithm 1, this point is updated by PGD at every outer iteration.

However, the bounds in Part A of Appendix B compare augmented solutions while keeping the regularization center fixed. The later Lyapunov analysis appears to treat the resulting augmented objectives as if they belonged to the same sequence of functions without accounting for the change in this center.

More explicitly, writing the augmented objective as Φμ,a\Phi_{\mu,a}, the interiteration difference contains an additional term involving $ \Phi_{\mu_{t+1},a_t}(x_{t+1}), $ where ata_t denotes the PGD output. I could not find a bound for this term in Parts A–D.

This matters because the augmented lower solution and its implicit gradient both depend on the regularization center. Unless the authors can establish a suitable tracking bound, it is unclear how the descent and telescoping arguments in Appendix B follow.

There are also smaller issues with the proof notation, including the use of yty_t versus yt+1y_{t+1} in the stationarity guarantee and the inconsistent sign of the adjoint variable between Parts A and B.

Questions for authors
  1. Can the authors clarify why the augmented hypergradient should approach a valid stationarity measure when the lower-level Hessian is singular? In particular, how does Theorem 2 handle the example given above?

  2. How is the change in the regularization center controlled in the Lyapunov analysis? Is there an additional argument establishing that consecutive augmented objectives remain sufficiently close?

  3. Can the authors provide convergence diagnostics related to the proposed stationarity metric, rather than only upper- and lower-level loss curves?

  4. How sensitive is the empirical performance to the fixed regularization parameter, and how does the practical implementation relate to the decreasing schedule required by the theory?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.