# On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 69 references that are in the map.
- First posted on arXiv 2 Jan 2023.

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

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)

## Built on by (most cited first, 30 of 39)

- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization](https://mlsanity.com/paper/2407.17823/) (2024)
- [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [A First-order Generative Bilevel Optimization Framework for Diffusion Models](https://mlsanity.com/paper/2502.08808/) (2025)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [A Framework for Bilevel Optimization on Riemannian Manifolds](https://mlsanity.com/paper/2402.03883/) (2024)
- [On The Global Convergence Of Online RLHF With Neural Parametrization](https://mlsanity.com/paper/2410.15610/) (2024)
- [Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization](https://mlsanity.com/paper/2503.22923/) (2025)
- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [BLISS: A Lightweight Bilevel Influence Scoring Method for Data Selection in Language Model Pretraining](https://mlsanity.com/paper/2510.06048/) (2025)
- [Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2511.19656/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024)
- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)
- [Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems](https://mlsanity.com/paper/2409.06530/) (2024)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints](https://mlsanity.com/paper/2511.09845/) (2025)
- [Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities](https://mlsanity.com/paper/2602.13510/) (2026)
- [Oracle-Robust Online Alignment for Large Language Models](https://mlsanity.com/paper/2602.20457/) (2026)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization](https://mlsanity.com/paper/2605.09094/) (2026)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [On the Convergence of Self-Improving Online LLM Alignment](https://mlsanity.com/paper/2606.31524/) (2026)
- [Balancing Multi-modal Sensor Learning via Multi-objective Optimization](https://mlsanity.com/paper/2511.06686/) (2025)
- [Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning](https://mlsanity.com/paper/2602.00282/) (2026)

## Abstract (arXiv)

Bilevel optimization reveals the inner structure of otherwise oblique optimization problems, such as hyperparameter tuning, neural architecture search, and meta-learning. A common goal in bilevel optimization is to minimize a hyper-objective that implicitly depends on the solution set of the lower-level function. Although this hyper-objective approach is widely used, its theoretical properties have not been thoroughly investigated in cases where the lower-level functions lack strong convexity. In this work, we first provide hardness results to show that the goal of finding stationary points of the hyper-objective for nonconvex-convex bilevel optimization can be intractable for zero-respecting algorithms. Then we study a class of tractable nonconvex-nonconvex bilevel problems when the lower-level function satisfies the Polyak-Lojasiewicz (PL) condition. We show a simple first-order algorithm can achieve better complexity bounds of tildeO(ε-2), tildeO(ε-4) and tildeO(ε-6) in the deterministic, partially stochastic, and fully stochastic setting respectively. The complexities in the first two cases are optimal up to logarithmic factors.