PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu

arXiv:2609.30501v1cs.LG

TL;DR

General nonconvex lower-level bilevel problems remain poorly covered by existing convexity-based assumptions and first-order surrogates, which can admit saddle points. The paper uses a second-order stationarity surrogate and PROBE to target lower-level local optima; it reports finite-time convergence and better baseline performance on two machine-learning tasks.

  • Problem

    Existing LLNC-BLO methods often require structural assumptions or use first-order stationarity surrogates, which can converge to lower-level saddle points.

    Source: §1 · p. 2

  • Method

    The paper reformulates the lower-level problem with a second-order stationarity surrogate and develops PROBE to probe and escape lower-level saddle points.

    Source: §1 · p. 3

  • Results

    PROBE achieves an upper-level finite-time convergence rate of O(T^-2/5) with lower-level local optimality guarantees and outperforms baselines on LLM data curation and meta-learning tasks.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The SOSP-based surrogate targets lower-level local optima by requiring a positive-semidefinite Hessian, ruling out undesirable saddle points.

    Source: §1 · p. 3

    SOSP does not theoretically preclude non-strict saddle points, whose escape generally requires computationally intractable higher-order derivatives.

    Source: §4 · p. 5

Abstract

from arXiv · show

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, 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 prove that PROBE achieves a finite-time convergence rate of $O(T^{-2/5})$, where T denotes iterations. To our knowledge, this work is the first to establish the finite-time convergence 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 SOTA methods.

1 Introduction

Bilevel optimization remains difficult in general nonconvex lower-level settings, where prior methods use structural assumptions or first-order surrogates that can settle at saddle points. The paper proposes a second-order stationarity surrogate and PROBE to seek lower-level local optima while solving these problems.

1 Introduction

  • PROBE is the only method in the illustrated example that escapes the lower-level saddle point and finds true solutions, unlike PBGD, GALET, MEHA, and SUN-DSBO-SE.The figure plots convergence trajectories and the distance from the true optimum across iterations.Source: §1 · p. 2
  • LLSC and LLGC assumptions simplify analysis but exclude many practical problems, including those with highly nonconvex deep-neural-network objectives.LLSC assumes strong convexity in y; LLGC relaxes this to convexity.Source: §1 · p. 2
  • Existing LLNC-BLO approaches either impose structural assumptions or use first-order stationarity surrogates, which can converge to saddle points and yield solutions substantially worse than the true optimum.The paper's example notes that the PL condition fails and first-order-surrogate methods converge to lower-level saddles.Source: §1 · p. 2
  • The SOS-based lower-level surrogate requires a zero lower-level gradient and a positive-semidefinite Hessian, enforcing local convexity that rules out undesirable saddle points and guarantees at least local optimality with respect to y.Source: §1 · p. 3
  • The SOSP reformulation yields a constrained, nonsmooth problem, while LLNC leaves the upper-level hypergradient ill-defined and without a natural stationarity-gap metric.The paper introduces an augmented convergence metric that progressively shrinks its augmentation parameter to recover solutions to the original problem.Source: §1 · p. 3
  • The authors report that PROBE outperforms existing baselines on both an LLM dataset-curation task and a meta-learning task.Both tasks are formulated as bilevel optimization problems.Source: §1 · p. 3

2 Related Work

Related work traces bilevel optimization from convex lower-level settings toward nonconvex ones, where available approaches remain limited. A separate saddle-escaping literature motivates the paper's focus on lower-level saddles, a setting not addressed by prior bilevel saddle-escaping work.

Bilevel Optimization (BLO)

  • Prior bilevel methods largely assume lower-level strong convexity, while general-convexity relaxations still exclude nonconvex practical scenarios.The cited LLSC works include Franceschi et al. (2018), Ghadimi and Wang (2018), and Ji et al. (2021); LLGC works include Cao et al. (2023) and Liu et al. (2023).Source: §2 · p. 4
  • Existing LLNC-BLO works either impose strong structural assumptions or consider FOSP-based relaxations; these methods fail to distinguish lower-level local minima from saddle points, leading to significantly suboptimal solutions versus the true optimum of original LLNC-BLO problems.Source: §2 · p. 4

Escaping Saddle Points in Single-Level Nonconvex Optimization

  • Single-level saddle-escaping research seeks dimension-efficient methods, but the cited bilevel saddle-escaping studies address upper-level saddles only under LLSC, unlike this paper's lower-level LLNC setting.The cited bilevel studies are Huang et al. (2025) and Chen et al. (2025).Source: §2 · p. 4
  • Single-level nonconvex optimization faces saddle points and NP-hard global optimization, motivating methods that escape saddles while reducing dimension dependence.The passage describes methods with polynomial dimension dependence and later work targeting polylogarithmic dependence.Source: §2 · p. 4

3 The Second-Order Stationarity-Based Lower-Level Surrogate

The lower-level surrogate distinguishes first-order stationary points from second-order stationary points by adding a Hessian condition. Under the strict-saddle condition, this second-order criterion identifies local minima rather than saddle points.

3 The Second-Order Stationarity-Based Lower-Level Surrogate

  • The formulation assumes twice-differentiable upper- and lower-level objectives with stated smoothness conditions.The passage also notes that such smoothness assumptions are widely adopted in bilevel optimization and numerically observed in large-scale models, including LLMs.Source: §3 · p. 4
  • An FOSP requires a zero lower-level gradient, whereas an SOSP additionally requires the minimum eigenvalue of the lower-level Hessian to be nonnegative.The paper defines approximate versions using a tolerance on the gradient norm and, for SOSP, the minimum Hessian eigenvalue.Source: §3 · p. 5
  • Under the strict-saddle assumption, an SOSP yields a local minimum, unlike an FOSP that may be an undesirable saddle point.The paper defines a saddle point as a stationary point that is not a local minimum.Source: §3 · p. 5

4 The Proposed PROBE Algorithm

PROBE uses a second-order-stationarity surrogate to seek locally optimal lower-level solutions and a regularized hypergradient for upper-level updates. Its double-loop design shrinks the regularization while probing for lower-level saddle points.

4 The Proposed PROBE Algorithm

  • An SOSP lower-level estimate plus μ-regularization restores local strong convexity, enabling a locally unique implicit solution and a μ-augmented hypergradient.The prose defines that hypergradient as ∇Φμ and says local strong convexity guarantees existence and uniqueness.Source: §4 · p. 5
  • An SOSP does not rule out non-strict saddle points, which may occur in highly overparameterized deep-learning landscapes.The passage contrasts this boundary with escaping strict saddles, including local maxima.Source: §4 · p. 5
  • The convergence metric Π(x, y) combines the squared norm of the μ-augmented hypergradient with the lower-level SOSP violation.Its stated definition assumes y is an ϵ′-SOSP and all saddle points are strict.Source: §4 · pp. 5–6
  • PROBE uses an inner loop to find an ϵt-SOSP and an outer loop to update x using a μt-augmented hypergradient, with μt shrinking toward zero.Shrinking μt progressively reduces hypergradient approximation bias toward the original LLNC-BLO problem.Source: §4 · p. 6
  • PGD injects noise when the lower-level gradient is small and confirms an approximate SOSP after insufficient function-value reduction; warm-started conjugate gradient estimates the outer-loop adjoint.The inner loop returns its identified SOSP estimate to the outer loop at each iteration.Source: §4 · p. 7

5 Finite-Time Convergence Analysis of PROBE

The analysis establishes finite-time convergence for PROBE with a lower-level SOSP guarantee, without requiring the PL condition. Its rate depends on a trade-off among parameter schedules, step size, and inner-loop accuracy.

5 Finite-Time Convergence Analysis of PROBE

  • For (p, q) = (1/5, 3/5), Algorithm 1’s generated sequence has a convergence guarantee for the minimum Π(x_t, y_t) over iterations 2 through T, with probability at least 1−δ.Source: §5 · p. 7
  • The proof controls lower-level and adjoint tracking errors, bounds changes in the augmented implicit function, then uses a dynamic Lyapunov function and telescoping sum.Together these steps bound error terms and establish finite-time convergence.Source: §5 · p. 8
  • A larger p can yield a faster rate, but q ≥ 3p requires a small learning rate αt; the authors choose (p, q) = (1/5, 3/5) to balance the trade-off.At q = 3p, the smoothness coefficient scales as Θ((t+1)^-3p).Source: §5 · p. 8
  • PROBE increases inner-loop iterations Kt over time to reduce the lower-level error ϵt and the associated augmentation μt toward zero.This creates the two-timescale design needed to control the augmentation error.Source: §5 · p. 8

6 Experimental Results

On the HelpSteer data-curation task, PROBE compares favorably with LLNC-BLO baselines in upper-level convergence and wall-clock time. The experiments also examine the effect of inner-loop iterations on PROBE’s upper-level loss.

6 Experimental Results

  • PBGD and GALET fail to converge on data curation, while MEHA, SUN-DSBO-SE, and PROBE reach better upper-level solutions; PROBE outperforms all baselines in wall-clock time.Figure 2 plots upper-level loss with standard-error bars over five trials; theoretical rates are not directly comparable across these methods.Source: Figure 2 · p. 8, §6 · p. 9
  • The data-curation experiment uses HelpSteer and Llama-3.2-3B-Instruct, with training-data weights as upper-level variables and LLM parameters as lower-level variables.The passage identifies the lower-level problem as nonconvex.Source: §6 · p. 8
  • Increasing inner-loop PGD iterations K significantly improves PROBE’s upper-level loss in Figures 3a and 3b.The passage attributes this pattern to small K restricting PGD’s ability to probe and escape saddle points.Source: Figure 3 · p. 9

7 Conclusion

The paper develops PROBE for bilevel optimization with nonconvex lower levels, using a second-order stationarity-based surrogate. It establishes finite-time convergence and reports experiments on LLM data curation.

7 Conclusion

  • Figure 4 is identified as an ablation study.Source: Figure 4 · p. 9
  • The second-order stationarity-based surrogate addresses lower-level saddle points that existing first-order stationarity-based surrogates often fail to escape.The paper develops PROBE based on this surrogate.Source: §7 · p. 9
  • The paper establishes a finite-time convergence rate for PROBE.The conclusion does not specify the rate value.Source: §7 · p. 9
  • Experiments on dataset curation for LLM fine-tuning validate PROBE.Source: §7 · p. 9

A.1 Meta-Learning Experiments

The meta-learning experiment uses task-specific adaptation at the lower level and representation learning at the upper level. In this convex, not strongly convex lower-level setting, PROBE converges fastest while all compared methods converge.

A.1 Meta-Learning Experiments

  • The lower level adapts to tasks using training data, while the upper level improves representation utility for generalization.Source: §A.1 · p. 14
  • The experiment uses five heterogeneous MNIST training tasks, each mixing 80% of a selected digit pair with 20% of other pairs.Validation uses the test split with the same five task ratios.Source: §A.1 · p. 14
  • The lower-level problem is convex but not strongly convex because the loss is convex and y represents a linear layer.Source: §A.1 · p. 14
  • PROBE converges fastest in the meta-learning task, while all baselines and PROBE converge at both levels.Figure 5 presents the baseline comparison; the experiment is in an LLGC setting.Source: §A.1 · p. 14, Figure 5 · p. 14

A.2 Implementation Details and Additional Results on Data Curation Task

The data-curation experiments compare lower-level performance across methods using an LLM fine-tuned on HelpSteer. PROBE is reported as the most efficient method, while GALET’s seemingly favorable lower-level solutions are generally suboptimal.

A.2 Implementation Details and Additional Results on Data Curation Task

  • The data-curation task fine-tunes Llama-3.2-3B-Instruct on HelpSteer, separating responses into high-quality and low-quality sets using average-score thresholds.High-quality training examples have scores ≥2.5 and low-quality examples have scores ≤2; validation contains high-quality data only.Source: §A.2 · pp. 14–15
  • The comparison fixes total iterations at 20,000, reports 100 iterations, and repeats each experiment five times with standard error bars.Baseline results use the best-performing tested configurations.Source: §A.2 · p. 15
  • PROBE converges in the shortest running time and performs consistently well in validation, whereas GALET’s seemingly favorable lower-level solutions are generally suboptimal.Figure 6 presents lower-level performance; the suboptimality assessment is made alongside Figure 2.Source: §A.2 · p. 15, Figure 6 · p. 15

B Proof of Main Result

The proof establishes a high-probability convergence guarantee for PROBE under a parameter schedule. It controls lower-level approximation, conjugate-gradient error, and changes in the augmented objective to obtain the bound.

B Proof of Main Result

  • Under 3p ≤ q < 1, Theorem 1 gives a convergence guarantee for the sequence generated by Algorithm 1 with probability at least 1−δ.The proof’s bound is expressed using the convergence metric Π(xt, yt).Source: B Proof of Main Result · pp. 15–16
  • With p = 1/5 and q = 3/5, the proof specializes the convergence guarantee to the selected parameter schedule.The supplied result passage identifies these parameter values but truncates the resulting bound.Source: B Proof of Main Result · pp. 16, 20
  • With probability at least 1−δ′, Algorithm 2 ensures y_{t+1} is an ϵ_t-SOSP: ∥∇_y g(x_t,y_{t+1})∥≤ϵ_t and λ_min(∇²_yy g(x_t,y_{t+1}))≥−√ρϵ_t.Source: B Proof of Main Result · p. 16
  • The proof separately controls conjugate-gradient error by comparing its approximate solution with the exact solution of the regularized Hessian linear system.The system uses the lower-level Hessian plus µtI and the upper-level gradient as its right-hand side.Source: B Proof of Main Result · p. 17

C Details of Illustrative Example

The illustrative example contrasts first-order-stationarity surrogates with PROBE on a nonconvex lower level. In the example, PROBE escapes a lower-level saddle point that can mislead the first-order approaches.

C Details of Illustrative Example

  • The example represents existing approaches as solving a lower-level surrogate based on first-order stationarity or an equivalent formulation under additional assumptions.The cited approaches are Xiao et al. (2023), Shen and Chen (2023), Liu et al. (2024), and Ma et al. (2026).Source: C Details of Illustrative Example · p. 20
  • Substituting the first-order stationary condition into the upper-level problem yields candidate solutions including (2, 0), which is a saddle point of the lower-level objective.The other two candidates are identified as true solutions.Source: C Details of Illustrative Example · p. 20
  • In the example, the first-order-stationarity methods can be drawn to the lower-level saddle point, whereas PROBE escapes it and finds an optimal solution.The passage identifies PBGD, GALET, MEHA, and SUN-DSBO-SE as the compared methods.Source: C Details of Illustrative Example · p. 20

D Scope and Implications of SOSP Guarantees

The SOSP guarantee excludes stationary points with negative-curvature directions and, under strict-saddle conditions, corresponds to a lower-level local minimum. It does not ensure selection of the best lower-level local minimum.

D Scope and Implications of SOSP Guarantees

  • PROBE is not guaranteed to select the best among multiple lower-level local minima; finding the global minimum is generally NP-hard.Without additional structural assumptions, the effects of different lower-level local solutions on the upper-level problem cannot generally be characterized.Source: D Scope and Implications of SOSP… · p. 20
  • An SOSP excludes stationary points admitting a negative-curvature direction, making its stationarity guarantee stronger than FOSP without requiring the strict-saddle property.The strict-saddle property is used to conclude that an SOSP corresponds to a lower-level local minimum.Source: D Scope and Implications of SOSP… · p. 21
  • Across five PROBE trials, all 61 encountered saddle points had a negative minimum eigenvalue of the lower-level Hessian.The paper presents this as empirical evidence that the encountered saddles in these runs were strict.Source: D Scope and Implications of SOSP… · p. 21

Related papers

Loading 2609.30501v1…