# On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization

arXiv: https://arxiv.org/abs/2507.23155 · HTML: https://mlsanity.com/paper/2507.23155/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 51 references that are in the map.
- First posted on arXiv 30 Jul 2025.

## Builds on (most cited first, 28 of 28)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization](https://mlsanity.com/paper/2112.12376/) (2021)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [BLUR: A Bi-Level Optimization Approach for LLM Unlearning](https://mlsanity.com/paper/2506.08164/) (2025)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization](https://mlsanity.com/paper/2407.17823/) (2024)
- [A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints](https://mlsanity.com/paper/2007.15845/) (2020)
- [Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function](https://mlsanity.com/paper/2307.08245/) (2023)
- [Penalty-based Methods for Simple Bilevel Optimization under H"olderian Error Bounds](https://mlsanity.com/paper/2402.02155/) (2024)
- [Ghost Penalties in Nonconvex Constrained Optimization: Diminishing Stepsizes and Iteration Complexity](https://mlsanity.com/paper/1709.03384/) (2017)
- [Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization](https://mlsanity.com/paper/1705.07285/) (2017)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Achieving optimal complexity guarantees for a class of bilevel convex optimization problems](https://mlsanity.com/paper/2310.12247/) (2023)
- [Careful with that Scalpel: Improving Gradient Surgery with an EMA](https://mlsanity.com/paper/2402.02998/) (2024)
- [Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method](https://mlsanity.com/paper/2402.05415/) (2024)
- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)
- [CB2O: Consensus-Based Bi-Level Optimization](https://mlsanity.com/paper/2411.13394/) (2024)
- [A Projection-Free Method for Solving Convex Bilevel Optimization Problems](https://mlsanity.com/paper/2311.09738/) (2023)
- [Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems](https://mlsanity.com/paper/2409.06530/) (2024)

## Built on by (most cited first, 2 of 2)

- [Selective Ambulance Dispatch Under Contextual Travel-Time Uncertainty](https://mlsanity.com/paper/2605.23378/) (2026)
- [Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption](https://mlsanity.com/paper/2609.06580/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of solving a simple bilevel optimization problem, where the upper-level objective is minimized over the solution set of the lower-level problem. We focus on the general setting in which both the upper- and lower-level objectives are smooth but potentially nonconvex. Due to the absence of additional structural assumptions for the lower-level objective-such as convexity or the Polyak-Lojasiewicz (PL) condition-guaranteeing global optimality is generally intractable. Instead, we introduce a suitable notion of stationarity for this class of problems and aim to design a first-order algorithm that finds such stationary points in polynomial time. Intuitively, stationarity in this setting means the upper-level objective cannot be substantially improved locally without causing a larger deterioration in the lower-level objective. To this end, we show that a simple and implementable variant of the dynamic barrier gradient descent (DBGD) framework can effectively solve the considered nonconvex simple bilevel problems up to stationarity. Specifically, to reach an (εf, εg)-stationary point-where εf and εg denote the target stationarity accuracies for the upper- and lower-level objectives, respectively-the considered method achieves a complexity of Oleft(maxleft(εf^-frac3+p1+p, εg^-frac3+p2right)right), where p ≥ 0 is an arbitrary constant balancing the terms. To the best of our knowledge, this is the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in general nonconvex simple bilevel problems.