mlsanityData to 7 Oct 2026

A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization

arXiv 2302.08766 ↗First posted 17 Feb 2023stat.ML cs.LG math.OCcited by 16

Not on the map. Why?

Abstract (arXiv)

Bilevel optimization problems, which are problems where two optimization problems are nested, have more and more applications in machine learning. In many practical cases, the upper and the lower objectives correspond to empirical risk minimization problems and therefore have a sum structure. In this context, we propose a bilevel extension of the celebrated SARAH algorithm. We demonstrate that the algorithm requires O((n+m)frac12varepsilon-1) oracle calls to achieve varepsilon-stationarity with n+m the total number of samples, which improves over all previous bilevel algorithms. Moreover, we provide a lower bound on the number of oracle calls required to get an approximate stationary point of the objective function of the bilevel problem. This lower bound is attained by our algorithm, making it optimal in terms of sample complexity.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 42 of its 66 references that are in the map. First posted on arXiv 17 Feb 2023.

Builds on

42 of 66 references.

References · 42

  1. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2019Deep Equilibrium Modelscited by 603
  5. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  6. 2019Meta-Learning with Implicit Gradientscited by 523
  7. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  8. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  9. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  10. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  11. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  12. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
30 more
  1. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  2. 2016Hyperparameter optimization with approximate gradientcited by 231
  3. 2018Approximation Methods for Bilevel Programmingcited by 231
  4. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  5. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  6. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  7. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  8. 2017Lower Bounds for Finding Stationary Points Icited by 125
  9. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  10. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  11. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  12. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  13. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 97
  14. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  15. 2020DADA: Differentiable Automatic Data Augmentationcited by 57
  16. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  17. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  18. 2021iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradientscited by 51
  19. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  20. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  21. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 33
  22. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  23. 2022Benchopt: Reproducible, efficient and collaborative optimization benchmarkscited by 27
  24. 2021SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit modelscited by 26
  25. 2020Super-efficiency of automatic differentiation for functions defined as a minimumcited by 24
  26. 2021CADDA: Class-wise Automatic Differentiable Data Augmentation for EEG Signalscited by 22
  27. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 19
  28. 2014A Lower Bound for the Optimization of Finite Sumscited by 13
  29. 2022Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximizationcited by 11
  30. 2016Fast Incremental Method for Nonconvex Optimizationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

16 papers.

Sort:

  1. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  2. 2024On the Complexity of First-Order Methods in Stochastic Bilevel Optimizationcited by 11
  3. 2024A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothnesscited by 7
  4. 2023BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimizationcited by 4
  5. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  6. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  7. 2024Differentially Private Bilevel Optimizationcited by 2
  8. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  9. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  10. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  11. 2023On the Communication Complexity of Decentralized Stochastic Bilevel Optimizationcited by 0
  12. 2024Derivatives of Stochastic Gradient Descent in parametric optimizationcited by 0
4 more
  1. 2025A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimizationcited by 0
  2. 2026Optimal Transport under Group Fairness Constraintscited by 0
  3. 2026Federated stochastic bilevel optimization with fully first-order gradientscited by 0
  4. 2026Optimal Stochastic Bilevel Optimization with First-Order Oraclescited by 0