# Sharper Analysis of Single-Loop Methods for Bilevel Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 34 references that are in the map.
- First posted on arXiv 11 Jul 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [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)
- [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)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selection](https://mlsanity.com/paper/2410.07471/) (2024)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [MiLeNAS: Efficient Neural Architecture Search via Mixed-Level Reformulation](https://mlsanity.com/paper/2003.12238/) (2020)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [Stability and Generalization of Bilevel Programming in Hyperparameter Optimization](https://mlsanity.com/paper/2106.04188/) (2021)
- [On the Global Optimality of Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2006.13182/) (2020)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Making Scalable Meta Learning Practical](https://mlsanity.com/paper/2310.05674/) (2023)
- [Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy](https://mlsanity.com/paper/2405.09927/) (2024)
- [Relational Experience Replay: Continual Learning by Adaptively Tuning Task-wise Relationship](https://mlsanity.com/paper/2112.15402/) (2021)
- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [qNBO: quasi-Newton Meets Bilevel Optimization](https://mlsanity.com/paper/2502.01076/) (2025)

## Abstract (arXiv)

Bilevel optimization underpins many machine learning applications, including hyperparameter optimization, meta-learning, neural architecture search, and reinforcement learning. While hypergradient-based methods have advanced significantly, a gap persists between theoretical guarantees and practical single-loop implementations required for efficiency. We bridge this gap by establishing sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods, leveraging our proposed analytical framework, decoupled norm analysis (DNA). For AID, we improve the convergence rate from O(kappa6/K) to O(kappa5/K), where kappa is the condition number of the inner-level problem. For ITD, we prove that the asymptotic error is O(kappa2), exactly matching the known lower bound and improving upon the previous O(kappa3) guarantee. Numerical experiments on synthetic and real tasks corroborate our theoretical findings.