Bilevel Optimization: Convergence Analysis and Enhanced Design

By Kaiyi Ji, Junjie Yang, Yingbin Liang. International Conference on Machine Learning, 2020

366 citations recorded by the source corpus.

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 convergence rate 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 convergence rate 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 convergence rate guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect to the condition number $\kappa$ and the target accuracy $\epsilon$. We further validate our theoretical results and demonstrate the efficiency of bilevel optimization algorithms by the experiments on meta-learning and hyperparameter optimization.

Subfields: Finance

View Paper: https://www.semanticscholar.org/paper/51501cfe17a784fcb3610f235e97b0ee1738988c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Finance

1. Marco Cuturi
2. Aryan Mokhtari

Citations in the corpus

• Efficient and Modular Implicit Differentiation (2021, result): “While our guarantees concern the Jacobian of x (cid:63) ( θ ) , we note that other studies [47, 54, 13] give guarantees on hypergradients (i.e., the gradient of an outer objective).”
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, methodology): “In recent years, gradient-based methods for problem (3) have become increasingly popular including implicit differentiation (Domke, 2012; Pedregosa, 2016; Gould et al., 2016; Ji et al., 2021) and iterative differentiation (Maclaurin et al.”