Fully First-Order Methods for Contextual Stochastic Bilevel Optimization

Contextual stochastic bilevel optimization (CSBO) is a new paradigm for decision making under uncertainty. It generalizes stochastic bilevel optimization (SBO) by integrating contextual information in the lower-level optimization problem and thus offers a stronger modeling capability. Nevertheless, owing to its semi-infinite nature, CSBO is extremely challenging from a computational perspective, hindering its real-world applications. Indeed, many algorithms designed for SBO are not applicable to CSBO. In this paper, we propose a double-loop fully first-order algorithm for solving CSBO and prove that both expected sample and gradient complexities of the algorithm are $\tilde{\mathcal{O}}({ϵ}^{-6})$. To tackle the increasing number of inner-loop iterations, we further develop an accelerated version of our algorithm using the random truncated multilevel Monte Carlo technique and an adaptive stepsize for empirical stabilization. The accelerated algorithm enjoys the improved expected complexities of $\tilde{\mathcal{O}}({ϵ}^{-4})$. These sample and gradient complexity orders match those of the corresponding Hessian-based algorithms for CSBO, while our algorithms use only first-order derivatives of $g$. Numerical experiments on meta-learning and a contextual electricity pricing problem demonstrate the superiority of the proposed algorithms over existing Hessian-based and reduction-based algorithms in terms of both speed and solution quality.