Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces MRT-FD, a novel single-loop first-order method for nonconvex-strongly-convex bilevel optimization with stochastic oracles, which simultaneously updates the upper-level variable, lower-level solution, and implicit differentiation response. MRT-FD leverages order-$p$ finite differences to approximate second-order derivative actions, achieving an $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient query complexity for finding $\varepsilon$-stationary points. This complexity is proven to be optimal, matching a newly established $\Omega(\varepsilon^{-4-2/p})$ oracle lower bound and closing the gap in stochastic first-order bilevel optimization.
Optimal $\mathcal{O}(\varepsilon^{-4-2/p})$ convergence for stochastic bilevel optimization is achieved with a single-loop first-order method, matching a new lower bound.
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 $p\ge1$ in the lower-level variable, MRT-FD finds an $\varepsilon$-stationary point using $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient queries. We also prove a matching $\Omega(\varepsilon^{-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 $\varepsilon$ is optimal for every fixed finite $p$, closing the upper--lower complexity gap in this stochastic first-order oracle setting.