# Contextual Stochastic Bilevel Optimization

arXiv: https://arxiv.org/abs/2310.18535 · HTML: https://mlsanity.com/paper/2310.18535/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Builds on (most cited first, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Personalized Federated Learning using Hypernetworks](https://mlsanity.com/paper/2103.04628/) (2021)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Hierarchically Structured Meta-learning](https://mlsanity.com/paper/1905.05301/) (2019)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence](https://mlsanity.com/paper/2202.12183/) (2022)
- [Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization](https://mlsanity.com/paper/1905.11957/) (2019)
- [Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization](https://mlsanity.com/paper/2305.18730/) (2023)
- [Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning](https://mlsanity.com/paper/2106.04911/) (2021)
- [Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization](https://mlsanity.com/paper/2206.01991/) (2022)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [End-to-End Learning for Stochastic Optimization: A Bayesian Perspective](https://mlsanity.com/paper/2306.04174/) (2023)
- [Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management](https://mlsanity.com/paper/2205.01774/) (2022)

## Built on by (most cited first, 14 of 14)

- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Multilevel neural simulation-based inference](https://mlsanity.com/paper/2506.06087/) (2025)
- [Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Sets](https://mlsanity.com/paper/2403.14822/) (2024)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Regularization for Adversarial Robust Learning](https://mlsanity.com/paper/2408.09672/) (2024)
- [Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization](https://mlsanity.com/paper/2503.22923/) (2025)
- [On the KL-Divergence-based Robust Satisficing Model](https://mlsanity.com/paper/2408.09157/) (2024)
- [Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints](https://mlsanity.com/paper/2511.09845/) (2025)
- [Quantum speedup of non-linear Monte Carlo problems](https://mlsanity.com/paper/2502.05094/) (2025)
- [Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization](https://mlsanity.com/paper/2606.22433/) (2026)
- [To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity](https://mlsanity.com/paper/2609.30501/) (2026)

## Abstract (arXiv)

We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This framework extends classical stochastic bilevel optimization when the lower-level decision maker responds optimally not only to the decision of the upper-level decision maker but also to some side information and when there are multiple or even infinite many followers. It captures important applications such as meta-learning, personalized federated learning, end-to-end learning, and Wasserstein distributionally robust optimization with side information (WDRO-SI). Due to the presence of contextual information, existing single-loop methods for classical stochastic bilevel optimization are unable to converge. To overcome this challenge, we introduce an efficient double-loop gradient method based on the Multilevel Monte-Carlo (MLMC) technique and establish its sample and computational complexities. When specialized to stochastic nonconvex optimization, our method matches existing lower bounds. For meta-learning, the complexity of our method does not depend on the number of tasks. Numerical experiments further validate our theoretical results.