# First-Order Methods for Linearly Constrained Bilevel Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 97 references that are in the map.
- First posted on arXiv 18 Jun 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [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)
- [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)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [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)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [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)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [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)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [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)

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

- [CoBo: Collaborative Learning via Bilevel Optimization](https://mlsanity.com/paper/2409.05539/) (2024)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024)
- [Leveraging Machine Unlearning for Cost-Efficient Preference Alignment](https://mlsanity.com/paper/2504.06659/) (2025)
- [Safe Gradient Flow for Bilevel Optimization](https://mlsanity.com/paper/2501.16520/) (2025)
- [Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints](https://mlsanity.com/paper/2511.09845/) (2025)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques](https://mlsanity.com/paper/2509.13880/) (2025)
- [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)

## Abstract (arXiv)

Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained bilevel problems, the constrained setting remains relatively underexplored. We present first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear equality constraints, we attain ε-stationarity in widetildeO(ε-2) gradient oracle calls, which is nearly-optimal. For linear inequality constraints, we attain (δ,ε)-Goldstein stationarity in widetildeO(dδ-1 ε-3) gradient oracle calls, where d is the upper-level dimension. Finally, we obtain for the linear inequality setting dimension-free rates of widetildeO(δ-1 ε-4) oracle complexity under the additional assumption of oracle access to the optimal dual variable. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. We verify these guarantees with preliminary numerical experiments.