# An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 58 references that are in the map.
- First posted on arXiv 19 Aug 2023.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [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)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [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)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [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)
- [Learned convex regularizers for inverse problems](https://mlsanity.com/paper/2008.02839/) (2020)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [A Neural-Network-Based Convex Regularizer for Inverse Problems](https://mlsanity.com/paper/2211.12461/) (2022)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [Regularization by architecture: A deep prior approach for inverse problems](https://mlsanity.com/paper/1812.03889/) (2018)
- [SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models](https://mlsanity.com/paper/2106.00553/) (2021)
- [Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagation](https://mlsanity.com/paper/2205.03076/) (2022)
- [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)
- [Bilevel methods for image reconstruction](https://mlsanity.com/paper/2109.09610/) (2021)
- [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)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Accelerating Inexact HyperGradient Descent for Bilevel Optimization](https://mlsanity.com/paper/2307.00126/) (2023)
- [Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise](https://mlsanity.com/paper/1910.04055/) (2019)
- [Techniques for Gradient Based Bilevel Optimization with Nonsmooth Lower Level Problems](https://mlsanity.com/paper/1602.07080/) (2016)
- [A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization](https://mlsanity.com/paper/2104.09003/) (2021)
- [Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers](https://mlsanity.com/paper/1804.00154/) (2018)
- [Analyzing Inexact Hypergradients for Bilevel Learning](https://mlsanity.com/paper/2301.04764/) (2023)

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

- [Learning Regularization Functionals for Inverse Problems: A Comparative Study](https://mlsanity.com/paper/2510.01755/) (2025)
- [An Adaptively Inexact Method for Bilevel Learning Using Primal-Dual Style Differentiation](https://mlsanity.com/paper/2412.06436/) (2024)
- [Bilevel Learning with Inexact Stochastic Gradients](https://mlsanity.com/paper/2412.12049/) (2024)
- [Bilevel Learning via Inexact Stochastic Gradient Descent](https://mlsanity.com/paper/2511.06774/) (2025)

## Abstract (arXiv)

Various tasks in data science are modeled utilizing the variational regularization approach, where manually selecting regularization parameters presents a challenge. The difficulty gets exacerbated when employing regularizers involving a large number of hyperparameters. To overcome this challenge, bilevel learning can be employed to learn such parameters from data. However, neither exact function values nor exact gradients with respect to the hyperparameters are attainable, necessitating methods that only rely on inexact evaluation of such quantities. State-of-the-art inexact gradient-based methods a priori select a sequence of the required accuracies and cannot identify an appropriate step size since the Lipschitz constant of the hypergradient is unknown. In this work, we propose an algorithm with backtracking line search that only relies on inexact function evaluations and hypergradients and show convergence to a stationary point. Furthermore, the proposed algorithm determines the required accuracy dynamically rather than manually selected before running it. Our numerical experiments demonstrate the efficiency and feasibility of our approach for hyperparameter estimation on a range of relevant problems in imaging and data science such as total variation and field of experts denoising and multinomial logistic regression. Particularly, the results show that the algorithm is robust to its own hyperparameters such as the initial accuracies and step size.