# An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 12 Feb 2024.

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

- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (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)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [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)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [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 inertial extrapolation method for convex simple bilevel optimization](https://mlsanity.com/paper/1809.06250/) (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)
- [On a decomposition formula for the proximal operator of the sum of two convex functions](https://mlsanity.com/paper/1707.08509/) (2017)
- [Projecting onto the intersection of a cone and a sphere](https://mlsanity.com/paper/1708.00585/) (2017)

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

- [On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization](https://mlsanity.com/paper/2507.23155/) (2025)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [Hierarchical Zero-Order Optimization for Deep Neural Networks](https://mlsanity.com/paper/2602.10607/) (2026)
- [Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption](https://mlsanity.com/paper/2609.06580/) (2026)

## Abstract (arXiv)

In this paper, we focus on simple bilevel optimization problems, where we minimize a convex smooth objective function over the optimal solution set of another convex smooth constrained optimization problem. We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem using a cutting plane approach and employs an accelerated gradient-based update to reduce the upper-level objective function over the approximated solution set. We measure the performance of our method in terms of suboptimality and infeasibility errors and provide non-asymptotic convergence guarantees for both error criteria. Specifically, when the feasible set is compact, we show that our method requires at most O(max1/√εf, 1/εg) iterations to find a solution that is εf-suboptimal and εg-infeasible. Moreover, under the additional assumption that the lower-level objective satisfies the r-th H"olderian error bound, we show that our method achieves an iteration complexity of O(maxεf^-frac2r-12r,εg^-frac2r-12r), which matches the optimal complexity of single-level convex constrained optimization when r=1.