mlsanityData to 7 Oct 2026

Efficiently Escaping Saddle Points in Bilevel Optimization

arXiv 2202.03684 ↗First posted 8 Feb 2022cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases. In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization. Specifically, we show that the perturbed approximate implicit differentiation (AID) with a warm start strategy finds ε-approximate local minimum of bilevel optimization in tildeO(ε-2) iterations with high probability. Moreover, we propose an inexact NEgative-curvature-Originated-from-Noise Algorithm (iNEON), a pure first-order algorithm that can escape saddle point and find local minimum of stochastic bilevel optimization. As a by-product, we provide the first nonasymptotic analysis of perturbed multi-step gradient descent ascent (GDmax) algorithm that converges to local minimax point for minimax problems.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 43 of its 80 references that are in the map. First posted on arXiv 8 Feb 2022.

Builds on

43 of 80 references.

References · 43

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  3. 2019Meta-Learning with Implicit Gradientscited by 523
  4. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  5. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  6. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  7. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
  8. 2017How to Escape Saddle Points Efficientlycited by 284
  9. 2014The Loss Surfaces of Multilayer Networkscited by 278
  10. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  11. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  12. 2016Hyperparameter optimization with approximate gradientcited by 231
31 more
  1. 2018Approximation Methods for Bilevel Programmingcited by 231
  2. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  3. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  4. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 108
  7. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  8. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  9. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  10. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  11. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  12. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  13. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  14. 2018Escaping Saddles with Stochastic Gradientscited by 66
  15. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  16. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  17. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  18. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  19. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45
  20. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  21. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  22. 2019On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Gamescited by 35
  23. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  24. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  25. 2020A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distancecited by 27
  26. 2019Efficiently escaping saddle points on manifoldscited by 24
  27. 2021Projection Robust Wasserstein Barycenterscited by 8
  28. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  29. 2017Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWUcited by 4
  30. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  31. 2021On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transportcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 6; 2024: 3; 2025: 5; 2026: 2.

19 papers.

Sort:

By area:

  1. 2023First-order penalty methods for bilevel optimizationcited by 40
  2. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  3. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  4. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  5. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  6. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  7. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  8. 2024Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomycited by 16
  9. 2023Accelerating Inexact HyperGradient Descent for Bilevel Optimizationcited by 15
  10. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  11. 2025Solving bilevel optimization via sequential minimax optimizationcited by 3
  12. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
7 more
  1. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  2. 2023Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learningcited by 1
  3. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  4. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  5. 2025Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validationcited by 0
  6. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimizationcited by 0
  7. 2026To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationaritycited by 0