Lower Bounds and Accelerated Algorithms for Bilevel Optimization

Abstract

Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. Although recent studies have characterized the convergence rate for several such popular algorithms, it is still unclear how much further these convergence rates can be improved. In this paper, we address this fundamental question from two perspectives. First, we provide the first-known lower complexity bounds of $\tilde{\Omega }(\frac{1}{\sqrt{{\mu }_x}{\mu }_y})$ and $\tilde{\Omega }(\frac{1}{\sqrt{\epsilon }}\min \{\frac{1}{{\mu }_y},\frac{1}{\sqrt{{\epsilon }^3}}\})$ respectively for strongly-convex-strongly-convex and convex-strongly-convex bilevel optimizations. Second, we propose an accelerated bilevel optimizer named AccBiO, for which we provide the first-known complexity bounds without the gradient boundedness assumption (which was made in existing analyses) under the two aforementioned geometries. We also provide significantly tighter upper bounds than the existing complexity when the bounded gradient assumption does hold. We show that AccBiO achieves the optimal results (i.e., the upper and lower bounds match up to logarithmic factors) when the inner-level problem takes a quadratic form with a constant-level condition number. Interestingly, our lower bounds under both geometries are larger than the corresponding optimal complexities of minimax optimization, establishing that bilevel optimization is provably more challenging than minimax optimization.

53 pages, 3 Table

References in corpus (11)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Bilevel Optimization: Convergence Analysis and Enhanced Design
• 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
• A Gradient-based Bilevel Optimization Approach for Tuning Hyperparameters in Machine Learning
• Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee
• Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians
• Provably Faster Algorithms for Bilevel Optimization
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization

Cited by in corpus (7)

• Communication-Efficient Robust Federated Learning with Noisy Labels
• A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization
• Enhanced Bilevel Optimization via Bregman Distance
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Stability and Generalization of Bilevel Programming in Hyperparameter Optimization
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Value-Function-based Sequential Minimization for Bi-level Optimization