A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization

Jul 16, 2026

Upload by Jiven

Bilevel optimization targets hierarchical learning problems in which upper-level decisions depend on lower-level optima. The paper introduces PnPBO, a plug-and-play single-loop framework for stochastic bilevel optimization that unifies unbiased and biased stochastic estimators. Different estimators for distinct variables can be added independently, and a moving-average correction is used with an unbiased upper-level estimator. A unified convergence and complexity theory shows optimal sample complexity, matching known lower bounds in the finite-sum case. Experiments on benchmarks confirm the theoretical guarantees.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages40

Reading Time1 h 41 min

Abstract

Introduction

Problem formulation and hypergradient

Challenges and prior approaches

Contributions and framework overview

arXiv :2505 .01258v2 [math .OC] 12 Jul 2026 A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization ∗ Tianshu Chu† Dachuan Xu‡ Wei Yao§ Chengming Yu¶ Jin Zhang ‖ Abstract Bilevel optimization has recently attracted significant attention in machine learning due to its wide range of applications and advanced hierarchical optimization capabilities. In this paper, we propose a plug-and-play framework, named PnPBO, for developing and analyzing stochastic bilevel optimization methods. This framework integrates both modern unbiased and biased stochastic estimators into the single-loop bilevel optimization framework introduced in [9], with several improvements. In the implementation of PnPBO, all stochastic estimators for different variables can be independently incorporated, and an additional moving average technique is applied when using an unbiased estimator for the upper-level variable. In the theoretical analysis, we provide a unified convergence and complexity analysis for PnPBO, demonstrating that the adaptation of various stochastic estimators (including PAGE, ZeroSARAH, and mixed strategies) within the PnPBO framework achieves optimal sample complexity. Specifically, in the finite-sum setting, the resulting complexity matches the lower bound in [10] and is comparable to that of single-level optimization [49] . This resolves the open question of whether the optimal complexity bounds for solving bilevel optimization are identical to those for single-level optimization. Finally, we empirically validate our framework, demonstrating its effectiveness on several benchmark problems and confirming our theoretical findings. Keywords: bilevel optimization, stochastic optimization, plug-and-play, sample complexity 1 Introduction Bilevel optimization (BLO) effectively addresses challenges arising from hierarchical optimization, where the decision variables in the upper level are also involved in the lower level. In recent years, BLO has gained increasing attention due to its extensive and effective applications, including hyperparameter optimization [13], meta-learning [21], continual learning [17], and reinforcement learning [40] . ∗ This work was partially presented at International Conference on Machine Learning (ICML) 2024 ([7]) . †Institute of Operations Research and Information Engineering, Beijing University of Technology; National Center for Applied Mathematics Shenzhen; [chuts@emails.bjut.edu.cn](chuts@emails.bjut.edu.cn) ‡Institute of Operations Research and Information Engineering, Beijing University of Technology; [xudc@bjut.edu.cn](xudc@bjut.edu.cn) § National Center for Applied Mathematics Shenzhen, and Department of Mathematics, Southern University of Science and Technology; [yaow@sustech.edu.cn](yaow@sustech.edu.cn) ¶ School of Science, Beijing University of Posts and Telecommunications; National Center for Applied Mathematics Shenzhen; [yucm@bupt.edu.cn](yucm@bupt.edu.cn) ‖Department of Mathematics, and National Center for Applied Mathematics Shenzhen, Southern University of Science and Technology; [zhangj9@sustech.edu.cn](zhangj9@sustech.edu.cn) In this paper, we focus on the nonconvex-strongly-convex BLO problem under classical assumptions, formulated as follows min H (x) := f(x, y∗ (x)) s.t. y ∗ (x) := arg min g (x, y), (1) x∈Rdx y∈Rdy where H (x) denotes the total objective function, also referred to as the value function [9, 10 , 6] . The upper-level (UL) objective f(x, y) is Lf-smooth and possibly nonconvex. The lower-level (LL) objective g(x, y) is Lg1-smooth and strongly convex in y, and its gradient ∇g is Lg2-smooth. As is the case in many applications of interest in machine learning [38], the UL and LL objective functions take the finite-sum form f (x, y) = 1n Xi1 Fi (x, y) , g (x, y) = 1m Gj (x, y) . (2) A widely used and effective strategy for solving the BLO problem in (1) involves using implicit differentiation [35 , 32 , 33 , 29], which lea

FAQs

What does the proposed PnPBO framework do in stochastic bilevel optimization?

PnPBO is a plug-and-play single-loop framework that integrates unbiased and biased stochastic estimators to develop and analyze stochastic bilevel optimization methods.

How are stochastic estimators incorporated in PnPBO?

Stochastic estimators for different variables can be independently integrated, and an additional moving-average technique is applied when using an unbiased estimator for the upper-level variable.

What does the paper prove about convergence and sample complexity?

The analysis provides a unified convergence and complexity result showing that adapting estimators such as PAGE, ZeroSARAH, and mixed strategies inside PnPBO achieves optimal sample complexity, matching lower bounds in the finite-sum setting and comparing favorably to single-level optimization.

Jul 16, 2026

Upload by Jiven