mlsanityData to 7 Oct 2026

Approximation Methods for Bilevel Programming

arXiv 1802.02246 ↗First posted 6 Feb 2018math.OCcited by 231

Not on the map. Why?

Abstract (arXiv)

In this paper, we study a class of bilevel programming problem where the inner objective function is strongly convex. More specifically, under some mile assumptions on the partial derivatives of both inner and outer objective functions, we present an approximation algorithm for solving this class of problem and provide its finite-time convergence analysis under different convexity assumption on the outer objective function. We also present an accelerated variant of this method which improves the rate of convergence under convexity assumption. Furthermore, we generalize our results under stochastic setting where only noisy information of both objective functions is available. To the best of our knowledge, this is the first time that such (stochastic) approximation algorithms with established iteration complexity (sample complexity) are provided for bilevel programming.

Key facts. Cited by 231 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 25; 2022: 38; 2023: 41; 2024: 53; 2025: 35; 2026: 39.

231 papers.

Sort:

By area:

  1. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  2. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  3. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  4. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  5. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  6. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 97
  7. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  8. 2021Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimizationcited by 75
  9. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  10. 2024SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selectioncited by 64
  11. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  12. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
38 more
  1. 2022Advancing Model Pruning via Bi-level Optimizationcited by 55
  2. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  3. 2021iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradientscited by 51
  4. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 50
  5. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  6. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  7. 2023First-order penalty methods for bilevel optimizationcited by 40
  8. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  9. 2023An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learningcited by 39
  10. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  11. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  12. 2024ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweightingcited by 35
  13. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  14. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 33
  15. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 32
  16. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  17. 2021Stability and Generalization of Bilevel Programming in Hyperparameter Optimizationcited by 31
  18. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  19. 2022On Implicit Bias in Overparameterized Bilevel Optimizationcited by 30
  20. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  21. 2022Betty: An Automatic Differentiation Library for Multilevel Optimizationcited by 27
  22. 2022Gradient-based Bi-level Optimization for Deep Learning: A Surveycited by 26
  23. 2023Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexitycited by 26
  24. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  25. 2021Implicit differentiation for fast hyperparameter selection in non-smooth convex learningcited by 22
  26. 2022Alternating Differentiation for Optimization Layerscited by 22
  27. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  28. 2022Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecited by 21
  29. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  30. 2022Local Stochastic Bilevel Optimization with Momentum-Based Variance Reductioncited by 20
  31. 2024Functional Bilevel Optimization for Machine Learningcited by 20
  32. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  33. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  34. 2022Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-startcited by 17
  35. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  36. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
  37. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  38. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16

50 most cited of 231 All 231 (JSON)