# Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 67 references that are in the map.
- First posted on arXiv 1 Oct 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks](https://mlsanity.com/paper/1312.6211/) (2013)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions](https://mlsanity.com/paper/2006.02903/) (2020)
- [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)
- [Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations](https://mlsanity.com/paper/1710.10121/) (2017)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [Practical Gauss-Newton Optimisation for Deep Learning](https://mlsanity.com/paper/1706.03662/) (2017)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning](https://mlsanity.com/paper/1907.04472/) (2019)
- [On the Promise of the Stochastic Generalized Gauss-Newton Method for Training DNNs](https://mlsanity.com/paper/2006.02409/) (2020)
- [Constrained Optimization to Train Neural Networks on Critical and Under-Represented Classes](https://mlsanity.com/paper/2102.12894/) (2021)
- [Learning to Defend by Learning to Attack](https://mlsanity.com/paper/1811.01213/) (2018)
- [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018)
- [Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective](https://mlsanity.com/paper/2105.01696/) (2021)
- [Bilevel Continual Learning](https://mlsanity.com/paper/2007.15553/) (2020)
- [A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization](https://mlsanity.com/paper/2104.09003/) (2021)
- [Stabilizing Bi-Level Hyperparameter Optimization using Moreau-Yosida Regularization](https://mlsanity.com/paper/2007.13322/) (2020)

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

- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [qNBO: quasi-Newton Meets Bilevel Optimization](https://mlsanity.com/paper/2502.01076/) (2025)
- [A stochastic gradient method for trilevel optimization](https://mlsanity.com/paper/2505.06805/) (2025)
- [SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization](https://mlsanity.com/paper/2608.23211/) (2026)
- [Convex and Bilevel Optimization for Neuro-Symbolic Inference and Learning](https://mlsanity.com/paper/2401.09651/) (2024)
- [Efficient Bilevel Optimization with KFAC-Based Hypergradients](https://mlsanity.com/paper/2603.29108/) (2026)
- [Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization](https://mlsanity.com/paper/2606.22433/) (2026)
- [Designing Compact Neural Architectures via Neuron Gating and Mixed Activation](https://mlsanity.com/paper/2608.14443/) (2026)
- [LP-NAS: Linear Programming-based Neural Architecture Search](https://mlsanity.com/paper/2608.14472/) (2026)

## Abstract (arXiv)

Two-level stochastic optimization formulations have become instrumental in a number of machine learning contexts such as continual learning, neural architecture search, adversarial learning, and hyperparameter tuning. Practical stochastic bilevel optimization problems become challenging in optimization or learning scenarios where the number of variables is high or there are constraints. In this paper, we introduce a bilevel stochastic gradient method for bilevel problems with nonlinear and possibly nonconvex lower-level constraints. We also present a comprehensive convergence theory that addresses both the lower-level unconstrained and constrained cases and covers all inexact calculations of the adjoint gradient (also called hypergradient), such as the inexact solution of the lower-level problem, inexact computation of the adjoint formula (due to the inexact solution of the adjoint equation or use of a truncated Neumann series), and noisy estimates of the gradients, Hessians, and Jacobians involved. To promote the use of bilevel optimization in large-scale learning, we have developed new low-rank practical bilevel stochastic gradient methods (BSG-N-FD and~BSG-1) that do not require second-order derivatives and, in the lower-level unconstrained case, dismiss any matrix-vector products.