Bilevel Optimization with Coupled Decision-Dependent Distributions

Abstract

Bilevel optimization has been very popular recently due to its generality of formulating a wide range of machine learning problems. For example, in meta-learning, the upper-level (UL) problem can provide a good initialization for the lower-level (LL) model that is used for adaptation. However, the decision variables may influence the data feature and outcomes, which has been studied as the phenomenon of performative prediction. In this work, we consider the state-dependent distributions in bilevel optimization, where the UL data distribution is dependent on the LL optimization variable while the LL data distribution is also dependent on the upper level decision variable. We first show the sufficient conditions for the existence of performative stable solutions in this class of bilevel problems. Then, we provide efficient stochastic algorithms to find the performative stable point with theoretical convergence rate analysis. In addition, we theoretically discuss the optimality of the obtained solutions. Multiple numerical experiments validate our theoretical analysis by testing the bilevel performative prediction algorithms and non-performative ones in applications of meta strategic learning problems.