mlsanityData to 14 Oct 2026

Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

arXiv 2306.14853 ↗First posted 26 Jun 2023math.OC cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

In this work, we consider bilevel optimization when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product (HVP) oracle, one can provably find an ε-stationary point within O(ε-2) oracle calls. However, the HVP oracle may be inaccessible or expensive in practice. Kwon et al. (ICML 2023) addressed this issue by proposing a first-order method that can achieve the same goal at a slower rate of tildeO(ε-3). In this paper, we incorporate a two-time-scale update to improve their method to achieve the near-optimal tilde O(ε-2) first-order oracle complexity. Our analysis is highly extensible. In the stochastic setting, our algorithm can achieve the stochastic first-order oracle complexity of tilde O(ε-4) and tilde O(ε-6) when the stochastic noises are only in the upper-level objective and in both level objectives, respectively. When the objectives have higher-order smoothness conditions, our deterministic method can escape saddle points by injecting noise, and can be accelerated to achieve a faster rate of tilde O(ε-1.75) using Nesterov's momentum.

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

Builds on

98 of 141 references.

References · 98

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  3. 2018DARTS: Differentiable Architecture Searchcited by 1,798
  4. 2016Neural Architecture Search with Reinforcement Learningcited by 1,499
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  6. 2018On First-Order Meta-Learning Algorithmscited by 1,018
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  8. 2018Learning to Reweight Examples for Robust Deep Learningcited by 675
  9. 2016Learning to learn by gradient descent by gradient descentcited by 620
  10. 2014Convex Optimization: Algorithms and Complexitycited by 575
  11. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  12. 2019Meta-Learning with Implicit Gradientscited by 525
38 more
  1. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  2. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  3. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  5. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 304
  6. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 289
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  8. 2017How to Escape Saddle Points Efficientlycited by 285
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  10. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  11. 2018Approximation Methods for Bilevel Programmingcited by 236
  12. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  13. 2016Hyperparameter optimization with approximate gradientcited by 233
  14. 2019Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluationcited by 230
  15. 2018The Convergence of Sparsified Gradient Methodscited by 229
  16. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  17. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
  18. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  19. 2018Truncated Back-propagation for Bilevel Optimizationcited by 190
  20. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
  21. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  22. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  23. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
  24. 2019On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithmscited by 132
  25. 2017Lower Bounds for Finding Stationary Points Icited by 126
  26. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  27. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  28. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  29. 2019Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functionscited by 105
  30. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  31. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
  32. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  33. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  34. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  35. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  36. 2018Byzantine Stochastic Gradient Descentcited by 81
  37. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 79
  38. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78

50 most cited of 98 All 98 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 7; 2026: 8.

17 papers.

Sort:

By area:

  1. 2024ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweightingcited by 37
  2. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
  3. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  4. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  5. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 3
  6. 2024Differentially Private Bilevel Optimizationcited by 2
  7. 2025Computational Budget Should Be Considered in Data Selectioncited by 2
  8. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  9. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1
  10. 2025A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimizationcited by 0
  11. 2026Fully First-Order Algorithms for Online Bilevel Optimizationcited by 0
  12. 2026Bilevel Optimization of Synthetic Trajectories for Multi-Turn LLM Fine-Tuningcited by 0
5 more
  1. 2026Sharper Analysis of Single-Loop Methods for Bilevel Optimizationcited by 0
  2. 2026To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationaritycited by 0
  3. 2026ABO-Med: Accelerated Bilevel Optimization for Few-Shot Medical Image Classificationcited by 0
  4. 2026Optimal Stochastic Bilevel Optimization with First-Order Oraclescited by 0
  5. 2026Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomizationcited by 0