Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems
Abstract
Bilevel optimization has recently attracted growing attention, particularly in the development of efficient numerical methods. Despite substantial progress on optimistic bilevel optimization, pessimistic bilevel optimization (PBO) remains much less explored, especially the design of fully first-order, single-loop gradient-based methods. To address this gap, we propose a smooth approximation of PBO through reformulation, penalization and regularization, and establish convergence guarantees in terms of both minimizers and stationarity. Building on this framework, we then develop two single-loop algorithms for deterministic and stochastic PBOs, respectively. Both use only first-order gradient information and avoid second-order derivatives and inner-loop subproblem solves. Non-asymptotic convergence rates for the proposed algorithms are established to provide theoretical guarantees. Through a systematic empirical study of both synthetic and practical problem instances, we demonstrate that our algorithms are highly effective and efficient. In particular, our results on spam classification and Smart Predict-then-Optimize further illustrate PBO's advantages over its classical optimistic bilevel counterpart, highlighting its strong potential for practical modeling and the delivery of robust solutions.
Related
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- A true single-level reformulation for pessimistic bilevel optimization
- Benchmarking Bilevel Derivative-Free Optimization Algorithms
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?
BibTeX
@misc{cao2026singleloop,
title = {{Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems}},
author = {Qichao Cao and Bo Zeng and Shangzhi Zeng and Jin Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11183},
eprint = {2609.11183},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11183},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Single-Loop Gradient Algorithms for Pessimistic Bilevel Optimization Problems
AU - Qichao Cao
AU - Bo Zeng
AU - Shangzhi Zeng
AU - Jin Zhang
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11183
UR - https://arxiv.org/abs/2609.11183
AB - Bilevel optimization has recently attracted growing attention, particularly in the development of efficient numerical methods. Despite substantial progress on optimistic bilevel optimization, pessimistic bilevel optimization (PBO) remains much less explored, especially the design of fully first-order, single-loop gradient-based methods. To address this gap, we propose a smooth approximation of PBO through reformulation, penalization and regularization, and establish convergence guarantees in terms of both minimizers and stationarity. Building on this framework, we then develop two single-loop algorithms for deterministic and stochastic PBOs, respectively. Both use only first-order gradient information and avoid second-order derivatives and inner-loop subproblem solves. Non-asymptotic convergence rates for the proposed algorithms are established to provide theoretical guarantees. Through a systematic empirical study of both synthetic and practical problem instances, we demonstrate that our algorithms are highly effective and efficient. In particular, our results on spam classification and Smart Predict-then-Optimize further illustrate PBO's advantages over its classical optimistic bilevel counterpart, highlighting its strong potential for practical modeling and the delivery of robust solutions.
ER -