mlsanityData to 7 Oct 2026

First-Order Methods for Linearly Constrained Bilevel Optimization

arXiv 2406.12771 ↗First posted 18 Jun 2024math.OC cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained bilevel problems, the constrained setting remains relatively underexplored. We present first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear equality constraints, we attain ε-stationarity in widetildeO(ε-2) gradient oracle calls, which is nearly-optimal. For linear inequality constraints, we attain (δ,ε)-Goldstein stationarity in widetildeO(dδ-1 ε-3) gradient oracle calls, where d is the upper-level dimension. Finally, we obtain for the linear inequality setting dimension-free rates of widetildeO(δ-1 ε-4) oracle complexity under the additional assumption of oracle access to the optimal dual variable. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. We verify these guarantees with preliminary numerical experiments.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 62 of its 97 references that are in the map. First posted on arXiv 18 Jun 2024.

Builds on

62 of 97 references.

References · 62

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  4. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  5. 2019Deep Equilibrium Modelscited by 603
  6. 2017OptNet: Differentiable Optimization as a Layer in Neural Networkscited by 588
  7. 2019Meta-Learning with Implicit Gradientscited by 523
  8. 2019Meta-Learning with Differentiable Convex Optimizationcited by 461
  9. 2019Differentiable Convex Optimization Layerscited by 458
  10. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  11. 2018Meta-learning with differentiable closed-form solverscited by 395
  12. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
38 more
  1. 2017Smart "Predict, then Optimize"cited by 332
  2. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  3. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  4. 2016Hyperparameter optimization with approximate gradientcited by 231
  5. 2018Approximation Methods for Bilevel Programmingcited by 231
  6. 2018Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimizationcited by 220
  7. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  8. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  9. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  10. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  11. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  12. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 126
  13. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 108
  14. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  15. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  16. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
  17. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  18. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  19. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 97
  20. 2018Reviving and Improving Recurrent Back-Propagationcited by 69
  21. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  22. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  23. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  24. 2021A Value-Function-based Interior-point Method for Non-convex Bi-level Optimizationcited by 60
  25. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  26. 2023First-order penalty methods for bilevel optimizationcited by 40
  27. 2019Bi-level Actor-Critic for Multi-agent Coordinationcited by 38
  28. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  29. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 37
  30. 2019Penalty Method for Inversion-Free Deep Bilevel Optimizationcited by 33
  31. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 32
  32. 2022PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programmingcited by 32
  33. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 28
  34. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
  35. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
  36. 2021Difference of convex algorithms for bilevel programs with applications in hyperparameter selectioncited by 17
  37. 2022A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problemcited by 17
  38. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16

50 most cited of 62 All 62 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 6; 2026: 2.

10 papers.

  1. 2024CoBo: Collaborative Learning via Bilevel Optimizationcited by 5
  2. 2025A Fully First-Order Layer for Differentiable Optimizationcited by 3
  3. 2024Differentially Private Bilevel Optimizationcited by 2
  4. 2025Leveraging Machine Unlearning for Cost-Efficient Preference Alignmentcited by 2
  5. 2025Safe Gradient Flow for Bilevel Optimizationcited by 1
  6. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1
  7. 2025An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniquescited by 0
  8. 2025A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimizationcited by 0
  9. 2025Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraintscited by 0
  10. 2026Sample Complexity Analysis for Constrained Bilevel Reinforcement Learningcited by 0