acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 . Inverse-probability weighting corrects the shared-state bias up to finite-solve error, with controlling a computation–variance trade-off. For smooth CSBO with strongly convex unconstrained lower-level problems, the raw-update variant reaches in outer iterations for fixed with accuracy-dependent refinement. Its first- and second-order oracle complexities are and ; the total bound improves to 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.

Primary area:
optimization
Keywords:
CSBO, single-loop method, nonconvergence, randomized correction, meta-learning, ETO

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_oi4xOpenReview ↗
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 pp, using context-dependent inner solves. It reaches an ϵ\epsilon-stationary point with O~(ϵ−6)\tilde{O}(\epsilon^{-6}) first-order and O~(ϵ−4)\tilde{O}(\epsilon^{-4}) 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 λ=2\lambda = 2 be too large for the meta-learning experiment and make y⋆(x;ξ)≃xy^\star(x; \xi) \simeq x for all ξ\xi? This could explain why the uncorrected SL performs comparably to RCSL-GA. Did you try running the experiment with other values of λ\lambda?
  • 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?
Reviewer_qLdKOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies why directly extending single-loop stochastic bilevel optimization (SBO) methods to contextual stochastic bilevel optimization (CSBO) can fail. It shows that shared-state methods may optimize a surrogate objective rather than the original CSBO objective and provide a counterexample demonstrating this structural bias. To overcome this limitation, the authors propose RCSL-GA, which uses randomized contextual corrections to reduce computational costs. They establish convergence guarantees and demonstrate empirical improvements on synthetic and real-world benchmarks.

Critical strengths
  1. The paper identifies a limitation of directly applying single-loop methods to CSBO, supported by theoretical analysis and a clear counterexample.
  2. The proposed randomized correction mechanism is intuitive and provides a flexible trade-off between computational cost and estimator variance.
  3. The theoretical analysis establishes convergence guarantees and explicit oracle complexity bounds.
  4. Experiments across multiple applications demonstrate the effectiveness of RCSL-GA, particularly in terms of wall-clock efficiency.
Critical weaknesses
  1. Despite being described as a single-loop method, RCSL-GA still requires multiple context-specific inner iterations when corrections are activated, potentially limiting its computational advantages.
  2. The overall oracle complexity does not improve upon existing methods in the general stochastic setting. The theoretical computational advantages are primarily established through per-iteration comparisons rather than total complexity at matched accuracy.
  3. The convergence guarantees only cover the raw-update variant, while the experiments use direction averaging. This creates a gap between the theoretical analysis and empirical implementation.
  4. The experimental evaluation is somewhat limited. The meta-learning experiments use fixed pretrained features and only ten tasks, while the power-scheduling problem falls outside the theoretical assumptions.
  5. The substantial performance gap between RCSL-GA and Hessian-RT-MLMC in the meta-learning experiments raises questions about baseline tuning and comparison fairness.
Questions for authors
  1. Can the convergence guarantees be extended to the direction-averaged variant used in the experiments?
  2. Can the authors provide a total computational complexity comparison with existing CSBO methods under the same stationarity criterion?
  3. How sensitive is the proposed method to the correction probability pp, and can an adaptive strategy improve the computation–variance trade-off?
  4. Why does Hessian-RT-MLMC perform significantly worse than the other methods in the meta-learning experiments? Could this be related to hyperparameter selection?
Reviewer_Ze6gOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studied a single loop contextual stochastic bilevel method and showed that if we use one shared state, the algorithm cannot converge to the stationary solution of the actual problem. Based on this finding, they introduced a random context-aware correction algorithm with probability weighted correction, and established its convergence rate. Experiments on three tasks validate the effectiveness of their algorithm.

Critical strengths
  1. The counterexample shown in this paper is interesting and showcased an important mismatch in contextual stochastic bilevel optimization when we use a shared state that does not depend on the context, which is different from non-contextual bilevel optimization.

  2. The proposed method is well-motivated and has theoretical guarantee.

Critical weaknesses
  1. The major weakness for this paper is that it is hard to read, including many unnecessary notations and narrations. For example, the notations Hξ(x,y):=∇222Gξ(x,y),Aξ(x,y):=∇122Gξ(x,y)H_{\xi}(x, y):=\nabla_{22}^2 G_{\xi}(x, y), A_{\xi}(x, y):=\nabla_{12}^2 G_{\xi}(x, y) are almost the same length which can be omitted, while the g^y,t,H^t,b^t,f^x,t,A^t\widehat{g}_{y, t}, \widehat{H}_t, \widehat{b}_t, \widehat{f}_{x, t}, \widehat{A}_t are not clearly defined. In addition, in line 343-344, the sentence “it is not a last-iterate or fixed-inner-accuracy result, and it does not cover direction-averaged or Adam-type outer updates” is unnecessary because the convergence of Adam itself is hard to establish even for the single-level optimization, so such a result is not expected within the current scope of the paper.

These presentation issues make the main contributions of each theorem and the whole paper unclear and obscure.

  1. Another issue is that the paper seems to overstate the scope of its negative results for single-loop methods. Theorem 2 does not establish a negative result for general single-loop algorithms. Instead, it identifies a special class of single-loop algorithms without context-dependent states, but this is not the only way to extend single-loop methods to contextual bilevel optimization.

  2. The established convergence rate is the same as the existing work [Hu et al, NeurIPS 2023]. Table 1 shows that per-iteration complexity of the proposed method can be lower under certain conditions, but does not show that the proposed method reaches the same accuracy with less total iterations.

  3. The experimental presentation is not clear and the comparisons with prior works are incomplete. For example, in Figure 2, the line colors for different methods are too close, which is hard to distinguish whether the proposed method outperforms or not. Moreover, it lacks of comparisons with double loop approach, especially for the total iteration complexity.

Questions for authors

Can the authors provide the conditions that can make the structural bias in Theorem 1 vanishes? This could help to see whether the proposed method solve that issue.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.