Optimal Stochastic Bilevel Optimization with First-Order Oracles

We study nonconvex–strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the outer variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-$p$ finite differences. For any fixed finite smoothness order $p\ge 1$ in the lower variable, MRT-FD finds an $\epsilon$-stationary point using $\mathcal{O}({\epsilon }^{-4-2/p})$ stochastic gradient queries. We also prove a matching $\Omega ({\epsilon }^{-4-2/p})$ oracle lower bound. The lower-bound construction starts from a hard stochastic nonconvex chain under a stronger oracle and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on $\epsilon$ is optimal for every fixed finite $p$, closing the upper–lower complexity gap in this stochastic first-order oracle setting.