From Nested Solving to Predictive Tracking: Learning Lower-Level Dynamics for Bi-level Optimization

Bi-level optimization couples an upper-level objective with a parameter-dependent lower-level problem, requiring repeated lower-level solves as the upper-level variable evolves. Repeatedly solving the lower-level problem is costly, but inaccurate responses distort the upper-level update. We introduce SUPRO, a first-order method that tracks a persistent lower-level response across outer iterations. SUPRO models the joint state of the lower-level iterate and an auxiliary value response to predict response motion, and adapts the predictor online using feedback from subsequent corrections. Fixed-budget gradient corrections and objective-based candidate selection control prediction errors. We establish a non-asymptotic stationarity guarantee for the associated fixed value-function penalty, together with a response-tracking bound that improves as predictions become more accurate. SUPRO uses only single-loop computation and requires neither Hessian-vector products nor implicit linear solves. Experiments on nonconvex problems, representative learning tasks, and large-model post-training show that SUPRO realize remarkable performances while maintaining stable optimization.