Provably Faster Algorithms for Bilevel Optimization

Abstract

Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve bilevel optimization problems faster. However, those momentum-based algorithms do not achieve provably better computational complexity than $\tilde{\mathcal{O}}({\epsilon }^{-2})$ of the SGD-based algorithm. In this paper, we propose two new algorithms for bilevel optimization, where the first algorithm adopts momentum-based recursive iterations, and the second algorithm adopts recursive gradient estimations in nested loops to decrease the variance. We show that both algorithms achieve the complexity of $\tilde{\mathcal{O}}({\epsilon }^{-1.5})$, which outperforms all existing algorithms by the order of magnitude. Our experiments validate our theoretical results and demonstrate the superior empirical performance of our algorithms in hyperparameter applications.

This paper is accepted in NeurIPS 2021

References in corpus (6)

• On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• On the Iteration Complexity of Hypergradient Computation
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence

Cited by in corpus (6)

• Lower Bounds and Accelerated Algorithms for Bilevel Optimization
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• Enhanced Bilevel Optimization via Bregman Distance
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization