AdaBiO: Stochastic Bilevel Optimization For Non-Convex Performative Risk

While stochastic bilevel optimization provides a framework for nested learning problems, most existing methods assume that the data distributions at both levels remain fixed throughout the optimization process. This assumption can fail in performative settings, where the deployed decisions change the environment and thereby affect future data distributions. We study stochastic bilevel optimization for nonconvex performative risk when both the upper-level (UL) and lower-level (LL) distributions are decision-dependent and unknown. Unlike existing bilevel performative methods that primarily target performatively stable points, our goal is to directly optimize the performative risk and find its stationary point. We propose AdaBiO, which iteratively estimates the two unknown distribution maps using explored samples. We prove that AdaBiO converges to an $ϵ$-stationary point with $\mathcal{O}({ϵ}^{-2})$ computational complexity and $\mathcal{O}({ϵ}^{-1})$ sample complexity. Experiments on strategic credit classification demonstrate that AdaBiO achieves lower performative risk than both non-performative stocBiO and a bilevel performatively stable point baseline. Moreover, its performance approaches that of AdaBiO with known distribution maps.