Research map / Optimization / Nonconvex and smooth optimization

BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Penalty and implicit-gradient bilevel methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes BROS, a single-loop stochastic bilevel method that runs the lower-level and auxiliary recursions in randomized Haar subspaces and corrects the projection-induced Hessian bias with Rademacher bi-probes, matching MA-SOBA's O(ε^-2) rate with lower memory.

Problem

Exact single-loop stochastic bilevel methods create large memory pressure when the lower-level is a large neural network, while memory-efficient surrogates lose exact hypergradient recovery or convergence rates.

Approach

Sample random Haar projectors to compress lower-level and auxiliary updates into subspaces, and remove the bias of the lifted sketched Hessian action with a layerwise Rademacher bi-probe correction so the auxiliary HVP is conditionally unbiased for the full Hessian action.

Key results

• On MNIST hyper-data cleaning with 50% label noise, BROS reaches 84.30% test accuracy vs 84.46% for MA-SOBA, outperforming Penalty, FdeHBO and ZOFO.
• On data-mixture learning, BROS achieves average loss 2.8109, essentially matching MA-SOBA (2.8098), and reduces proxy peak memory by about 45% vs MA-SOBA and about 27% vs Penalty.
• Theoretical analysis gives O(K^{-1/2}) stationarity rate with constants depending on omega_P = max m/r, i.e. O(eps^-2) sample complexity matching MA-SOBA.

Surprising findings

• The vanilla sketch-then-lift auxiliary HVP is biased even with Haar projectors satisfying E[PP^T]=I, and a deterministic quadratic counterexample shows it can converge to a nonstationary point.

Limitations

• Convergence theorem only covers the SGD-style recursion; momentum and Adam variants are not analyzed.
• Remaining activation memory is still significant in large architectures.
• Constants scale with (1+omega_P^4), so small subspace ratios inflate variance and iteration counts.

Experimental setup

Datasets: MNIST CIFAR-10 CIFAR-100 The Pile (17 copyright-free domains)

Benchmarks: MNIST hyper-data cleaning data-mixture learning on Pile domains CIFAR-10 hyper-representation learning CIFAR-100 ViT sample reweighting

Metrics: test accuracy average per-domain loss peak memory step rate

Baselines: MA-SOBA Penalty FdeHBO ZOFO SOBA SPABA SUSTAIN MRBO

Builds on: MA-SOBA randomized subspace optimization (RSO) randomized subspace Newton (RSN) SOBA

Closest papers by meaning

• A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.88)
• Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guarantees (ICML 2025 · similarity 0.88)
• Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.87)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization (NeurIPS 2024 · similarity 0.87)
• Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.87)
• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.87)