# Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization

arXiv: https://arxiv.org/abs/2509.02937 · HTML: https://mlsanity.com/paper/2509.02937/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 63 references that are in the map.
- First posted on arXiv 3 Sep 2025.

## Builds on (most cited first, 30 of 48)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selection](https://mlsanity.com/paper/2410.07471/) (2024)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [First-order penalty methods for bilevel optimization](https://mlsanity.com/paper/2301.01716/) (2023)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweighting](https://mlsanity.com/paper/2406.19976/) (2024)

## Built on by (most cited first, 1 of 1)

- [Optimal Stochastic Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2610.01843/) (2026)

## Abstract (arXiv)

This paper studies the complexity of finding an ε-stationary point for stochastic bilevel optimization when the upper-level problem is nonconvex and the lower-level problem is strongly convex. Recent work proposed the first-order method, F2SA, achieving the tildeO(ε-6) upper complexity bound for first-order smooth problems. This is slower than the optimal Omega(ε-4) complexity lower bound in its single-level counterpart. In this work, we show that faster rates are achievable for higher-order smooth problems. We first reformulate F2SA as approximating the hyper-gradient with a forward difference. Based on this observation, we propose a class of methods F2SA-p that uses pth-order finite difference for hyper-gradient approximation and improves the upper bound to tildeO(p ε-4-p/2) for pth-order smooth problems. Finally, we demonstrate that the Omega(ε-4) lower bound also holds for stochastic bilevel problems when the high-order smoothness holds for the lower-level variable, indicating that the upper bound of F2SA-p is nearly optimal in the highly smooth region p = Omega( log ε-1 / log log ε-1).