# Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 17 Jul 2023.

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

- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization](https://mlsanity.com/paper/2104.09003/) (2021)
- [A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints](https://mlsanity.com/paper/2007.15845/) (2020)
- [An Iterative Regularized Incremental Projected Subgradient Method for a Class of Bilevel Optimization Problems](https://mlsanity.com/paper/1809.10050/) (2018)
- [An inertial extrapolation method for convex simple bilevel optimization](https://mlsanity.com/paper/1809.06250/) (2018)
- [Iterative regularization via dual diagonal descent](https://mlsanity.com/paper/1610.02170/) (2016)
- [ε-Subgradient Algorithms for Bilevel Convex Optimization](https://mlsanity.com/paper/1703.02648/) (2017)

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

- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization](https://mlsanity.com/paper/2402.08097/) (2024)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (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)
- [Stabilizing Deep Reconstruction Operators with Contractive Anchoring](https://mlsanity.com/paper/2607.23341/) (2026)

## Abstract (arXiv)

In this paper, we propose the Bi-Sub-Gradient (Bi-SG) method, which is a generalization of the classical sub-gradient method to the setting of convex bi-level optimization problems. This is a first-order method that is very easy to implement in the sense that it requires only a computation of the associated proximal mapping or a sub-gradient of the outer non-smooth objective function, in addition to a proximal gradient step on the inner optimization problem. We show, under very mild assumptions, that Bi-SG tackles bi-level optimization problems and achieves sub-linear rates both in terms of the inner and outer objective functions. Moreover, if the outer objective function is additionally strongly convex (still could be non-smooth), the outer rate can be improved to a linear rate. Last, we prove that the distance of the generated sequence to the set of optimal solutions of the bi-level problem converges to zero.