Abstract
In this paper, we propose a new Hessian inverse free Fully Single Loop Algorithm (FSLA) for bilevel optimization problems. Classic algorithms for bilevel optimization admit a double loop structure which is computationally expensive. Recently, several single loop algorithms have been proposed with optimizing the inner and outer variable alternatively. However, these algorithms do not yet achieve a fully single loop, as they overlook the loop needed to evaluate the hyper-gradient for a given inner and outer state. In order to develop a fully single loop algorithm, we first study the structure of the hyper-gradient and identify a general approximation formulation of hyper-gradient computation that encompasses several previous common approaches, such as back-propagation through time and conjugate gradient. Based on this formulation, we introduce a new state variable to maintain historical hyper-gradient information. Combining our new formulation with the alternative update of the inner and outer variables, we propose an efficient fully single loop algorithm. We theoretically show that the error generated by the new state can be bounded and our algorithm converges with the rate of $O(\epsilon^{-2})$. Finally, we verify the efficacy of our algorithm empirically through multiple bilevel optimization based machine learning tasks.
Introduction
Bilevel optimization is a framework for solving nested optimization problems where an "outer" objective depends on the optimal solution of an "inner" objective. This structure is foundational to many modern machine learning paradigms, including hyperparameter optimization, meta-learning, and neural architecture search. Despite its utility, bilevel optimization is computationally demanding. Traditional "double-loop" algorithms require solving the inner problem to high precision for every update of the outer variable, leading to significant overhead.
Recent efforts have introduced "single-loop" methods that update inner and outer variables alternatively. However, these methods often encounter a "hidden" loop during hyper-gradient evaluation. Calculating the gradient of the outer objective typically necessitates approximating a Hessian inverse or employing iterative techniques like backpropagation through time (BP) or conjugate gradient (CG). These sub-procedures effectively re-introduce an inner loop, preventing a truly single-loop execution.
Methodology: The FSLA Algorithm
The proposed Fully Single Loop Algorithm (FSLA) addresses this bottleneck by treating hyper-gradient estimation as a dynamic process. The authors first establish a unified framework, proving that common hyper-gradient approximation methods (BP, Neumann Series, and CG) can be represented by a single recursive formulation.
Building on this, FSLA introduces a new state variable, $v_k$, to track historical hyper-gradient information. Instead of re-computing the hyper-gradient from scratch at each step, FSLA performs a single-step update on $v_k$ alongside the inner ($\omega$) and outer ($\lambda$) variables. To ensure stability in stochastic environments, the algorithm incorporates a momentum-based variance reduction technique inspired by the STORM optimizer. This allows FSLA to maintain a theoretical convergence rate of $O(\epsilon^{-2})$ for non-convex-strongly-convex problems, matching the complexity of standard single-level stochastic optimization.
Experimental Evaluation
The efficacy of FSLA was evaluated on synthetic datasets and hyper data-cleaning tasks using MNIST, Fashion-MNIST, and QMNIST. In data-cleaning, the model learns weights for training samples to minimize loss on a clean validation set, identifying noisy labels in the process.
Empirical results demonstrate that FSLA significantly outperforms traditional methods in terms of wall-clock time. While iterative methods like BP, NS, or CG require multiple matrix-vector products per outer step, FSLA requires only one. As shown in the performance benchmarks, FSLA converges to lower validation losses much faster than various BP configurations.
Conclusion
FSLA represents a significant step forward in bilevel optimization by achieving a truly fully single-loop structure. By eliminating the need for expensive Hessian inverses and iterative hyper-gradient sub-loops, it offers a highly efficient alternative for large-scale machine learning tasks. While current theoretical guarantees assume a strongly convex inner problem, the empirical success of FSLA suggests broad applicability. Future work will focus on extending these guarantees to non-convex inner problems and exploring applications in complex domains like Neural Architecture Search.
Summary updated