Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization
arXiv:2509.02937v2 Announce Type: replace-cross Abstract: This paper studies the complexity of finding an $epsilon$-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, F${}^2$SA, achieving the $tilde{mathcal{O}}(epsilon^{-6})$ upper complexity bound for first-order smooth problems. This is slower than the optimal $Omega(epsilon^{-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 […]