Efficient Gradient-Based Methods for Bilevel Learning via Recycling Krylov Subspaces

Abstract. Many optimization problems require hyperparameters, i.e., parameters that must be prespecified in advance of their solution, such as regularization parameters and parametric regularizers in variational regularization methods for inverse problems and dictionaries in compressed sensing. A data-driven approach to determine appropriate hyperparameter values is via a nested optimization framework known as bilevel learning. Even when it is possible to employ a gradient-based solver to the bilevel optimization problem, construction of the gradients, known as hypergradients, is computationally challenging, each one requiring both a solution of a minimization problem and a linear system solve. These systems do not change much during the iterations, which motivates us to apply recycling Krylov subspace methods, wherein information from one linear system solve is reused to solve the next linear system. Existing recycling strategies often employ eigenvector approximations called Ritz vectors. In this work, we propose a novel recycling strategy based on a new concept, Ritz generalized singular vectors, which acknowledge the bilevel setting. Additionally, while existing iterative methods primarily terminate according to the residual norm, the newly introduced Ritz generalized singular vectors allow us to define a new stopping criterion that directly approximates the error of the associated hypergradient. The proposed approach is validated through extensive numerical testing in the context of inverse problems in imaging. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/s-j-scott/bilevel-recycling and in the supplementary materials ( M171688_Supplementary_Materials_1.pdf [177KB], bilevel-recycling-main.zip [80.4MB]). [Formula: see text]