acceptodds
Under review as a conference paper at ICLR 2027

OPR-BROS: History-Aware Principal–Random Bi-Sketching for Bilevel Optimization

Abstract

Stochastic bilevel optimization (SBO) is a standard framework for data reweighting, hyperparameter optimization, meta-learning, and data-mixture learning. Exact single-loop SBO methods operate with full-dimensional states and derivative computations. Randomized-subspace methods reduce the working dimension, motivating estimators that combine conditional unbiasedness, efficient operator evaluation, and reuse of persistent directions. We propose OPR-BROS, a history-aware single-loop coordinate method that combines independent operator bi-sketching with predictable principal-random factors. Independent input and output sketches yield conditionally unbiased Hessian actions, while a past-only Oja update learns reusable directions and a fresh random complement preserves exploration. We establish exact sketch-moment and mean-squared-error identities, prove that OPR-BROS retains the standard squared-stationarity rate, or iteration complexity, under the stated assumptions, and derive a bound that retains the realized, operator-weighted sketch risks. Small-task experiments show favorable validation time-to-quality, and a Pile-280M experiment attains competitive upper-level loss with low measured step time and peak memory.

Primary area:
optimization
Keywords:
stochastic bilevel optimization, computation-efficient optimization, randomized subspace methods

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_if44OpenReview ↗
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 O(ϵ−2)O(\epsilon^{-2}) 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
  1. 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.

  2. 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
  1. 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].
  2. 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.
  3. The paper introduces too much notation, some of which seems unnecessary. This significantly affects readability and makes the main ideas difficult to follow.

  4. 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
  1. 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?

  2. Why does the paper compare against an older Penalty method rather than more recent fully first-order methods such as F2SA?

  3. What is the practical advantage of implicit-gradient methods for large-scale problems? Given that value-function penalty methods can approximate implicit hypergradients with O(1/γ)O(1/\gamma) error under suitable assumptions, why are they not compared in performance versus wall-clock time?

  4. 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
AuthorsOpenReview ↗

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 ϵ\epsilon-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)\mathcal 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:

  1. Fixed ranks (Lines 1, 3): total, historical, and fresh ranks are fixed before the run.
  2. Past-measurable basis and mixing probability (Lines 3, 12; Section 2.2; Eq. (4)): Oja/QR updates history after the current computation for use next iteration, inductively preserving orthonormality and Fk\mathcal F_k-measurability from an orthonormal initialization.
  3. Conditional branch independence (Line 4; Section 2.3): branches use independent fresh randomness; shared past bases are fixed conditional on Fk\mathcal F_k.
  4. Factor–oracle independence (Lines 4, 6): factors and current data use independent randomness.
  5. Identity mean (Line 4; Eq. (5)): normalized complementary sampling gives Ek[Qk]=I\mathbb E_k[Q^k]=I.
  6. Bounded second moments (Lines 3, 4; Eq. (5)): fixed ranks and rf≥1r_f\ge1 for non-full-space blocks give an iteration-uniform finite bound; full-space blocks use Qk=IQ^k=I.
  7. Finite initialization errors independent of rank and iteration count (Line 1): the same fixed finite deterministic inputs, with Assumption 3.1, give a finite initial objective gap and three squared tracking errors.

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.

AuthorsOpenReview ↗

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).

CategorySymbolsMeaning
Problem/statesf,g,Φf,g,\Phi; xk,Ykx^k,\boldsymbol Y^kObjectives; upper/lower-level states
Projections/historyr,rh,rfr,r_h,r_f; Pk,QkP^k,Q^kTotal/historical/fresh ranks; factor/lifting operator
Derivatives/directionsHk,Jk\mathscr H_k,\mathscr J_kHessian/mixed-Jacobian operators
AnalysisFk,Ek\mathcal F_k,\mathbb E_kPast information; conditional expectation

We will clarify that ⋅~\widetilde{\cdot} denotes low-dimensional derivatives/operators and ⋅^\widehat{\cdot} 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.

MethodFinal upper-level loss ↓Per-step time (s) ↓Peak GPU memory (GiB) ↓
OPR-BROS (History)3.1437 ± 0.00770.3543 ± 0.000956.04
OPR-BROS (Fresh)3.1859 ± 0.00300.3520 ± 0.001156.04
BROS (w correction)3.1525 ± 0.01321.7104 ± 0.002156.30
Penalty3.5040 ± 0.02110.8967 ± 0.000261.58
F²SA3.3927 ± 0.00230.5341 ± 0.000757.81
V-PBGD3.2022 ± 0.01611.1383 ± 0.002054.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.

MethodActual training tokensFinal fixed7 CE ↓Actual runtime (h)Peak GPU memory (GiB)
OPR-BROS (History)10.54B3.087366.1685.14
MA-SOBA12.04B2.755261.5192.40
DoReMi Proxy11.35B3.267166.5688.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.

TaskMethodFinal validation CE ↓Average per-step time (s, including validation) ↓Peak GPU memory (GiB, allocated / reserved) ↓
CIFAR-10OPR-BROS (History)1.30410.25350.849 / 0.973
CIFAR-10F²SA1.85820.21611.000 / 1.080
CIFAR-10V-PBGD1.31370.31550.875 / 0.934
CIFAR-100OPR-BROS (History)2.29840.87464.918 / 5.127
CIFAR-100F²SA2.40050.76125.061 / 5.303
CIFAR-100V-PBGD2.31391.55655.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.

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

This paper presents OPR-BROS, a history-aware randomized subspace method for stochastic bilevel optimization. Independent input and output sketches are used to construct unbiased Hessian vector products. Historical directions are incorporated using Oja update. Theoretical analysis establishes O(ϵ−2)O(\epsilon^{-2}) iteration complexity under the standard nonconvex–strongly-convex assumptions. Numerical experiments are designed to measure the performance of the proposed algorithm.

Critical strengths

Clean motivation. Independent sketches on both input and output sides give an unbiased estimator. Clean presentation. The background is well-explained; assumptions and results are stated cleanly.

Critical weaknesses

Some experimental results do not fully match algorihtm 1. More clarification of these results would be beneficial to the presentation of the paper.

Questions for authors

Table 3: The last two rows report archived configurations (O-Fresh and B-NoProbe), neither of which appears to implement the full proposed Algorithm 1. Why is the complete OPR-BROS algorithm not included in this experiment? Appendix E states that Fresh and OPR-BROS retain exact first-order gradients in the small and native-network experiments. Could the authors clarify the motivations for using exact gradients in these experiments? Line 1610. "We organize the evidence by setting." This sentence seems to be unfinished.

2 comments
AuthorsOpenReview ↗

Response to Reviewer YYzd

Response to Reviewer YYzd

Thank you for your comments. We address each question below.

Q1. Evaluation of the complete OPR-BROS algorithm

The original Table 3 used simplified archived configurations. We have added OPR-BROS (History) with History, Oja updates, and independent sampling of the five factors enabled, along with BROS (w correction). OPR-BROS (Fresh) and BROS (w/o correction) are retained as ablation baselines. All four methods use the same common settings, with projections refreshed every 16 steps, and have been compared over three random seeds.

Table R2-1. Pile-280M, 10,000 steps, seeds 42/43/44. Loss and time are reported as mean ± standard deviation. Memory is the sum of the peak allocated memory across four GPUs.

MethodFinal upper-level loss ↓Per-step time (s) ↓Peak memory (GiB) ↓
OPR-BROS (History)3.1437 ± 0.00770.3543 ± 0.000956.04
OPR-BROS (Fresh)3.1859 ± 0.00300.3520 ± 0.001156.04
BROS (w/o correction)3.1504 ± 0.03031.2079 ± 0.002556.30
BROS (w correction)3.1525 ± 0.01321.7104 ± 0.002156.30

Compared with OPR-BROS (Fresh), OPR-BROS (History) reduces the mean final loss by 1.32%, with only a 0.65% increase in per-step time. Compared with BROS (w correction), OPR-BROS (History) achieves a similar final loss and an approximately 4.83-fold speedup in mean per-step time.

Q2. Motivation for retaining exact first-order gradients

In both OPR-BROS (Fresh) and OPR-BROS (History), we retain the uncompressed first-order gradients within the current minibatch to isolate the effects of compressing Hessian/mixed-Jacobian actions and reusing history. This corresponds to the special case Qgk=Quk=IQ_g^k=Q_u^k=I in Algorithm 1. Here, “exact” is relative to the current minibatch; data sampling remains stochastic.

We have also added an ablation over three seeds. On MNIST, when the first-order gradients are also projected, OPR-BROS (History) improves accuracy over OPR-BROS (Fresh) by 13.83 percentage points; when uncompressed first-order gradients are retained, the improvement is 11.29 percentage points. This indicates that the benefit of history reuse on this task also exists when first-order gradients are compressed. On FashionMNIST, the accuracy gap between OPR-BROS (History) and OPR-BROS (Fresh) is approximately 0.01 percentage points under both settings.

Q3. Clarification of the sentence at Line 1610

This sentence introduces the experimental settings and supplementary results for each task in Appendix E. The specific wording is: “We present the experimental settings and supplementary results separately for each task.”

Thank you again for your comments.

References

[1] Zhang, H., et al. "BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization." arXiv:2605.10288, 2026.

Thank you for the detailed response. The additional experiments have sufficiently addressed my concerns. I will maintain my original score.

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

This paper proposes OPR-BROS, a history-aware single-loop method for reducing derivative computation costs in stochastic bilevel optimization. It uses conditionally independent input and output sketches to estimate Hessian actions without distribution-specific bias correction, while combining past-only Oja updates with a fresh random complement to balance direction reuse and exploration. The authors establish conditional unbiasedness, exact mean-squared-error decompositions, and operator-weighted risk characterizations, and recover the standard convergence rate in expected squared gradient norm under the stated nonconvex–strongly-convex assumptions. The paper further analyzes memory and computational costs and reports experiments on data cleaning, data-mixture optimization, and neural-network tasks.

Critical strengths
  1. The paper addresses derivative computation as an important bottleneck in large-scale bilevel optimization. Reducing operator evaluation costs while preserving the standard single-loop recursion is a worthwhile research direction.

  2. Conditional independence between the input and output factors allows the construction to recover the full Hessian action in expectation, including both within-layer and cross-layer derivative contributions.

  3. The history basis is updated after computing the current directions and used in the next iteration, avoiding additional dependence between current samples and adaptive factors. The convergence bound also explicitly retains the factor-moment parameters, accounting for the stochastic error introduced by low-rank compression.

Critical weaknesses
  1. Independent Hessian factors and the history basis introduce additional storage, so memory savings depend on maintaining comparable optimization quality at a smaller total sketch width. The experiments do not directly establish the connection between history reuse, width reduction, and measured memory savings, while the native-network results show no consistent time or memory gains. Moreover, BROS in Table 6 uses a different compression ratio and a generic-autograd reconstruction, limiting direct attribution of performance differences to algorithm design.

  2. The risk conditions and stationarity bounds are valuable, but Proposition C.1 assumes a fixed signal, an eigengap, and a warm start. It therefore does not directly establish the behavior of the default Oja update under evolving auxiliary states. Capturing the auxiliary state’s Euclidean energy also does not necessarily reduce Hessian- or Jacobian-weighted errors. The History/Fresh HVP-MSE ratio of 1.5185 under history mismatch in Table 8 illustrates this potential downside. The authors should clarify whether the selector in C.2 or another fallback strategy is used in the experiments, and provide evidence of risk reduction in the key branches along actual optimization trajectories.

  3. The appendix states that O-Fresh uses neither History nor Oja updates and disables branch-independent sampling, while B-NoProbe disables CorrHVP. O-Fresh also uses a time-optimized archived configuration, whereas the other configurations use the common v12 setting. These results therefore cannot directly be interpreted as a comparison between complete OPR-BROS and bias-corrected BROS, and timing differences cannot be attributed solely to algorithm design. Although these differences are disclosed in the appendix, the figure legends still use BROS and OPR-BROS. The authors should clarify how O-Fresh relates to Eq. (8), consistently label the variants, and either provide comparisons under matched execution settings or qualify the conclusions accordingly.

Questions for authors
  1. When branch-independent sampling is disabled in the Pile experiments, which factors are shared? Does the implementation follow the factor construction in Eq. (8) and satisfy the conditional independence requirements of Lemma 3.1? Are comparable results for complete OPR-BROS and bias-corrected BROS already available?

  2. How does the time-optimized O-Fresh configuration differ from the v12 settings used for the other methods? Can the same optimizations be applied uniformly across methods?

  3. Are sketch-width sweeps or comparisons under matched resource budgets already available on the existing tasks to assess whether history reuse permits a smaller total sketch width while maintaining comparable optimization quality?

  4. Was the history/fresh selector in Appendix C.2 enabled in the experiments? If so, how were pilot-query and update costs accounted for? If not, how were the history rank, update frequency, and freezing schedule selected?

4 comments
AuthorsOpenReview ↗

Response to Reviewer cjjA (1/2)

Response to Reviewer cjjA (1/2)

Thank you for your comments. We address the concerns below.

W1/Q3. History reuse, sketch width, and resource comparisons

We have added a comparison of two sketch widths on CIFAR-100 using SmallViT, batch size 512, and seed 42. All methods were trained for 6,000 steps and evaluated on the same 10,000 official test images; the schedule for OPR-BROS (History) was selected using the validation set. Reducing its compression ratio from ρ=0.25\rho=0.25 to 0.200.20 reduces the total number of sketch columns from 4,704 to 3,920, a reduction of 16.7%, while maintaining similar validation and test quality. At the same ρ=0.25\rho=0.25, OPR-BROS (History) achieves 3.68 percentage points higher test accuracy than OPR-BROS (Fresh).

Table R1-1. CIFAR-100, 6,000 steps, single seed. Memory is peak training allocated / reserved GPU memory; the runs used different physical RTX 4090 GPUs.

MethodCompression ratio ρ\rhoValidation CETest accuracyPeak GPU memory (GiB)
OPR-BROS (History)0.202.247950.26%4.902 / 5.121
OPR-BROS (History)0.252.235849.85%4.907 / 5.127
OPR-BROS (Fresh)0.202.471445.73%5.266 / 5.589
OPR-BROS (Fresh)0.252.437746.17%5.284 / 5.600
BROS (w/o correction)0.252.935632.26%15.382 / 16.525

We have also added a four-method comparison on Pile-280M under common execution settings, including OPR-BROS (History) and OPR-BROS (Fresh). All methods were trained for 10,000 steps using seeds 42/43/44 and four A100 GPUs. The independent sampling and projection-refresh settings are described in W3/Q1/Q2 in Part 2.

Table R1-2. Pile-280M, 10,000 steps, seeds 42/43/44. Loss is the worst-domain excess validation CE. Loss and per-step time are reported as mean ± standard deviation; memory is the sum of peak allocated GPU memory across the four GPUs.

MethodFinal upper-level loss ↓Time per step (s) ↓Peak GPU memory (GiB) ↓
OPR-BROS (History)3.1437 ± 0.00770.3543 ± 0.000956.04
OPR-BROS (Fresh)3.1859 ± 0.00300.3520 ± 0.001156.04
BROS (w/o correction)3.1504 ± 0.03031.2079 ± 0.002556.30
BROS (w correction)3.1525 ± 0.01321.7104 ± 0.002156.30

In this experiment, OPR-BROS (History) reduces the final upper-level loss by 1.32% relative to OPR-BROS (Fresh), with only a 0.65% increase in per-step time and the same measured peak GPU memory.

W2. Scope of Proposition C.1 and operator-weighted errors

Proposition C.1 characterizes the local alignment behavior of the Oja update under a fixed signal: the eigengap determines the target principal subspace, and the warm start restricts the analysis to a local contraction region. The main convergence theorem does not require a fixed signal, an eigengap, or a warm start for the history basis. Under the remaining assumptions and step-size conditions, the history mechanism only needs to satisfy past measurability, conditional independence, and uniform moment bounds. Benefits from history under changing signals are evaluated through operator errors along training trajectories.

Capturing more Euclidean energy alone is insufficient to guarantee a reduction in derivative-estimation error. Appendix B uses operator-weighted risks corresponding to the Hessian and mixed Jacobian, and the full HVP decomposition includes output-side errors and input–output interaction terms. The benefit of history depends jointly on these weighted risks and the remaining fresh width, and the history-sensitive stationarity bound retains the accumulated contribution of the actual risks.

To directly test the effect under evolving auxiliary states, we have added FashionMNIST training-trajectory diagnostics using three seeds and the same total sketch width.

Table R1-3. MSE ratios of OPR-BROS (History) to OPR-BROS (Fresh); values below 1 indicate lower error for OPR-BROS (History). The full HVP includes the effect of the output-side projection.

Training stepFull HVPHessian input branchMixed-Jacobian input branch
1001.0030.9681.025
1,0000.5280.1100.102
6,0000.1580.0008430.000704

The two estimators have similar errors early in training. At steps 1,000 and 6,000, OPR-BROS (History) reduces the full HVP-MSE by 47.2% and 84.2%, respectively, and errors in both input branches also decrease. These results provide direct empirical evidence of improved operator estimation during training.

AuthorsOpenReview ↗

Response to Reviewer cjjA (2/2)

Response to Reviewer cjjA (2/2)

W2/Q4. History mismatch, the selector, and fixed update schedules

The experiments reported in the paper did not enable the pilot-query selector in Appendix C.2, so there was no corresponding pilot-query overhead. To examine history mismatch, we have added a recovery experiment and training-trajectory diagnostics. On the same eight synthetic instances as in Table 8, the HVP-MSE ratio of OPR-BROS (History) to OPR-BROS (Fresh) is 1.5185 after the signal switch. After 10 and 25 additional Oja updates, the ratio decreases to 0.8362 and 0.5923, respectively, showing that updates can readapt the history basis to the changed signal.

For the FashionMNIST training-trajectory diagnostics, please refer to W2 and Table R1-3 in Part 1.

The history rank and update schedules were fixed empirically before the experiments. MNIST uses a total width of 256 and a history rank of 64. It uses OPR-BROS (Fresh) for the first 600 steps while maintaining the history basis; Oja updates occur every 10 steps, and the basis is frozen after step 1,200. CIFAR uses a fixed 500-step OPR-BROS (Fresh) warm-up and a history rank equal to one quarter of the total width. In the newly added CIFAR-10 experiment, the history basis is updated every 16 steps.

W3/Q1/Q2. Variant definitions and matched execution settings

Relative to Equation (8), the original O-Fresh disables History/Oja. Its time-optimized archived configuration also shared projection matrices across some branches to reduce the overhead of sampling multiple factors within the experimental time budget. The other baselines used the common v12 configuration. Their algorithms do not involve the five independent projection groups required by OPR-BROS, so they have no corresponding option for this multi-factor sharing optimization; this therefore does not introduce an unfair comparison.

We have rerun OPR-BROS (Fresh) and OPR-BROS (History) with independent sampling of all five factors, removing projection sharing between branches, and compared them with BROS (w correction) and BROS (w/o correction) under common execution settings using three seeds. At each projection refresh, Pg,Pu,Pi,Po,PjP_g,P_u,P_i,P_o,P_j are sampled independently conditional on past information. This uses the independent Hessian input/output factor construction in Equation (8) and satisfies the branch independence required by Lemma 3.1. OPR-BROS (History) enables the history basis and Oja updates, whereas OPR-BROS (Fresh) uses no history component. All projection methods refresh their projections every 16 steps, with the remaining common settings held the same.

In the next version, the figure legends will explicitly label the original O-Fresh as OPR-BROS (Fresh) and B-NoProbe as BROS (w/o correction). The legends will consistently distinguish OPR-BROS (History), OPR-BROS (Fresh), BROS (w correction), and BROS (w/o correction); the newly added OPR-BROS (History) enables all the components described above.

The full four-method results are reported in Table R1-2 in Part 1. OPR-BROS (History) and BROS (w correction) achieve similar final losses, while the mean time per step decreases from 1.7104 s to 0.3543 s, corresponding to an approximately 4.83-fold speedup. The comparison between OPR-BROS (History) and OPR-BROS (Fresh) is discussed in W1/Q3 in Part 1. BROS (w correction) and BROS (w/o correction) show no clear difference in final upper-level loss, but correction reduces the cross-seed standard deviation of final loss from 0.0303 to 0.0132, a reduction of 56.44%.

Thank you again for your comments.

References

[1] Zhang, H., et al. "BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization." arXiv:2605.10288, 2026.

AuthorsOpenReview ↗

Can we have valuable feedback on our rebuttals?

Dear Reviewer cjjA,

We sincerely thank you for your valuable comments and the time and effort you have devoted to reviewing our submission.

We have carefully addressed your concerns in our rebuttal and would greatly appreciate it if you could take a moment to review our responses and let us know whether any concerns remain. Your further feedback would be invaluable in helping us strengthen and improve our work.

Thank you again for your time and consideration.

Best regards,

The Authors

Reviewer_cjjAOpenReview ↗

Additional Review Comments

I have read the authors’ response and the other reviewers’ comments. I agree with Reviewer if44 that assuming strong convexity of the lower-level objective limits the scope of the results. The authors point out that MA-SOBA and BROS also rely on this assumption. I find that clarification reasonable. The limitation still matters, but given that these related methods share it, I do not think it warrants changing my original score.

My familiarity with this area of bilevel optimization is limited. I therefore ask the AC and the other reviewers to weigh my assessment alongside the views of reviewers with more expertise in this area.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response to All Reviewers

We thank reviewers cjjA, YYzd, and if44 for their feedback. This overview complements our individual replies. Key revisions are highlighted in blue in the revised manuscript.

1. Complete-method comparisons and recent baselines (cjjA W3/Q1–Q2; YYzd Q1; if44 W4/Q2–Q3)

We add three-seed, 10,000-step Pile comparisons with common execution settings. OPR-BROS (History) includes history reuse, Oja updates, and independent sampling across five factor groups; BROS (w correction) includes CorrHVP. Their final losses are 3.1437±0.0077 and 3.1525±0.0132, respectively, with step times of 0.3543 and 1.7104 s: a 4.83-fold step-time advantage at similar final loss. The expanded comparisons include F²SA and V-PBGD on Pile and native CIFAR. On CIFAR-10 (seed 42), History/F²SA/V-PBGD give final CE 1.3041/1.8582/1.3137 and step times 0.2535/0.2161/0.3155 s, respectively. Locations: Sec. 5, Fig. 1, Table 3; App. F.1/F.3, Tables 7, 10–11.

2. History reuse, sketch width, and memory (cjjA W1/Q3)

On three-seed CIFAR-100 at ρ=0.25\rho=0.25, OPR-BROS (History) improves mean validation CE from 2.3624 to 2.2453 relative to OPR-BROS (Fresh), with peak allocated memory of 4.907 versus 5.284 GiB. Reducing History’s total sketch width from 4,704 to 3,920 columns (16.7%) gives validation CE 2.2280. Peak memory remains approximately unchanged across these two History widths (4.907 versus 4.901 GiB). We distinguish this measured result from the theoretical memory crossover condition. Locations: Sec. 4.1; App. E.1/F.3, Table 10.

3. Oja tracking and operator-estimation risk (cjjA W2/Q4)

We add diagnostics along actual Fashion-MNIST optimization trajectories over three seeds. At matched width, History reduces full HVP MSE by 47.2% at step 1,000 and 84.2% at step 6,000. In the synthetic signal-shift experiment, the History/Fresh HVP-MSE ratio decreases from 1.5185 immediately after the shift to 0.8362 and 0.5923 after 10 and 25 further Oja updates. Optimization experiments use fixed update schedules without the optional pilot-query selector. Locations: App. D.1–D.2; App. F.2/F.5, Tables 8, 12–13.

4. Problem assumptions and algorithmic guarantees (if44 W2/Q1)

Former Assumption 3.3 is now Proposition 3.1, derived from Assumptions 3.1–3.2 and the specified initialization, sampling, and update rules. Its proof establishes history predictability, conditional independence, identity means, uniform factor moments, and finite initial errors, together with an induction for finite-time integrability. We retain the standard nonconvex–strongly-convex theoretical setting used by MA-SOBA and BROS, with the same O(ε−2)O(\varepsilon^{-2}) iteration order for fixed factor-moment bounds. Locations: Sec. 3.1–3.3, Proposition 3.1; App. C.1.

5. Full-parameter evaluation at the 500M scale (if44 W4/Q4)

We add a DataFlex proxy experiment with approximately 500M trainable lower-level parameters. OPR-BROS (History) uses Adam, history reuse, Oja updates, and independent draws for all five factors. It reaches mean cross-entropy 3.0873 on the fixed7 evaluation panel after 10.54B training tokens. The single-run comparison with MA-SOBA and DoReMi reports each method’s training tokens, final quality, elapsed time, and memory, extending the evaluation to full-parameter training at this scale. Location: App. F.6, Table 14.

6. Related work and readability (if44 W1/W3; YYzd Q3)

We expand related work on memory-efficient implicit gradients, penalty formulations, and fully first-order methods. A categorized notation table groups optimization states, sketches/history, operators/directions, and analysis parameters. We also standardize the four variant names and reorganize the experiment descriptions. Locations: App. A–B, Table 5; Sec. 5 and App. F.

Thank you again for the constructive feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.