mlsanityData to 14 Oct 2026

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

arXiv 2605.10288 ↗First posted 11 May 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic bilevel optimization (SBO) has become a standard framework for hyperparameter learning, data reweighting, representation learning, and data-mixture optimization in deep learning. Existing exact single-loop SBO methods and memory-efficient surrogate SBO methods either create severe memory pressure for large lower-level neural networks or lack competitive convergence guarantees under standard assumptions. In this paper, we propose BROS, a memory-efficient single-loop SBO method with the same convergence rate order as exact single-loop SBO methods. BROS performs lower and auxiliary updates in randomized subspaces with a Rademacher bi-probe correction that recovers an unbiased Hessian-action estimator. We prove that BROS preserves the mathcal O(varepsilon-2) sample complexity of MA-SOBA for finding an varepsilon-stationary point under only standard assumptions. Experiments on hyper-data cleaning, data-mixture learning, hyper-representation learning, and ViT sample reweighting show that BROS reduces peak memory by up to 44.9% while closely matching full-space baseline performance.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 60 of its 69 references that are in the map. First posted on arXiv 11 May 2026.

Builds on

60 of 69 references.

References · 60

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  5. 2019Parameter-Efficient Transfer Learning for NLPcited by 4,236
  6. 2020The Pile: An 800GB Dataset of Diverse Text for Language Modelingcited by 2,411
  7. 2020GLU Variants Improve Transformercited by 1,804
  8. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,346
  9. 2022GPT-NeoX-20B: An Open-Source Autoregressive Language Modelcited by 713
  10. 2018Learning to Reweight Examples for Robust Deep Learningcited by 675
  11. 2019Meta-Learning with Implicit Gradientscited by 525
  12. 2024GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projectioncited by 463
38 more
  1. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  2. 2023DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretrainingcited by 399
  3. 2018Meta-learning with differentiable closed-form solverscited by 397
  4. 2018Approximation Methods for Bilevel Programmingcited by 236
  5. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  6. 2023ReLoRA: High-Rank Training Through Low-Rank Updatescited by 204
  7. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
  8. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  9. 2019Meta Label Correction for Noisy Label Learningcited by 108
  10. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  11. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  12. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
  13. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  14. 2024SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selectioncited by 64
  15. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 63
  16. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  17. 2024APOLLO: SGD-like Memory, AdamW-level Performancecited by 54
  18. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  19. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  20. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
  21. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  22. 2024SLTrain: a sparse plus low-rank approach for parameter and memory efficient pretrainingcited by 45
  23. 2024ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweightingcited by 37
  24. 2019RSN: Randomized Subspace Newtoncited by 34
  25. 2024Subspace Optimization for Large Language Models with Convergence Guaranteescited by 34
  26. 2019Penalty Method for Inversion-Free Deep Bilevel Optimizationcited by 33
  27. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  28. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  29. 2025CoLA: Compute-Efficient Pre-Training of LLMs via Low-Rank Activationcited by 28
  30. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  31. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  32. 2023Learning from Noisy Labels with Decoupled Meta Label Purifiercited by 21
  33. 2024VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projectionscited by 18
  34. 2025A Memory Efficient Randomized Subspace Optimization Method for Training Large Language Modelscited by 16
  35. 2024Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysiscited by 15
  36. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  37. 2024Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimizationcited by 11
  38. 2023Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problemscited by 8

50 most cited of 60 All 60 (JSON)

Built on by

Not cited yet.