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}(\epsilon^{-1.5})$ sample complexity of ${O}(\epsilon^{-1.5})$ 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}(\epsilon^{-1.5})$ iterations
(each using ${O}(1)$ samples and only first-order gradient information) to find
an $\epsilon$-accurate stationary point. As far as we know, this is the first
Hessian/Jacobian-free method with an ${O}(\epsilon^{-1.5})$ sample complexity
for nonconvex-strongly-convex stochastic bilevel optimization.

本文提出了一种新的 Hessian/Jacobian-free 双层优化器 FdeHBO，通过每次迭代使用 O (1) 个样本和仅一阶梯度信息，在非凸 - 强凸随机双层优化中实现了 O (ε^(-1.5)) 样本复杂度，达到 ε- 精确的稳定点。