A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse

Junyi Li, Bin Gu, Heng Huang

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:

  1. 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$.
  2. Hessian-Inverse Free: A recursive update rule for $v_k$ bypasses the need for Hessian inversion, utilizing only matrix-vector products.
  3. Variance Reduction: To ensure stability in non-convex settings, FSLA incorporates momentum-based variance reduction (similar to the STORM optimizer).
Convergence of the hyper-gradient approximation for FSLA compared to traditional methods and theoretical rates.

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.
Comparison of FSLA against Back-propagation (BP) variants on validation loss over hyper-iterations and wall-clock time.

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

Abstract

In this paper, we propose a novel 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 not yet achieve 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, e.g. back-propagation through time, conjugate gradient, etc. Based on this formulation, we introduce a new state variable to maintain the 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. Finally, we verify the efficacy our algorithm empirically through multiple bilevel optimization based machine learning tasks. A long version of this paper can be found in: https://arxiv.org/abs/2112.04660.
BibTeX
@inproceedings{li2022fully,
  author = {Junyi Li and Bin Gu and Heng Huang},
  title = {{A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i7.20706},
}
Figure