When Single-Loop Methods Fail: Randomized Correction for Contextual Stochastic Bilevel Optimization

Directly extending single-loop stochastic bilevel methods to contextual stochastic bilevel optimization (CSBO) may optimize a different objective. We characterize the averaged surrogate induced by shared-state transfers and give a smooth counterexample where surrogate stationarity vanishes while the CSBO stationarity error remains nonzero. We then propose randomly corrected single-loop gradient averaging (RCSL-GA), which retains cheap shared-state updates and invokes contextual refinement with probability $p$. Inverse-probability weighting corrects the shared-state bias up to finite-solve error, with $p$ controlling a computation–variance trade-off. For smooth CSBO with strongly convex unconstrained lower-level problems, the raw-update variant reaches $\mathbb{E}\Vert \nabla F(\hat{x}){\Vert }^2\le {ϵ}^2$ in $\mathcal{O}({ϵ}^{-4})$ outer iterations for fixed $p>0$ with accuracy-dependent refinement. Its first- and second-order oracle complexities are $\tilde{\mathcal{O}}({ϵ}^{-6})$ and $\tilde{\mathcal{O}}({ϵ}^{-4})$; the total bound improves to $\tilde{\mathcal{O}}({ϵ}^{-4})$ when conditional lower-gradient noise vanishes. We also identify when infrequent correction lowers expected per-iteration cost relative to double-loop methods. Experiments on a structural-bias example, Tiny-ImageNet meta-learning, and a task-aggregated power-scheduling surrogate show favorable solution quality and wall-clock gains, with infrequent correction on Tiny-ImageNet nearly matching correction at every iteration at substantially lower cost.