# Bilevel Learning via Inexact Stochastic Gradient Descent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 50 references that are in the map.
- First posted on arXiv 10 Nov 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [JFB: Jacobian-Free Backpropagation for Implicit Networks](https://mlsanity.com/paper/2103.12803/) (2021)
- [Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategies](https://mlsanity.com/paper/2112.13835/) (2021)
- [A Neural-Network-Based Convex Regularizer for Inverse Problems](https://mlsanity.com/paper/2211.12461/) (2022)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Learning Weakly Convex Regularizers for Convergent Image-Reconstruction Algorithms](https://mlsanity.com/paper/2308.10542/) (2023)
- [One-step differentiation of iterative algorithms](https://mlsanity.com/paper/2305.13768/) (2023)
- [Meta-Learning to Improve Pre-Training](https://mlsanity.com/paper/2111.01754/) (2021)
- [SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models](https://mlsanity.com/paper/2106.00553/) (2021)
- [Automatic differentiation of nonsmooth iterative algorithms](https://mlsanity.com/paper/2206.00457/) (2022)
- [Learning the Sampling Pattern for MRI](https://mlsanity.com/paper/1906.08754/) (2019)
- [Insights into analysis operator learning: From patch-based sparse models to higher-order MRFs](https://mlsanity.com/paper/1401.2804/) (2014)
- [Automatic Differentiation of Some First-Order Methods in Parametric Optimization](https://mlsanity.com/paper/1910.05696/) (2019)
- [Techniques for Gradient Based Bilevel Optimization with Nonsmooth Lower Level Problems](https://mlsanity.com/paper/1602.07080/) (2016)
- [Analyzing Inexact Hypergradients for Bilevel Learning](https://mlsanity.com/paper/2301.04764/) (2023)
- [Inexact Derivative-Free Optimization for Bilevel Learning](https://mlsanity.com/paper/2006.12674/) (2020)
- [Linearly convergent bilevel optimization with single-step inner methods](https://mlsanity.com/paper/2205.04862/) (2022)
- [Deep Equilibrium models for Poisson Imaging Inverse problems via Mirror Descent](https://mlsanity.com/paper/2507.11461/) (2025)
- [An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learning](https://mlsanity.com/paper/2308.10098/) (2023)
- [A simplified convergence theory for Byzantine resilient stochastic gradient descent](https://mlsanity.com/paper/2208.11879/) (2022)
- [TomoSelfDEQ: Self-Supervised Deep Equilibrium Learning for Sparse-Angle CT Reconstruction](https://mlsanity.com/paper/2502.21320/) (2025)

## Abstract (arXiv)

Bilevel optimization is a central tool in machine learning for high-dimensional hyperparameter tuning. Its applications are vast; for instance, in imaging it can be used for learning data-adaptive regularizers and optimizing forward operators in variational regularization. These problems are large in many ways: a lot of data is usually available to train a large number of parameters, calling for stochastic gradient-based algorithms. However, exact gradients with respect to parameters (so-called hypergradients) are not available, and their precision is usually linearly related to computational cost. Hence, algorithms must solve the problem efficiently without unnecessary precision. The design of such methods is still not fully understood, especially regarding how accuracy requirements and step size schedules affect theoretical guarantees and practical performance. Existing approaches introduce stochasticity at both the upper level (e.g., in sampling or mini-batch estimates) and the lower level (e.g., in solving the inner problem) to improve generalization, but they typically fix the number of lower-level iterations, which conflicts with asymptotic convergence assumptions. In this work, we advance the theory of inexact stochastic bilevel optimization. We prove convergence and establish rates under decaying accuracy and step size schedules, showing that with optimal configurations convergence occurs at an O(k-1/4) rate in expectation. Experiments on image denoising and inpainting with convex ridge regularizers and input-convex networks confirm our analysis: decreasing step sizes improve stability, accuracy scheduling is more critical than step size strategy, and adaptive preconditioning (e.g., Adam) further boosts performance. These results bridge theory and practice, providing convergence guarantees and practical guidance for large-scale imaging problems.