Abstract
Bilevel optimization is a critical framework for modern machine learning tasks such as meta-learning and neural architecture search, yet it is often hampered by the computational cost of inner-loop optimization and Hessian inversions. We present the Fully Single Loop Algorithm (FSLA), a novel approach that eliminates these bottlenecks. By introducing a state variable to track historical hyper-gradient information and utilizing a recursive update rule, FSLA achieves a true single-loop structure. Theoretically, FSLA maintains a competitive $O(\epsilon^{-2})$ convergence rate. Empirically, it significantly outperforms traditional methods like Back-propagation through time (BP) and Conjugate Gradient (CG) in wall-clock efficiency.
Introduction
Bilevel optimization involves an outer optimization task that depends on the optimal solution of an inner task. Calculating the hyper-gradient—the gradient of the outer objective with respect to outer variables—traditionally requires solving the inner problem to completion or computing a computationally expensive Hessian inverse. While some "single-loop" algorithms exist, they often rely on hidden sub-loops to approximate these gradients.
FSLA addresses this by reusing information from previous iterations. Instead of recomputing the hyper-gradient from scratch, the algorithm maintains a state variable $v_k$ that evolves alongside the inner and outer variables. This structure avoids redundant computations and eliminates the need for explicit Hessian matrix inversion.
Methods
The Unified Framework
The authors first establish a theoretical unification of three classic hyper-gradient approximation methods: Back-propagation through time (BP), Neumann Series (NS), and Conjugate Gradient (CG). They demonstrate that these methods share a common mathematical structure, allowing for a generalized formulation of hyper-gradient convergence.
The FSLA Algorithm
Building on this unification, FSLA introduces three key innovations:
- Incremental Updates: Each iteration performs exactly one step for the inner variable, one for the outer variable, and one for the state variable $v_k$.
- Hessian-Inverse Free: A recursive update rule for $v_k$ bypasses the need for Hessian inversion, utilizing only matrix-vector products.
- Variance Reduction: To ensure stability in non-convex settings, FSLA incorporates momentum-based variance reduction (similar to the STORM optimizer).
Experimental Evaluation
Datasets and Tasks
FSLA was validated on a synthetic quadratic dataset to verify theoretical convergence and on hyper data-cleaning tasks using MNIST, Fashion-MNIST, and QMNIST. In data cleaning, the model learns to weight training samples to minimize the impact of corrupted labels.
Key Results
- Theoretical Convergence: FSLA converges at a rate of $O(1/\sqrt{K})$, translating to a sample complexity of $O(\epsilon^{-2})$ for non-convex-strongly-convex problems.
- Empirical Speedup: FSLA demonstrates superior wall-clock efficiency. In data-cleaning experiments, it reached lower validation losses significantly faster than BP or CG variants. For instance, FSLA outperformed BP-201 (which uses 201 inner steps) while maintaining a much lower per-iteration cost.
- Memory Efficiency: By avoiding the storage of large Hessian matrices or extensive back-propagation paths, FSLA is highly suitable for memory-constrained environments.
Discussion and Limitations
Information Reuse
The core strength of FSLA lies in treating hyper-gradient evaluation as a dynamical system. By "remembering" progress through the state $v_k$, the algorithm reaches the correct descent direction faster than methods that restart the approximation at every outer step. While FSLA may require more iterations than deep inner-loop methods to reach a specific accuracy, its $O(1)$ per-iteration cost makes it the clear winner in total running time.
Limitations
Currently, the theoretical proofs for FSLA rely on the strong convexity of the inner problem. While common in literature, many deep learning problems are only weakly convex. Additionally, like other momentum-based methods, FSLA introduces hyperparameters that may require tuning for specific architectures. Future work will explore extending this fully single-loop logic to non-convex inner problems and complex structures like those in reinforcement learning.
Summary updated