# Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 10 Sep 2024.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models](https://mlsanity.com/paper/2104.07788/) (2021)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints](https://mlsanity.com/paper/2007.15845/) (2020)
- [Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function](https://mlsanity.com/paper/2307.08245/) (2023)
- [Penalty-based Methods for Simple Bilevel Optimization under H"olderian Error Bounds](https://mlsanity.com/paper/2402.02155/) (2024)
- [An Iterative Regularized Incremental Projected Subgradient Method for a Class of Bilevel Optimization Problems](https://mlsanity.com/paper/1809.10050/) (2018)
- [Achieving optimal complexity guarantees for a class of bilevel convex optimization problems](https://mlsanity.com/paper/2310.12247/) (2023)
- [Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method](https://mlsanity.com/paper/2402.05415/) (2024)
- [ε-Subgradient Algorithms for Bilevel Convex Optimization](https://mlsanity.com/paper/1703.02648/) (2017)

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

- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)

## Abstract (arXiv)

This paper studies simple bilevel problems, where a convex upper-level function is minimized over the optimal solutions of a convex lower-level problem. We first show the fundamental difficulty of simple bilevel problems, that the approximate optimal value of such problems is not obtainable by first-order zero-respecting algorithms. Then we follow recent works to pursue the weak approximate solutions. For this goal, we propose a novel method by reformulating them into functionally constrained problems. Our method achieves near-optimal rates for both smooth and nonsmooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions.