# Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method

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

## Key facts

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

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

- [BLUR: A Bi-Level Optimization Approach for LLM Unlearning](https://mlsanity.com/paper/2506.08164/) (2025)
- [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)

## Abstract (arXiv)

This paper studies a class of simple bilevel optimization problems where we minimize a composite convex function at the upper-level subject to a composite convex lower-level problem. Existing methods either provide asymptotic guarantees for the upper-level objective or attain slow sublinear convergence rates. We propose a bisection algorithm to find a solution that is εf-optimal for the upper-level objective and εg-optimal for the lower-level objective. In each iteration, the binary search narrows the interval by assessing inequality system feasibility. Under mild conditions, the total operation complexity of our method is tilde Oleft(max√Lf1/εf,√Lg1/εg  right). Here, a unit operation can be a function evaluation, gradient evaluation, or the invocation of the proximal mapping, Lf1 and Lg1 are the Lipschitz constants of the upper- and lower-level objectives' smooth components, and tilde O hides logarithmic terms. Our approach achieves a near-optimal rate, matching the optimal rate in unconstrained smooth or composite convex optimization when disregarding logarithmic terms. Numerical experiments demonstrate the effectiveness of our method.