mlsanityData to 14 Oct 2026

Accelerating Inexact HyperGradient Descent for Bilevel Optimization

arXiv 2307.00126 ↗First posted 30 Jun 2023math.OC cs.LG stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We present a method for solving general nonconvex-strongly-convex bilevel optimization problems. Our method -- the Restarted Accelerated HyperGradient Descent (textttRAHGD) method -- finds an ε-first-order stationary point of the objective with tildeO(kappa3.25ε-1.75) oracle complexity, where kappa is the condition number of the lower-level objective and ε is the desired accuracy. We also propose a perturbed variant of textttRAHGD for finding an big(ε,O(kappa2.5√ε,)big)-second-order stationary point within the same order of oracle complexity. Our results achieve the best-known theoretical guarantees for finding stationary points in bilevel optimization and also improve upon the existing upper complexity bound for finding second-order stationary points in nonconvex-strongly-concave minimax optimization problems, setting a new state-of-the-art benchmark. Empirical studies are conducted to validate the theoretical results in this paper.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 30 of its 54 references that are in the map. First posted on arXiv 30 Jun 2023.

Builds on

30 of 54 references.

References · 30

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2022Generative Adversarial Networkscited by 5,627
  3. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  4. 2018Meta-learning with differentiable closed-form solverscited by 397
  5. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
  6. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 289
  7. 2017How to Escape Saddle Points Efficientlycited by 285
  8. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  9. 2018Approximation Methods for Bilevel Programmingcited by 236
  10. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  11. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  12. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
18 more
  1. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  2. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  3. 2017Lower Bounds for Finding Stationary Points Icited by 126
  4. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  5. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  6. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  7. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
  8. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  9. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  10. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  11. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  12. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45
  13. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  14. 2020A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distancecited by 27
  15. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  16. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  17. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  18. 2020Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separationcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 9; 2025: 3; 2026: 2.

15 papers.

Sort:

By area:

  1. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  2. 2024Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategycited by 16
  3. 2024Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimizationcited by 11
  4. 2024Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexitycited by 10
  5. 2024A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraintscited by 7
  6. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 5
  7. 2023An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learningcited by 4
  8. 2024LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspacecited by 4
  9. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 3
  10. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  11. 2026Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementationcited by 1
  12. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
3 more
  1. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  2. 2025A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimizationcited by 0
  3. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0