2025/03/25 by Maxime Bouscary, Jiawei Zhang, Bouscary, Maxime +3
Decision Sciences · Economics, Econometrics and Finance · #FOS: Mathematics #Housing Market and Economics #Optimization and Control (math.OC) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2503.19991
openalex publication_date 2025/03/25 · openalex created_date 2025/04/01 · openalex updated_date 2026/07/28
Contextual Stochastic Bilevel Optimization (CSBO) extends standard stochastic bilevel optimization (SBO) by incorporating context-dependent lower-level problems. CSBO problems are generally intractable since existing methods require solving a distinct lower-level problem for each sampled context, resulting in prohibitive sample and computational complexity, in addition to relying on impractical conditional sampling oracles. We propose a reduction framework that approximates the lower-level solutions using expressive basis functions, thereby decoupling the lower-level dependence on context and transforming CSBO into a standard SBO problem solvable using only joint samples from the context and noise distribution. First, we show that this reduction preserves hypergradient accuracy and yields an ε-stationary solution to CSBO. Then, we relate the sample complexity of the reduced problem to simple metrics of the basis. This establishes sufficient criteria for a basis to yield ε-stationary solutions with a near-optimal complexity of \widetildeO(ε-3), matching the best-known rate for standard SBO up to logarithmic factors. Moreover, we show that Chebyshev polynomials provide a concrete and efficient choice of basis that satisfies these criteria for a broad class of problems. Empirical results on inverse and hyperparameter optimization demonstrate that our approach outperforms CSBO baselines in convergence, sample efficiency, and memory usage.