# On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 21 references that are in the map.
- First posted on arXiv 27 Feb 2026.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [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)
- [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)
- [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)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [MiLeNAS: Efficient Neural Architecture Search via Mixed-Level Reformulation](https://mlsanity.com/paper/2003.12238/) (2020)
- [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)
- [Beyond Value Functions: Single-Loop Bilevel Optimization under Flatness Conditions](https://mlsanity.com/paper/2507.20400/) (2025)

## Abstract (arXiv)

Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms, their theoretical understanding in the stochastic regime remains less developed than that of multi-loop methods. In this paper, we provide a refined convergence analysis of the Single-loop Stochastic Approximate Implicit Differentiation (SSAID) algorithm. Under the squared-gradient stationarity criterion |nablaPhi(x)|2≤ε, the corrected proof establishes an oracle complexity of O(kappa14ε-2), equivalently an averaged stationarity rate of O(kappa7K-1/2). The result preserves the canonical O(ε-2) dependence on the target accuracy while giving an explicit characterization of the condition-number dependence for stochastic AID-based single-loop methods.