# Achieving optimal complexity guarantees for a class of bilevel convex optimization problems

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

## Key facts

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

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

- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)
- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)
- [Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems](https://mlsanity.com/paper/2409.06530/) (2024)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)

## Abstract (arXiv)

We design and analyze a novel accelerated gradient-based algorithm for a class of bilevel optimization problems. These problems have various applications arising from machine learning and image processing, where optimal solutions of the two levels are interdependent. That is, achieving the optimal solution of an upper-level problem depends on the solution set of a lower-level optimization problem. We significantly improve existing iteration complexity to O(ε-0.5) for both suboptimality and infeasibility error metrics, where ε>0 denotes an arbitrary scalar. In addition, contrary to existing methods that require solving the optimization problem sequentially (initially solving an optimization problem to approximate the solution of the lower-level problem followed by a second algorithm), our algorithm concurrently solves the optimization problem. To the best of our knowledge, the proposed algorithm has the fastest known iteration complexity, which matches the optimal complexity for single-level optimization. We conduct numerical experiments on sparse linear regression problems to demonstrate the efficacy of our approach.