# Efficient Gradient Approximation Method for Constrained Bilevel Optimization

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 72 references that are in the map.
- First posted on arXiv 3 Feb 2023.

## 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)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Learning to Compare: Relation Network for Few-Shot Learning](https://mlsanity.com/paper/1711.06025/) (2017)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [TADAM: Task dependent adaptive metric for improved few-shot learning](https://mlsanity.com/paper/1805.10123/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (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)
- [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)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [Gradient Sampling Methods for Nonsmooth Optimization](https://mlsanity.com/paper/1804.11003/) (2018)

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

- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints](https://mlsanity.com/paper/2406.10148/) (2024)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [You Shall Pass: Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization](https://mlsanity.com/paper/2307.16304/) (2023)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024)
- [Meta-Reinforcement Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator](https://mlsanity.com/paper/2410.09728/) (2024)
- [Safe Gradient Flow for Bilevel Optimization](https://mlsanity.com/paper/2501.16520/) (2025)
- [Explainable reinforcement learning from human feedback to improve alignment](https://mlsanity.com/paper/2512.13837/) (2025)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [Riemannian Bilevel Optimization](https://mlsanity.com/paper/2405.15816/) (2024)
- [Double Momentum Method for Lower-Level Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.17386/) (2024)
- [A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2510.24710/) (2025)
- [Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning](https://mlsanity.com/paper/2602.00282/) (2026)
- [Interactive Inverse Reinforcement Learning of Interaction Scenarios via Bi-level Optimization](https://mlsanity.com/paper/2605.08131/) (2026)

## Abstract (arXiv)

Bilevel optimization has been developed for many machine learning tasks with large-scale and high-dimensional data. This paper considers a constrained bilevel optimization problem, where the lower-level optimization problem is convex with equality and inequality constraints and the upper-level optimization problem is non-convex. The overall objective function is non-convex and non-differentiable. To solve the problem, we develop a gradient-based approach, called gradient approximation method, which determines the descent direction by computing several representative gradients of the objective function inside a neighborhood of the current estimate. We show that the algorithm asymptotically converges to the set of Clarke stationary points, and demonstrate the efficacy of the algorithm by the experiments on hyperparameter optimization and meta-learning.