# Overcoming Lower-Level Constraints in Bilevel Optimization: A Novel Approach with Regularized Gap Functions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2024.

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

- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints](https://mlsanity.com/paper/2406.10148/) (2024)
- [A First-order Generative Bilevel Optimization Framework for Diffusion Models](https://mlsanity.com/paper/2502.08808/) (2025)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [Solving bilevel optimization via sequential minimax optimization](https://mlsanity.com/paper/2511.07398/) (2025)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2505.01258/) (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)
- [Learning with Bilevel-Minimax Optimization for Efficient and Reliable Transfer Attacks](https://mlsanity.com/paper/2608.11815/) (2026)
- [Anchoring Adversarial Trajectories to Data Manifolds: A Bilevel Transfer Optimization Framework](https://mlsanity.com/paper/2609.38991/) (2026)

## Abstract (arXiv)

Constrained bilevel optimization tackles nested structures present in constrained learning tasks like constrained meta-learning, adversarial learning, and distributed bilevel optimization. However, existing bilevel optimization methods mostly are typically restricted to specific constraint settings, such as linear lower-level constraints. In this work, we overcome this limitation and develop a new single-loop, Hessian-free constrained bilevel algorithm capable of handling more general lower-level constraints. We achieve this by employing a doubly regularized gap function tailored to the constrained lower-level problem, transforming constrained bilevel optimization into an equivalent single-level optimization problem with a single smooth constraint. We rigorously establish the non-asymptotic convergence analysis of the proposed algorithm under the convexity of lower-level problem, avoiding the need for strong convexity assumptions on the lower-level objective or coupling convexity assumptions on lower-level constraints found in existing literature. Additionally, the generality of our method allows for its extension to bilevel optimization with minimax lower-level problem. We evaluate the effectiveness and efficiency of our algorithm on various synthetic problems, typical hyperparameter learning tasks, and generative adversarial network.