Reproduce “BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Hengrui Zhang, Boao Kong, Engao Zhang, Kun Yuan

BROS, a method from Sichuan University and Peking University, enables memory-efficient stochastic bilevel optimization (SBO) for large neural networks by employing bias-corrected randomized subspaces. It achieved memory reductions of up to 72% on tasks like CIFAR-100 ViT Sample Reweighting while preserving the state-of-the-art O(ε⁻²) convergence rate of exact full-space SBO methods.

Key insights

  • A direct application of randomized subspace projection to second-order information (e.g., Hessian-vector products) in SBO introduces a fundamental bias that prevents convergence to a true stationary point.
  • This projection-induced bias can be accurately corrected through an additional set of carefully designed 'probe' queries (Rademacher bi-probes), enabling unbiased estimation of full-space Hessian actions from compressed subspace representations.
  • By combining randomized subspace operations with this bias correction, it is possible to achieve substantial memory savings in SBO while retaining the exact hypergradient update structure and its strong theoretical convergence guarantees.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.