- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper builds on BROS, which was recently accepted to NeurIPS 2026 in September, with its preprint publicly available on arXiv in May 2026.
The paper studies implicit-gradient methods for bilevel optimization under lower-level strong convexity and additional stochastic assumptions (e.g., predictable factors and initialization). Following BROS, it uses iterative auxiliary updates to approximate inverse-Hessian actions and estimates Hessian–vector products (HVPs) and Jacobian–vector products (JVPs) through randomized subspaces to reduce computational and memory costs.
The proposed method is an incremental extension of BROS, addressing three remaining limitations: (1) shared-projection bias, (2) the additional second-order query required for bias correction, and (3) the lack of history-adaptive sampling. It addresses these limitations by (C1) proposing a conditionally unbiased operator estimator under Assumption 3.3 and (C2) introducing history-aware subspace sampling. Under the stated assumptions, the method retains the single-loop iteration complexity of BROS.
The paper establishes convergence guarantees under its assumptions and provides experiments on several relatively small-scale tasks, along with a slightly larger data-mixture proxy, comparing against some baselines.
Critical strengths
-
Interesting estimator design. The use of independent input and output sketches provides a simple way to avoid the bias correction required by BROS, potentially reducing the computational cost of second-order operations.
-
History-aware sampling. Incorporating historical directions into randomized subspace sampling is a reasonable extension that may improve estimation efficiency when useful directions persist across iterations.
Critical weaknesses
-
Literature review is not comprehensive.
- Memory-efficient implicit-gradient methods extend beyond the cited ones. [1–3] are some examples I am aware of.
- The review of penalty methods is also incomplete. [4–8] are some relevant examples.
- Fully first-order methods are not sufficiently covered either, e.g., [9–10].
-
Strong assumptions:
- Lower-level strong convexity is a restrictive assumption. Recent methods have already considered relaxed assumptions. The large-scale problems motivating this paper often do not satisfy strong convexity.
- Assumption 3.3 appears rather restrictive and not sufficiently motivated. Some conditions seem to be introduced mainly to facilitate the proofs. Further justification of their practical validity is needed. Alternatively, the authors could provide an inductive argument showing that these conditions hold at each iteration under more standard initialization assumptions.
-
The paper introduces too much notation, some of which seems unnecessary. This significantly affects readability and makes the main ideas difficult to follow.
-
Limited experimental scale and baselines.
- Most experiments are relatively small-scale, and the comparisons with recent methods are limited.
- Several baselines are relatively old. For example, the Penalty baseline does not represent recent developments in penalty-based bilevel optimization, such as [4–8], or the F2SA, PBGD methods that are reviewed but not tested.
- The Pile experiments use archived configurations rather than a direct comparison of the complete proposed method with corrected BROS. This limits the strength of the empirical conclusions.
[1] Dong, Y., Yang, J., Yao, W., and Zhang, J. "Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization." ICML, 2025.
[2] Liao, D., Dangel, F., and Yu, Y. "Efficient Bilevel Optimization with KFAC-Based Hypergradients." AISTATS, 2026.
[3] Giovannelli, T., Kent, G. D., and Vicente, L. N. "Inexact Bilevel Stochastic Gradient Methods for Constrained and Unconstrained Lower-Level Problems." Journal of Global Optimization, 2025.
[4] Kwon, J., Kwon, D., Wright, S., and Nowak, R. "On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation." ICLR, 2024.
[5] Lu, Z., and Mei, S. "First-Order Penalty Methods for Bilevel Optimization." SIAM Journal on Optimization, 2024.
[6] Jiang, L., Xiao, Q., Chen, L., and Chen, T. "Beyond Value Functions: Single-Loop Bilevel Optimization under Flatness Conditions." NeurIPS, 2025.
[7] Zhang, S., Huang, X., and Huang, F. "Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level." ICML, 2025.
[8] Shen, W., Zhang, J., Huang, M., and Shen, C. "A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization." NeurIPS, 2025.
Questions for authors
-
Lower-level strong convexity and Assumption 3.3 appear too restrictive, particularly for large-scale applications. Why are such strong assumptions necessary, and how can they be justified in practical settings?
-
Why does the paper compare against an older Penalty method rather than more recent fully first-order methods such as F2SA?
-
What is the practical advantage of implicit-gradient methods for large-scale problems? Given that value-function penalty methods can approximate implicit hypergradients with error under suitable assumptions, why are they not compared in performance versus wall-clock time?
-
Why is the complete proposed method not evaluated on larger-scale problems with millions of trainable parameters? The Pile-280M experiment uses archived configurations rather than the full method.
5 comments
Response to Reviewer if44 (2/2)
Response to Reviewer if44 (2/2)
W3. Notation
We will streamline redundant notation and add a categorized table:
Table R3-1. Core notation (excerpt).
| Category | Symbols | Meaning |
|---|---|---|
| Problem/states | ; | Objectives; upper/lower-level states |
| Projections/history | ; | Total/historical/fresh ranks; factor/lifting operator |
| Derivatives/directions | Hessian/mixed-Jacobian operators | |
| Analysis | Past information; conditional expectation |
We will clarify that denotes low-dimensional derivatives/operators and lifted stochastic directions, linking Eqs. (6)–(8) to Algorithm 1.
W4-1/W4-3/Q4. Large-scale evaluation of the complete method
We add two large-scale evaluations. In both, OPR-BROS (History) enables History, Oja updates, and independent sampling of all five factors.
On Pile-280M, we use a GPT with 253.13M parameters and complete the comparison using seeds 42/43/44. All methods run for 10,000 steps under common settings. We report the final upper-level loss, per-step time, and loss-versus-wall-clock-time curves. Table R3-2 includes OPR-BROS (History) with all components, BROS (w correction), and the additional baselines.
Table R3-2. Pile-280M comparison with additional baselines. Loss is the worst-domain excess validation CE. Loss and time are reported as mean ± standard deviation.
| Method | Final upper-level loss ↓ | Per-step time (s) ↓ | Peak GPU memory (GiB) ↓ |
|---|---|---|---|
| OPR-BROS (History) | 3.1437 ± 0.0077 | 0.3543 ± 0.0009 | 56.04 |
| OPR-BROS (Fresh) | 3.1859 ± 0.0030 | 0.3520 ± 0.0011 | 56.04 |
| BROS (w correction) | 3.1525 ± 0.0132 | 1.7104 ± 0.0021 | 56.30 |
| Penalty | 3.5040 ± 0.0211 | 0.8967 ± 0.0002 | 61.58 |
| F²SA | 3.3927 ± 0.0023 | 0.5341 ± 0.0007 | 57.81 |
| V-PBGD | 3.2022 ± 0.0161 | 1.1383 ± 0.0020 | 54.03 |
We further evaluate OPR-BROS (History) with Adam on the approximately 500M-parameter Proxy task in the open-source DataFlex framework, with all model parameters participating in lower-level training. Final quality is measured by equally weighted domain CE on the fixed evaluation panel fixed7, where lower is better.
Table R3-3. DataFlex Proxy evaluation.
| Method | Actual training tokens | Final fixed7 CE ↓ | Actual runtime (h) | Peak GPU memory (GiB) |
|---|---|---|---|---|
| OPR-BROS (History) | 10.54B | 3.0873 | 66.16 | 85.14 |
| MA-SOBA | 12.04B | 2.7552 | 61.51 | 92.40 |
| DoReMi Proxy | 11.35B | 3.2671 | 66.56 | 88.01 |
The DataFlex results are single runs under each method's own training recipe. The DoReMi runtime includes both the reference-model and Proxy stages.
W4-2/Q2/Q3. Recent baselines and wall-clock comparisons
We add comparisons with F²SA and V-PBGD on CIFAR-10 and CIFAR-100. The two tasks use ResNet-18 and SmallViT, respectively. Within each task, all methods use the same data split, batch size, and GPU, and train for 6,000 steps. CIFAR-10 uses seed 42; CIFAR-100 uses seed 43. Average per-step time is computed by dividing the total training and validation time by 6,000; peak GPU memory is reported as allocated / reserved.
Table R3-4. CIFAR-10 and CIFAR-100 comparisons with additional baselines.
| Task | Method | Final validation CE ↓ | Average per-step time (s, including validation) ↓ | Peak GPU memory (GiB, allocated / reserved) ↓ |
|---|---|---|---|---|
| CIFAR-10 | OPR-BROS (History) | 1.3041 | 0.2535 | 0.849 / 0.973 |
| CIFAR-10 | F²SA | 1.8582 | 0.2161 | 1.000 / 1.080 |
| CIFAR-10 | V-PBGD | 1.3137 | 0.3155 | 0.875 / 0.934 |
| CIFAR-100 | OPR-BROS (History) | 2.2984 | 0.8746 | 4.918 / 5.127 |
| CIFAR-100 | F²SA | 2.4005 | 0.7612 | 5.061 / 5.303 |
| CIFAR-100 | V-PBGD | 2.3139 | 1.5565 | 5.157 / 5.463 |
The additional Pile-280M comparisons with F²SA and V-PBGD, with Penalty retained as a reference, are in Table R3-2. OPR-BROS (History) achieves a lower mean final loss than these three baselines. Its average per-step time is approximately 1.51× and 3.21× faster than F²SA and V-PBGD, respectively.
References
[1] Zhang, H., et al. "BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization." arXiv:2605.10288, 2026.
[2] Mehra, A., and Hamm, J. "Penalty Method for Inversion-Free Deep Bilevel Optimization." ACML, 2021.
[3] Kwon, J., et al. "A Fully First-Order Method for Stochastic Bilevel Optimization." ICML, 2023.
[4] Shen, H., and Chen, T. "On Penalty-Based Bilevel Gradient Descent Method." ICML, 2023.
[5] Liang, H., et al. "DataFlex: A Unified Framework for Data-Centric Dynamic Training of Large Language Models." arXiv:2603.26164, 2026.
[6] Chen, X., et al. "Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions." JMLR, 2024.
[7] Xie, S. M., et al. "DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretraining." NeurIPS, 2023.
Thank you for the detailed response and the updated experiments. My remaining question on the comprehensive comparison are:
-
Assumption 3.3: it indeed can be implemented by the algorithm, but my key concern is this assumption seems to be analysis inspired. Rather assumptions should be (sufficient) condition directly assumed on the problem setting rather on the trajectory of iteraiton.
-
Experimental Comparison: the updated comparison is more comprehensive and they are valuable. It would be important to include them in the revised manuscript. The current improve towards F2SA and V-PBGD, seems only marginal rather than as claimed in the paper to be a lot compared with "Penalty" method. Also, I would like to know the detailed hyperparermeters used in F2SA and V-PBGD, as otherwised not good hyperparameter choice would dampen their performance.
I would be happy to increase score if the author can provide clear evidence towards the remaining concern.
Response to Reviewer if44 (1/2)
Response to Reviewer if44 (1/2)
W1. Coverage of related work
Implicit gradients and resource efficiency. SOBA/SABA, MA-SOBA, and SPABA/PnPBO establish single-loop recursive frameworks for stochastic bilevel optimization (Dagréou et al., 2022; Chen et al., 2024; Chu et al., 2024; Chu et al., 2026). To reduce the cost of hypergradient computation, existing studies use inexact and low-rank approximations (Giovannelli et al., 2025), curvature-aware and KFAC approximations (Dong et al., 2025; Liao et al., 2026), Krylov subspaces (Yang et al., 2025), and finite differences (Yang et al., 2023). For stochastic compression, PRAC uses principal directions and a random complementary subspace for activation compression (Li et al., 2026), while BROS addresses shared-projection bias through randomized-subspace updates and a bi-probe correction (Zhang et al., 2026). OPR-BROS compresses derivative actions within a single-loop recursion, uses independent two-sided factors to avoid the bias correction required by shared projections, and reuses past information through historical subspaces.
Penalty methods. This line of work incorporates lower-level optimality into a surrogate objective through penalty reformulations. Representative studies include PBGD (Shen and Chen, 2023), analyses of nonconvex lower-level problems under error-bound conditions (Kwon et al., 2024), and first-order penalty methods with ϵ-KKT guarantees (Lu and Mei, 2024). Recent methods PBGD-Free, PNGBiO, and SFLCB study upper-level flatness, nonconvex lower-level problems under generalized smoothness, and coupled linear constraints, respectively (Jiang et al., 2025; Zhang et al., 2025; Shen et al., 2025). Related research also extends to minimax and constrained lower-level problems (Shen et al., 2026). These studies broaden the theory and scope of penalty reformulations; our work studies the memory and computational efficiency of implicit recursions in the nonconvex–strongly-convex setting.
Fully first-order methods. This line of work relies only on first-order gradient oracles and overlaps with some penalty methods. F²SA establishes nonasymptotic guarantees for fully first-order stochastic bilevel optimization (Kwon et al., 2023). Subsequent studies further improve deterministic and stochastic first-order complexity for nonconvex–strongly-convex problems (Chen et al., 2025) and cover differentiable constrained optimization layers, online bilevel optimization, and finite-sum variance reduction (Zhao et al., 2026; Jia and Chen, 2026; Zhou and Niu, 2026). Related work also provides first-order oracle complexity lower bounds (Ji, 2026). These studies mainly focus on algorithms and oracle-call complexity under first-order oracles; OPR-BROS retains implicit derivative operators, focusing on reducing the computational dimension of derivative actions and using historical information to improve projection quality.
W2/Q1. Strong convexity and Assumption 3.3
Lower-level strong convexity, also assumed by MA-SOBA and BROS, ensures a unique lower-level solution and an invertible Hessian. Under this shared assumption, OPR-BROS preserves their O(K−1/2) stationarity rate, reduces memory relative to MA-SOBA by compressing the working dimension, and reduces computation relative to BROS by eliminating correction queries.
Assumption 3.3 can be implemented through Algorithm 1:
References
[1] Chen, X., et al. "Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions." JMLR, 2024.
[2] Zhang, H., et al. "BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization." arXiv:2605.10288, 2026.