Optimal Stochastic Bilevel Optimization with First-Order Oracles
Pan and Yang study stochastic nonconvex–strongly-convex bilevel optimization when only unbiased stochastic gradient estimates are available. They propose MRT-FD, a single-loop algorithm that simultaneously tracks the upper-level variable, lower-level solution, and an auxiliary response variable, using order-$p$ finite differences to reconstruct hypergradient actions from first-order queries. For lower-level objectives with order-$p$ smoothness, the method achieves $\mathcal{O}(\varepsilon^{-4-2/p})$ oracle complexity, and the authors prove a matching $\Omega(\varepsilon^{-4-2/p})$ lower bound, settling the optimal $\varepsilon$-dependence for any fixed finite $p$.
The paper makes a crisp theoretical contribution: it sharpens both the upper and lower complexity bounds for first-order stochastic bilevel optimization under order-$p$ lower-variable smoothness, and the single-loop MRT-FD algorithm removes logarithmic factors relative to prior work. However, the lower bound is explicitly constructed only for scalar lower-level variables, and the practical value of the finite-difference hypergradient approximation remains unevaluated because no experiments are provided.
The algorithmic design is transparent and the analysis is carefully executed. The Lyapunov function in Appendix A couples objective descent with the tracking errors of $y_k$ and $z_k$ while controlling finite-difference bias and stochastic variance in closed form. The bias–variance tradeoff is sharp: choosing $\tau = (\varepsilon^2/(3C_\star))^{1/(2p)}$ yields $\mathcal{O}(\tau^{2p}) = \mathcal{O}(\varepsilon^2)$ bias with $\mathcal{O}(\tau^{-2})$ variance amplification, which the batch size $m$ exactly cancels. The lower-bound construction adapts the randomized nonconvex chain of Arjevani et al. to bilevel problems through sinusoidal coupling, preserving the required smoothness while attenuating the signal by $\delta = \varepsilon^{1/p}$.
Several limitations temper the contributions. First, the lower bound is proved only for scalar lower-level variables ($d_y=1$) and very high outer dimension $d_x = \mathcal{O}(\varepsilon^{-6-2/p}\log(1/\varepsilon))$, so its generality to practical settings with multidimensional lower problems is unclear. Second, the hard instance automatically has an infinitely smooth upper-level objective $f_\delta(x,y)=A(x)+y$, meaning the lower bound does not test whether the improved rate truly requires only $g$-smoothness or whether $f$-smoothness is implicitly needed.
Third, the constant $C_\star$ in Theorem 3.1 depends on $p$ in an unspecified manner, and because the Lyapunov constants grow with the stencil order and the projection radius $R_z=4B_f/\mu$, the hidden prefactors in the $\mathcal{O}(\varepsilon^{-4-2/p})$ bound could be large.
The evidence for the upper bound is a rigorous three-timescale stochastic approximation analysis in Appendix A, and the finite-difference estimator is well grounded in classical numerical analysis. Comparisons are mostly accurate: the paper correctly notes that Chen et al. (2026b) require higher-order smoothness on both $f$ and $g$, whereas MRT-FD needs it only for $g$, and I verified via the source that Chen et al. indeed report $\tilde{\mathcal{O}}(p\epsilon^{-4-2/p})$. However, the paper does not benchmark against the concurrent condition-number-dependent lower bounds of Chen et al. (2026a) and Gu et al. (2026a), which study a complementary regime; readers might conflate optimal $\varepsilon$-dependence with optimal joint $(\varepsilon,\kappa)$-dependence.
Algorithm 1 is fully explicit, including stepsizes $(\eta_x,\eta_y,\eta_z)$, projection radius $R_z=4B_f/\mu$, and the parameter rule $(\tau,m,K)$ in Equation (17). Yet independent reproduction is hindered by the absence of code, data, or even pseudocode for the lower-bound construction, and by the fact that the complete lower-bound proof resides in Appendix B, which is only referenced and not sufficiently sketched in the main text to verify the comparison-oracle argument. Moreover, no numerical experiments are provided to validate the predicted $\varepsilon$-scaling or the practical impact of the finite-difference stencil order on variance.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.