Optimal Stochastic Bilevel Optimization with First-Order Oracles

arXiv:2610.01843v1 Announce Type: cross Abstract: 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 upper-level 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 pge1 in the lower-level variable, MRT-FD finds an arepsilon-stationary point using O(arepsilon^{-4-2/p}) stochastic gradient queries. We also prove a matching Omega(arepsilon^{-4-2/p}) oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on arepsilon is optimal for every fixed finite p, closing the upper--lower complexity gap in this stochastic first-order oracle setting.

Source: arXiv cs.LG | 2026-10-02