Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization

This paper studies the complexity of finding an ε-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, F2SA, achieving the tildeO(ε-6) upper complexity bound for first-order smooth problems. This is slower than the optimal Omega(ε-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 first reformulate F2SA as approximating the hyper-gradient with a forward difference. Based on this observation, we propose a class of methods F2SA-p that uses pth-order finite difference for hyper-gradient approximation and improves the upper bound to tildeO(p ε-4-p/2) for pth-order smooth problems. Finally, we demonstrate that the Omega(ε-4) lower bound also holds for stochastic bilevel problems when the high-order smoothness holds for the lower-level variable, indicating that the upper bound of F2SA-p is nearly optimal in the highly smooth region p = Omega( log ε-1 / log log ε-1).