A Fully Single Loop Algorithm for Bilevel Optimization Without Hessian Inverse
Document Type
Article
Publication Title
arXiv
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 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 hypergradient 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 with the rate of O(ε−2). Finally, we verify the efficacy our algorithm empirically through multiple bilevel optimization based machine learning tasks. Copyright © 2021, The Authors. All rights reserved.
DOI
10.48550/arXiv.2112.04660
Publication Date
12-10-2021
Keywords
Back propagation through time; Bi-level optimization; Bilevel optimization problems; Classic algorithm; Double-loop; Gradients computation; Loop algorithms; Loop structure; Single loop; State-variables
Recommended Citation
J. Li, B. Gu, and H. Huang, "A fully single loop algorithm for bilevel optimization without hessian inverse," 2021, arXiv:2112.04660v2
Comments
Preprint: arXiv