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

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 $\mathcal{O}(K^{-1/2})$ squared-stationarity rate, or $\mathcal{O}({\epsilon }^{-2})$ 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.