# Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 80 of its 122 references that are in the map.
- First posted on arXiv 1 May 2024.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [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)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [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)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [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)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [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)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)

## Abstract (arXiv)

We present in this paper novel accelerated fully first-order methods in Bilevel Optimization (BLO). Firstly, for BLO under the assumption that the lower-level functions admit the typical strong convexity assumption, the (Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation (textttPRAF2BA) algorithm leveraging fully first-order oracles is proposed, whereas the algorithm for finding approximate first-order and second-order stationary points with state-of-the-art oracle query complexities in solving complex optimization tasks. Secondly, applying as a special case of BLO the nonconvex-strongly-convex (NCSC) minimax optimization, textttPRAF2BA rediscovers perturbed restarted accelerated gradient descent ascent (textttPRAGDA) that achieves the state-of-the-art complexity for finding approximate second-order stationary points. Additionally, we investigate the challenge of finding stationary points of the hyper-objective function in BLO when lower-level functions lack the typical strong convexity assumption, where we identify several regularity conditions of the lower-level problems that ensure tractability and present hardness results indicating the intractability of BLO for general convex lower-level functions. Under these regularity conditions we propose the Inexact Gradient-Free Method (textttIGFM), utilizing the Switching Gradient Method (textttSGM) as an efficient sub-routine to find an approximate stationary point of the hyper-objective in polynomial time. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms.