LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace
<|reference_start|>LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace: Bilevel optimization, with broad applications in machine learning, has an intricate hierarchical structure. Gradient-based methods have emerged as a common approach to large-scale bilevel problems. However, the computation of the hyper-gradient, which involves a Hessian inverse vector product, confines the efficiency and is regarded as a bottleneck. To circumvent the inverse, we construct a sequence of low-dimensional approximate Krylov subspaces with the aid of the Lanczos process. As a result, the constructed subspace is able to dynamically and incrementally approximate the Hessian inverse vector product with less effort and thus leads to a favorable estimate of the hyper-gradient. Moreover, we propose a~provable subspace-based framework for bilevel problems where one central step is to solve a small-size tridiagonal linear system. To the best of our knowledge, this is the first time that subspace techniques are incorporated into bilevel optimization. This successful trial not only enjoys $\mathcal{O}(\epsilon^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks.<|reference_end|>
@article{gao2024lancbio:,
    title={LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace},
    author={Bin Gao, Yan Yang, Ya-xiang Yuan},
    journal={arXiv preprint arXiv:2404.03331},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03331},
    primaryClass={math.OC cs.LG stat.ML}
}