acceptodds
Under review as a conference paper at ICLR 2027

A SINGLE-LOOP, CONSTANT-BATCH FIRST-ORDER PENALTY METHOD FOR STOCHASTIC BILEVEL OPTIMIZATION

Abstract

Recent advances in penalty-based methods for stochastic bilevel optimization (SBO) have eliminated the need for second-order derivative oracles. However, for stochastic nonconvex–strongly convex bilevel problems, existing first-order methods typically rely on nested loops and/or large batch sizes for attaining or sample complexity under standard bounded-variance assumption or mean-square smoothness assumption. Achieving these rates with a single-loop penalty method and a constant batch size remains challenging due to a large penalty value needed for an accurate approximation. To address this challenge, we develop a stochastic SIngle-loop COnstant-Batch first-order penalty method (SICO) that combines two complementary ingredients. First, it performs one stochastic-gradient update per-iteration for both the original lower-level and penalized problems, with a projection that controls the separation between their iterates. Second, it applies an exponential moving average to stabilize the upper-level gradient estimator. We show that this combination achieves sample complexity using only stochastic-gradient samples per iteration under unbiased, bounded-variance stochastic gradients. Under the additional mean-square smoothness assumption on the lower-level stochastic gradients, the same algorithm improves the complexity to also with batch size. To the best of our knowledge, this is the first work to match the best-known convergence rate for fully first-order SBO methods using a single loop and a constant batch size. This result addresses an open problem posed in the literature.

Primary area:
optimization
Keywords:
stochastic bilevel optimization, nonconvex-strongly convex bilevel optimization, first order optimization method

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_zX6ZOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes SICO, a fully first-order penalty method for nonconvex-strongly-convex stochastic bilevel optimization. Its main contribution is to combine projected coupling of the two lower-level trackers with an exponential-moving-average upper-level estimator. The resulting method is single-loop and uses a constant batch size, while attaining O(κ11ϵ−6)O(\kappa^{11}\epsilon^{-6}) under bounded variance and O(κ9ϵ−4)O(\kappa^9\epsilon^{-4}) under lower-level mean-square smoothness.

Critical strengths

The result addresses a meaningful gap in first-order stochastic bilevel optimization: prior methods attaining these ϵ\epsilon-rates require either nested loops or ϵ\epsilon-dependent batches. The algorithmic idea is simple and appealing, and the analysis of the coupled tracking error appears to be the main technical contribution. The experiments also include relevant first-order baselines and an ablation indicating that the projection is useful.

Critical weaknesses

I do not find any apparent weaknesses for the paper.

Questions for authors

What is the complexity in the deterministic setting? I wonder whether the method in this paper can remove the additional log factor in the existing upper bound.

Reviewer_9henOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

SICO uses one stochastic step for each of the two lower-level trackers, projects their separation, and smooths the upper update with an exponential moving average. The paper reports ϵ−6\epsilon^{-6} sample complexity under bounded variance and ϵ−4\epsilon^{-4} under lower-level mean-square smoothness, both with constant batch sizes, and tests two learning tasks.

Critical strengths
  1. The result targets a meaningful combination of requirements: ordinary gradients, a single loop, constant-size batches, and the stated best-known epsilon rates under each oracle assumption (Table 1 and Theorems 1-2). This is more specific than only improving an iteration count while increasing work per iteration.
  2. The projection controls the difference between the two trackers rather than assuming that all iterates are bounded. Combined with shared-sample gradient differences, this explains why lower-level mean-square smoothness removes the penalty factor from the upper estimator's variance (Equations 16-22 and Algorithm 1).
  3. The refined contraction explicitly includes the penalized-solution tracking error. Appendix D gives a simple deterministic counterexample to the uncoupled inequality discussed in Section 4.4, and Lemma 10 derives a corrected bound with a penalty-scaled error term. This is a useful technical clarification rather than only a new combination of update rules.
Critical weaknesses
  1. The hyper-cleaning metric does not establish useful cleaning by itself (major but fixable). Figure 1 reports only the average weight on corrupted samples. In my interpretation, assigning small weights to all samples could also improve this metric while harming learning. Add clean-sample weights, clean/corrupt separation, validation loss, and test accuracy, with a control that uses uniformly small weights.
  2. The experiments do not yet measure the main computational benefit (fixable). The methods use batch size 64 and a budget of 10,000 inner iterations, while nested methods use five inner updates per outer update. An inner iteration is not a common gradient-query unit across these algorithms. Report total stochastic-gradient evaluations, wall-clock time, and memory to the same accuracy; also compare small-batch SICO with larger-batch variants and appropriately tuned nested methods.
  3. Statistical and component evidence is limited (fixable). Figures 1-2 do not provide multi-seed uncertainty, and the component study removes projection but not the moving average. The reproducibility statement mentions fixed seeds without a multi-run protocol. Add paired repeats and a projection-by-momentum ablation, including a noisy setting that tests the stated stabilization mechanism rather than only final validation loss.
  4. The practical projection choice is not clearly tied to the theorem (fixable reproducibility gap). The analysis sets the radius to CfC_f divided by μg\mu_g times lambda, and also uses a warm-up condition, while the experiments tune the radius and multiplier separately. Appendix E gives extra search ranges but not the selected settings or warm-up details. Report the final radius, multiplier, momentum, initialization cost, and a practical rule for choosing the radius, distinguishing theorem-compatible choices from empirical variants.
Questions for authors

Please see weaknesses.

Reviewer_5iNCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic nonconvex–strongly convex bilevel optimization and proposes SICO, a single-loop, constant-batch, fully first-order penalty method.

The proposed algorithm builds on the penalty-based bilevel optimization framework and the projected lower-level coupling mechanism of Kwon et al. (2024). Specifically, the method maintains two sequences of lower-level iterates corresponding to the original and penalized lower-level problems. At each iteration, it projects the updated lower-level iterate ztz_t onto a ball of radius O(1/λ)O(1/\lambda) centered at the updated iterate yty_t. This projection helps control the difference between the two sequences. The algorithm further employs an exponential moving average to stabilize the upper-level gradient estimator.

The main theoretical contributions are improved oracle complexity guarantees using a single loop and constant batch size. Under the bounded-variance assumption, the proposed algorithm achieves O(κ11ϵ−6)O(\kappa^{11}\epsilon^{-6}) complexity, while under the additional mean-square smoothness (MSS) assumption, it achieves O(κ9ϵ−4)O(\kappa^9\epsilon^{-4}). These results match the best-known dependence on ϵ\epsilon for fully first-order penalty-based stochastic bilevel optimization methods while avoiding nested loops and large batch sizes.

The authors also provide numerical experiments on data hyper-cleaning and regularization selection, demonstrating promising empirical performance.

Critical strengths
  1. Improved convergence guarantees with a single-loop and constant-batch algorithm.

The main strength of this paper is its improved convergence analysis for fully first-order stochastic bilevel optimization. In particular, under the MSS assumption, the proposed algorithm improves the sample complexity from O(ϵ−5)O(\epsilon^{-5}), as achieved by previous single-loop constant-batch methods, to O(ϵ−4)O(\epsilon^{-4}). This is a meaningful theoretical improvement.

Without the MSS assumption, the improvement is not that significant compared to Chen et al. 2025. The improvement is the reduction in the batch size from O(κ)O(\kappa) to O(1)O(1).


  1. Simple algorithmic design supported by an interesting convergence analysis.

I appreciate the simplicity of the proposed algorithm. The main components are not entirely new, particularly the projection mechanism introduced by Kwon et al. (2024). However, the authors successfully integrate projected lower-level tracking into a single-loop stochastic algorithm and combine it with an exponential moving average of the upper-level gradient estimator.

The main technical contribution appears in Section 4.4, where the authors develop a refined analysis of the difference between the two lower-level iterates.

Critical weaknesses

A potential issue in the stochastic gradient variance analysis.

My primary technical concern is with Equation (22) and the corresponding analysis in Lemma 6. The conditional variance bound appears to overlook the randomness introduced by the stochastic updates of the lower-level variables yt+1y_{t+1} and zt+1z_{t+1}, which the conditional expectation Et\mathbb E_t may not have considered yet.

The randomness can come from the variables as well, and the authors may need to adopt some kind of Martingale analysis to make this work. I believe the proof is fixable though.

Questions for authors

Feedback: Please define s∗(wt)s^*(w_t) in the equation on top of Equation 20.

The rest please refer to the weakness part.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.