- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies the extension of stochastic bilevel optimization (SBO) methods to contextual SBO (CSBO), in which the lower-level solutions depend on a random context. The authors show that SBO algorithms that maintain a context-free lower-level solution and use only joint samples optimize an averaged surrogate problem, whose stationarity error can vanish while the CSBO stationarity error remains nonzero. The paper introduces RCSL-GA, which maintains a context-free lower-level solution but corrects its upper-level updates, with probability , using context-dependent inner solves. It reaches an -stationary point with first-order and second-order oracle calls. Experiments on two real-world tasks show lower or comparable objective values and shorter wall-clock times compared to existing CSBO methods that do not store context-dependent lower-level solutions.
Critical strengths
The paper clearly highlights why SBO algorithms are not directly amenable to solving CSBO problems, with an insightful example of a CSBO instance where, under joint sampling, SBO algorithms whose lower-level iterate is restricted to be context-free fail to reach CSBO stationarity. It also makes explicit the bias that extensions of SBO algorithms to CSBO need to correct.
The proposed randomized correction is novel and applicable to existing single-loop SBO algorithms, and shows significantly shorter wall-clock times compared to existing CSBO methods that do not store context-dependent lower-level solutions.
Critical weaknesses
The current experiments are not fully comprehensive or convincing. The two real-world problems involve a small number of contexts (10 tasks in meta-learning, 4 in power scheduling), for which methods with per-task states (e.g., the cited Guo et al. (2021)) are directly applicable and free of structural bias, but are not included in the benchmark. Additionally, while the experiments show a clear advantage of RCSL-GA over existing CSBO methods that do not store context-dependent lower-level solutions, the comparison with the uncorrected SL remains unclear, with Appendix G.2.5 showing a marginal improvement in objective value at the cost of much slower wall-clock convergence.
Questions for authors
- Could you compare your approach to methods with per-context lower-level solutions, such as Guo et al. (2021), on the two real-world problems?
- Wouldn't be too large for the meta-learning experiment and make for all ? This could explain why the uncorrected SL performs comparably to RCSL-GA. Did you try running the experiment with other values of ?
- The randomized correction is proposed for single-loop SBO algorithms. Is it restricted to such algorithms, or is it also applicable to double-loop SBO algorithms?