Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization

In this paper, we revisit the bilevel optimization problem, in which the upper-level objective function is generally nonconvex and the lower-level objective function is strongly convex. Although this type of problem has been studied extensively, it still remains an open question how to achieve an O(ε-1.5) sample complexity in Hessian/Jacobian-free stochastic bilevel optimization without any second-order derivative computation. To fill this gap, we propose a novel Hessian/Jacobian-free bilevel optimizer named FdeHBO, which features a simple fully single-loop structure, a projection-aided finite-difference Hessian/Jacobian-vector approximation, and momentum-based updates. Theoretically, we show that FdeHBO requires O(ε-1.5) iterations (each using O(1) samples and only first-order gradient information) to find an ε-accurate stationary point. As far as we know, this is the first Hessian/Jacobian-free method with an O(ε-1.5) sample complexity for nonconvex-strongly-convex stochastic bilevel optimization.