mlsanityData to 7 Oct 2026

On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis

arXiv 2301.00712 ↗First posted 2 Jan 2023math.OC cs.AI cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

Bilevel optimization reveals the inner structure of otherwise oblique optimization problems, such as hyperparameter tuning, neural architecture search, and meta-learning. A common goal in bilevel optimization is to minimize a hyper-objective that implicitly depends on the solution set of the lower-level function. Although this hyper-objective approach is widely used, its theoretical properties have not been thoroughly investigated in cases where the lower-level functions lack strong convexity. In this work, we first provide hardness results to show that the goal of finding stationary points of the hyper-objective for nonconvex-convex bilevel optimization can be intractable for zero-respecting algorithms. Then we study a class of tractable nonconvex-nonconvex bilevel problems when the lower-level function satisfies the Polyak-Lojasiewicz (PL) condition. We show a simple first-order algorithm can achieve better complexity bounds of tildeO(ε-2), tildeO(ε-4) and tildeO(ε-6) in the deterministic, partially stochastic, and fully stochastic setting respectively. The complexities in the first two cases are optimal up to logarithmic factors.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). Builds on 39 of its 69 references that are in the map. First posted on arXiv 2 Jan 2023.

Builds on

39 of 69 references.

References · 39

  1. 2022Generative Adversarial Networkscited by 5,603
  2. 2019Invariant Risk Minimizationcited by 1,832
  3. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  4. 2016Neural Architecture Search with Reinforcement Learningcited by 1,489
  5. 2020Meta-Learning in Neural Networks: A Surveycited by 944
  6. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  7. 2019Meta-Learning with Implicit Gradientscited by 523
  8. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  9. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  12. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
27 more
  1. 2016Hyperparameter optimization with approximate gradientcited by 231
  2. 2018Approximation Methods for Bilevel Programmingcited by 231
  3. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  4. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  5. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  6. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  7. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  8. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  9. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  10. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 108
  11. 2016Identity Matters in Deep Learningcited by 107
  12. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  13. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  14. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  15. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  16. 2021Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyondcited by 62
  17. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  18. 2021A Value-Function-based Interior-point Method for Non-convex Bi-level Optimizationcited by 60
  19. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  20. 2021iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradientscited by 51
  21. 2021Nonsmooth Implicit Differentiation for Machine Learning and Optimizationcited by 43
  22. 2022Invariant and Transportable Representations for Anti-Causal Domain Shiftscited by 37
  23. 2022Non-Convex Bilevel Games with Critical Point Selection Mapscited by 25
  24. 2022Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequalitycited by 19
  25. 2021ZARTS: On Zero-order Optimization for Neural Architecture Searchcited by 17
  26. 2022A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minimacited by 12
  27. 2021Quasi-Newton Methods for Saddle Point Problems and Beyondcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 16; 2026: 16.

39 papers.

Sort:

By area:

  1. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  2. 2024Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimizationcited by 10
  3. 2025On The Sample Complexity Bounds In Bilevel Reinforcement Learningcited by 10
  4. 2025Direct Prediction Set Minimization via Bilevel Conformal Classifier Trainingcited by 8
  5. 2024LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspacecited by 4
  6. 2025A First-order Generative Bilevel Optimization Framework for Diffusion Modelscited by 4
  7. 2024A Framework for Bilevel Optimization on Riemannian Manifoldscited by 3
  8. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  9. 2025Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimizationcited by 3
  10. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  11. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  12. 2025BLISS: A Lightweight Bilevel Influence Scoring Method for Data Selection in Language Model Pretrainingcited by 3
27 more
  1. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  2. 2025A Fully First-Order Layer for Differentiable Optimizationcited by 3
  3. 2024Differentially Private Bilevel Optimizationcited by 2
  4. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  5. 2024Functionally Constrained Algorithm Solves Convex Simple Bilevel Problemscited by 1
  6. 2025Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Ratescited by 1
  7. 2025On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimizationcited by 1
  8. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  9. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  10. 2026Oracle-Robust Online Alignment for Large Language Modelscited by 1
  11. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1
  12. 2026A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimizationcited by 1
  13. 2026DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexitycited by 1
  14. 2026On the Convergence of Self-Improving Online LLM Alignmentcited by 1
  15. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 0
  16. 2025Balancing Multi-modal Sensor Learning via Multi-objective Optimizationcited by 0
  17. 2025Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraintscited by 0
  18. 2026Sample Complexity Analysis for Constrained Bilevel Reinforcement Learningcited by 0
  19. 2026Fully First-Order Algorithms for Online Bilevel Optimizationcited by 0
  20. 2026On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiationcited by 0
  21. 2026Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithmcited by 0
  22. 2026Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimizationcited by 0
  23. 2026Sharper Analysis of Single-Loop Methods for Bilevel Optimizationcited by 0
  24. 2026Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexitycited by 0
  25. 2026Cross-View Correspondence Is a Measurement Intervention: Two-Sided Validation for Agent Evaluation and Credit Assignmentcited by 0
  26. 2026To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationaritycited by 0
  27. 2026Optimal Stochastic Bilevel Optimization with First-Order Oraclescited by 0