- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper considers contextual stochastic bilevel optimization (CSBO) problems, which are bilevel problems where the inner problem depends on a context . The authors adapt the penalty-based fully first-order approach to that regime. At each outer iteration, two inner loops are run, one on the inner problem and one on the inner problem perturbed by the outer function with weight , and their outputs are combined into a first-order estimate of the gradient of the bilevel objective with a bias in . They propose a vanilla algorithm with increasing provably reaching a complexity of . They also propose a variant that decreases the complexity to by leveraging the random truncated multilevel Monte Carlo technique, along with a level-dependent stepsize to stabilize it in practice. Experiments on meta-learning and contextual electricity pricing are provided.
Critical strengths
-
S1: This paper proposes the first fully first-order method to solve CSBO problems that handles general context distributions.
-
S2: The authors show a complexity in matching the complexities of the AID-based methods of [1]. The theoretical analysis is sound. Even though the proposed algorithms are an adaptation of the methods of [1] with the penalty-based estimator of [2], the analysis of this combination is not straightforward. The authors handle the variance amplification caused by the penalty parameter growing with the RT-MLMC level by directly controlling the coupled displacement of the two inner loops (Lemma A.9).
Critical weaknesses
None
Questions for authors
- Q1: How does the final complexity depend on the inner condition number?
2 comments
Thanks for the clarification.
Author Response to Reviewer 4gX2: Condition Number Dependence
We sincerely thank the reviewer for appreciating our work and for carefully examining how Lemma A.9 addresses the variance amplification caused by combining the penalty construction with RT-MLMC.
Question 1. How does complexity depend on the inner condition number?
Algorithm 2 matches the O(ϵ−4) expected sample and gradient complexity of Hessian-based CSBO methods using only first-order evaluations, for general context distributions. Let κg=ℓg,1/μg, with ℓg,1 and the remaining problem constants and damping parameters held fixed as μg varies. Proposition A.1 in the new Appendix A.11 establishes the following sufficient bound:
O(κg9ϵ−4[1+log(κg/ϵ)]2).
The improved condition-number dependence follows from a refined analysis of the coupled inner trajectories. By exploiting samplewise strong convexity and common-sample coupling, we obtain a uniform bound on their displacement. Combined with a two-regime analysis of the inner SGD error, this yields an O(κg6) coefficient in the multilevel correction's second-moment bound. The analysis also controls the bias introduced by the level-dependent stepsize. Together with the O(κg3) smoothness bound for the upper-level objective (Lemma A.4), these estimates lead to the stated κg9 dependence. The detailed proof is provided in Appendix A.11.
Recent lower bounds for non-contextual stochastic bilevel optimization give Ω(κy9/2ϵ−4) [1], Ω(κy8ϵ−6) [2], and Ω(κ10ϵ−6) [3], under their respective model assumptions.
The last two are concurrent preprints appearing around and after our submission. Note that their oracle and regularity assumptions differ from ours. Specifically, these two concurrent bounds use black-box stochastic gradients with a fresh sample per query. Our accelerated estimator uses sampled-function (white-box) access, evaluating the same conditional sample at multiple points under samplewise smoothness and strong convexity, with every gradient evaluation counted. Although CSBO includes non-contextual SBO as a special case, and context-dependent inner solutions may introduce additional difficulty, these black-box lower bounds do not apply to our algorithms.
Our algorithmic design and analysis prioritize achieving the accelerated rate O(ϵ−4) that is optimal with respect to the accuracy ϵ, in the sense that the exponent matches the SBO lower bound [4]. Deriving sharp lower bounds under our contextual and oracle assumptions and designing algorithms with optimal κg dependence remain open.
References
[1] L. Chen, K. Ji, and J. Zhang. On the Condition Number Dependency in Bilevel Optimization. arXiv:2511.22331v4, 2026.
[2] Z. Gu, Q. Wu, and J. Yang. An Ω(κy8ϵ−6) Lower Bound for Stochastic NC--SC Bilevel Optimization with First-order Oracles. arXiv:2609.21905, first posted 18 September 2026.
[3] H. Zhang et al. Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization. arXiv:2610.03633v2, first posted 2 October 2026.
[4] L. Chen, J. Li, E. M. Chayti, and J. Zhang. Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization. ICLR, 2026. Paper.
[5] Y. Hu, J. Wang, Y. Xie, A. Krause, and D. Kuhn. Contextual Stochastic Bilevel Optimization. Advances in Neural Information Processing Systems (NeurIPS), vol. 36, pp. 78412--78434, 2023.
[6] J. Kwon, D. Kwon, and H. Lyu. On the Complexity of First-Order Methods in Stochastic Bilevel Optimization. ICML, PMLR 235, pp. 25784--25811, 2024. Paper.