mlsanityData to 14 Oct 2026

Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

arXiv 2405.00914 ↗First posted 1 May 2024math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

80 of 122 references.

References · 80

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2022Generative Adversarial Networkscited by 5,627
  3. 2019Invariant Risk Minimizationcited by 1,854
  4. 2018DARTS: Differentiable Architecture Searchcited by 1,798
  5. 2016Neural Architecture Search with Reinforcement Learningcited by 1,499
  6. 2020Meta-Learning in Neural Networks: A Surveycited by 950
  7. 2014Convex Optimization: Algorithms and Complexitycited by 575
  8. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  9. 2019Meta-Learning with Implicit Gradientscited by 525
  10. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  11. 2018Meta-learning with differentiable closed-form solverscited by 397
  12. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
38 more
  1. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
  2. 2017How to Escape Saddle Points Efficientlycited by 285
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  4. 2018Approximation Methods for Bilevel Programmingcited by 236
  5. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  6. 2016Hyperparameter optimization with approximate gradientcited by 233
  7. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  8. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
  9. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  10. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  11. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  12. 2017Lower Bounds for Finding Stationary Points Icited by 126
  13. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  14. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 112
  15. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  16. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  17. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  18. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
  19. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  20. 2022Amortized Inference for Causal Structure Learningcited by 90
  21. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  22. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 79
  23. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  24. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  25. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  26. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  27. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  28. 2021Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyondcited by 63
  29. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 63
  30. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 60
  31. 2021A Value-Function-based Interior-point Method for Non-convex Bi-level Optimizationcited by 60
  32. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
  33. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  34. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  35. 2021iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradientscited by 51
  36. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  37. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  38. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45

50 most cited of 80 All 80 (JSON)

Built on by

Not cited yet.