# Penalty-based Methods for Simple Bilevel Optimization under H"olderian Error Bounds

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

## Key facts

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

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

- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (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)
- [Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities](https://mlsanity.com/paper/2602.13510/) (2026)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [BiRQ: Bi-Level Self-Labeling Random Quantization for Self-Supervised Speech Recognition](https://mlsanity.com/paper/2509.15430/) (2025)

## Abstract (arXiv)

This paper investigates simple bilevel optimization problems where we minimize an upper-level objective over the optimal solution set of a convex lower-level objective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose a penalization framework that delineates the relationship between approximate solutions of the original problem and its reformulated counterparts. This framework accommodates varying assumptions regarding smoothness and convexity, enabling the application of specific methods with different complexity results. Specifically, when both upper- and lower-level objectives are composite convex functions, under an α-H"olderian error bound condition and certain mild assumptions, our algorithm attains an (ε,εβ)-optimal solution of the original problem for any β> 0 within Oleft(√1/ε^maxα,βright) iterations. The result can be improved further if the smooth part of the upper-level objective is strongly convex. We also establish complexity results when the upper- and lower-level objectives are general nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms.