LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909512082915328 |
|---|---|
| author | Yang, Yan Gao, Bin Yuan, Ya-xiang |
| author_facet | Yang, Yan Gao, Bin Yuan, Ya-xiang |
| contents | 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}(ε^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03331 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace Yang, Yan Gao, Bin Yuan, Ya-xiang Optimization and Control Machine Learning 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}(ε^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks. |
| title | LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2404.03331 |