Research map / Optimization / Nonconvex and smooth optimization

Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization

NeurIPS 2025 · Optimization › Nonconvex and smooth optimization · approach: Penalty and implicit-gradient bilevel methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces set smoothness for lower-level solution maps in nonconvex-PL bilevel optimization, proves hyper-objectives are weakly convex (pessimistic) or weakly concave (optimistic), and gives a zeroth-order method computing approximate Clarke hyper-stationary points with non-asymptotic guarantees.

Problem

Computing strong (Clarke) hyper-stationary points of bilevel optimization hyper-objectives when the lower-level solution set is multi-valued and the hyper-objective is nonsmooth.

Approach

Defines set smoothness for set-valued maps and shows that error-bound (PL-type) lower-level conditions make the lower-level solution map set smooth, which implies weak convexity/concavity of the optimistic/pessimistic hyper-objectives, enabling zeroth-order computation of Clarke stationarity.

Key results

• Proves set smoothness of the lower-level solution map under an error bound with L_S = max{2H_f tau(1+9L_f^2 tau^2), 4L_f^2 tau^2}, implying rho-weak convexity/concavity of hyper-objectives with rho = M_F L_S + L_F(1+L_S).
• Shows an inexact zeroth-order method attains E[dist(0, Clarke subdifferential)^2] = O(sqrt(m)(Delta_o+1)/sqrt(T)) for optimistic BLO (with delta = O(T^{-1/4})).
• Shows E[||grad phi_{p,gamma}||^2] = O(sqrt(m)(Delta_p+1)/sqrt(T)) for pessimistic BLO via the Moreau envelope.

Surprising findings

• Adding a lower-level constraint can destroy set smoothness and hence weak convexity of the pessimistic hyper-objective (counterexample with box constraint).
• Goldstein stationarity is strictly weaker than Clarke stationarity: a convex 2-Lipschitz function shows a Goldstein stationary point far from Clarke stationarity.

Limitations

• Results require the error-bound (PL-type) lower-level assumption and do not extend to lower-level constrained BLO.
• No experiments are provided; guarantees are theoretical and depend on an inexact oracle for the hyper-objective values.
• Zeroth-order method's complexity is not claimed to be optimal; faster algorithms are left for future work.

Experimental setup

Metrics: expected squared distance to Clarke subdifferential expected squared Moreau envelope gradient norm

Baselines: Goldstein-stationarity zeroth-order bilevel methods penalty-based hyper-objective methods

Builds on: penalty-based bilevel framework Moreau envelope Goldstein stationarity Polyak-Lojasiewicz / error bound conditions

Closest papers by meaning

• First-Order Methods for Linearly Constrained Bilevel Optimization (NeurIPS 2024 · similarity 0.92)
• On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.90)
• Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · similarity 0.90)
• Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.89)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.89)