Provably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning
Lists
Only you see this
Abstract
Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-convex bilevel optimization problem. For deterministic bilevel optimization, we provide a comprehensive finite-time convergence analysis for two popular algorithms respectively based on approximate implicit differentiation (AID) and iterative differentiation (ITD). For the AID-based method, we orderwisely improve the previous finite-time convergence analysis due to a more practical parameter selection as well as a warm start strategy, and for the ITD-based method we establish the first theoretical convergence rate. Our analysis also provides a quantitative comparison between ITD and AID based approaches. For stochastic bilevel optimization, we propose a novel algorithm named stocBiO, which features a sample-efficient hypergradient estimator using efficient Jacobian- and Hessian-vector product computations. We provide the finite-time convergence guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect to the condition number κ and the target accuracy ϵ. We further validate our theoretical results and demonstrate the efficiency of bilevel optimization algorithms by the experiments on meta-learning and hyperparameter optimization.
BibTeX
@misc{ji2020provably,
author = {Kaiyi Ji and Junjie Yang and Yingbin Liang},
title = {{Provably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning}},
year = {2020},
eprint = {2010.07962},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2010.07962},
}Loading related content...