Orateur
Description
We introduce contextual stochastic bilevel optimization (CSBO) - a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on contextual information and on the upper-level decision variable. We also assume that there may be multiple (or even infinitely many) followers at the lower level. CSBO encapsulates important applications such as meta-learning, personalized federated learning, end-to-end learning, and Wasserstein distributionally robust optimization with side information as special cases. Due to the contextual information at the lower level, existing single-loop methods for classical stochastic bilevel optimization are not applicable. We thus propose an efficient double-loop gradient method based on the Multilevel Monte-Carlo (MLMC) technique. When specialized to stochastic nonconvex optimization, the sample complexity of our method matches existing lower bounds. Our results also have important ramifications for three-stage stochastic optimization and challenge the long-standing belief that three-stage stochastic optimization is harder than classical two-stage stochastic optimization.
