Provably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning

Kaiyi Ji, Junjie Yang, Yingbin Liang

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 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.

Introduction

Bilevel optimization is a hierarchical framework where one optimization problem (the upper-level) is nested within another (the lower-level). In machine learning, this structure is common in meta-learning (finding a global initialization), hyperparameter optimization (tuning model parameters), and reinforcement learning. Despite its power, bilevel optimization is computationally challenging because the upper-level gradient, or "hypergradient," depends on the solution to the lower-level problem. This often requires differentiating through the entire inner optimization path.

This research addresses the "nonconvex-strongly-convex" setting, where the outer problem is nonconvex and the inner problem is strongly convex. The goal is to bridge the gap between theoretical convergence guarantees and the practical efficiency of algorithms like Approximate Implicit Differentiation (AID) and Iterative Differentiation (ITD).

Methodology and Algorithm Design

The paper introduces several key theoretical and algorithmic advancements:

Refined Deterministic Analysis

The authors analyze AID and ITD methods, introducing a warm-start strategy. By starting the inner loop from the previous iteration's solution, the algorithm effectively "tracks" the optimal inner solution, which improves theoretical complexity. They prove that a constant number of inner-loop steps is sufficient for convergence, aligning theory with common engineering practices.

First ITD Convergence Rate

While ITD (backpropagating through the optimization path) is widely used, its non-asymptotic convergence rate was previously unknown. This work establishes the first such rate, providing a quantitative comparison showing that AID is generally more efficient than ITD by a factor related to the condition number ($\kappa$).

stocBiO: Stochastic Bilevel Optimizer

For large-scale datasets, the authors propose stocBiO. This algorithm utilizes a Neumann series to estimate hypergradients efficiently, relying on Jacobian-vector and Hessian-vector products rather than costly matrix inversions.

The stocBiO algorithm framework, illustrating the inner-loop SGD updates and the outer-loop hypergradient estimation using Jacobian-vector products.

Experimental Evaluation

The proposed methods were evaluated on standard benchmarks for meta-learning and hyperparameter optimization (HPO).

Meta-Learning Performance

Experiments on miniImageNet and FC100 (5-way 5-shot classification) demonstrated that the "AID-BiO-constant" method converges faster and achieves higher test accuracy than popular baselines like MAML and ANIL. It also proved more robust when the number of inner-loop steps was increased.

Performance comparison on the miniImageNet dataset. AID-BiO variants demonstrate faster convergence and higher accuracy compared to MAML and ANIL baselines.

Sample Efficiency and Speed

In HPO tasks using the 20 Newsgroups and MNIST datasets, stocBiO significantly outperformed existing stochastic methods like BSA and TTSA. The algorithm's sample efficiency allows it to reach optimal test accuracy much faster, improving the dependence on target accuracy ($\epsilon$) by a factor of $1/\sqrt{\epsilon}$ over previous state-of-the-art methods.

Conclusion

This work provides a major upgrade to the theoretical foundation of bilevel optimization. By establishing the first convergence rates for ITD and introducing the highly efficient stocBiO algorithm, the authors demonstrate that bilevel optimization can be both provably fast and practically superior for complex tasks like meta-learning. Future work may extend these findings to settings where the lower-level problem is not strongly convex, such as deep inner-loop architectures.

Summary updated

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 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.
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},
}
Figure