# Lower Bounds and Accelerated Algorithms for Bilevel Optimization

arXiv: https://arxiv.org/abs/2102.03926 · HTML: https://mlsanity.com/paper/2102.03926/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 61 references that are in the map.
- First posted on arXiv 7 Feb 2021.

## Builds on (most cited first, 30 of 33)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms](https://mlsanity.com/paper/1908.10400/) (2019)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Hyper-Parameter Optimization: A Review of Algorithms and Applications](https://mlsanity.com/paper/2003.05689/) (2020)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [MiLeNAS: Efficient Neural Architecture Search via Mixed-Level Reformulation](https://mlsanity.com/paper/2003.12238/) (2020)
- [Deep Bilevel Learning](https://mlsanity.com/paper/1809.01465/) (2018)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [Penalty Method for Inversion-Free Deep Bilevel Optimization](https://mlsanity.com/paper/1911.03432/) (2019)
- [Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2002.07836/) (2020)
- [Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee](https://mlsanity.com/paper/2009.00690/) (2020)

## Built on by (most cited first, 30 of 46)

- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Stability and Generalization of Bilevel Programming in Hyperparameter Optimization](https://mlsanity.com/paper/2106.04188/) (2021)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [Value-Function-based Sequential Minimization for Bi-level Optimization](https://mlsanity.com/paper/2110.04974/) (2021)
- [Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction](https://mlsanity.com/paper/2205.01608/) (2022)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (2023)
- [Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy](https://mlsanity.com/paper/2405.09927/) (2024)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [Value Function Based Difference-of-Convex Algorithm for Bilevel Hyperparameter Selection Problems](https://mlsanity.com/paper/2206.05976/) (2022)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima](https://mlsanity.com/paper/2203.01123/) (2022)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)
- [Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems](https://mlsanity.com/paper/2302.06701/) (2023)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)

## Abstract (arXiv)

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 widetildeOmega(frac1√μxμy) and widetilde Omegabig(frac1√εminfrac1μy,frac1√ε3big) 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.