# Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 51 references that are in the map.
- First posted on arXiv 24 Nov 2025.

## Builds on (most cited first, 30 of 37)

- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [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)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Reviving and Improving Recurrent Back-Propagation](https://mlsanity.com/paper/1803.06396/) (2018)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [First-order penalty methods for bilevel optimization](https://mlsanity.com/paper/2301.01716/) (2023)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Non-Convex Bilevel Games with Critical Point Selection Maps](https://mlsanity.com/paper/2207.04888/) (2022)
- [Achieving Linear Speedup in Non-IID Federated Bilevel Learning](https://mlsanity.com/paper/2302.05412/) (2023)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (2023)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)

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

- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2609.30877/) (2026)
- [Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization](https://mlsanity.com/paper/2610.01662/) (2026)

## Abstract (arXiv)

Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure. In this work, we focus on the smooth nonconvex-strongly-convex setting and develop new hard instances that yield nontrivial lower bounds under deterministic and stochastic first-order oracle models. In the deterministic case, we prove that any first-order zero-respecting algorithm requires at least Omega(kappa3/2ε-2) oracle calls to find an ε-accurate stationary point, improving the optimal lower bounds known for single-level nonconvex optimization and for nonconvex-strongly-convex min-max problems. In the stochastic case, we show that at least Omega(kappa5/2ε-4) stochastic oracle calls are necessary, again strengthening the best known bounds in related settings. Our results expose substantial gaps between current upper and lower bounds for bilevel optimization and suggest that even simplified regimes, such as those with quadratic lower-level objectives, warrant further investigation toward understanding the optimal complexity of bilevel optimization under standard first-order oracles.