ZOBA: An Efficient Single-loop Zeroth-order Bilevel Optimization Algorithm

Bilevel optimization problems consist of minimizing a value function whose evaluation depends on the solution of an inner optimization problem. These problems are typically tackled using first-order methods that require computing the gradient of the value function (the \it hypergradient). In several practical settings, however, first-order information is unavailable, rendering these methods inapplicable. Finite-difference methods provide an alternative by approximating hypergradients using function evaluations along a set of directions. However, such surrogates are notoriously expensive, and most finite-difference bilevel approaches rely on two-loop algorithms that are poorly parallelizable. Recently, several works have proposed single-loop finite-difference methods enabling parallelization. However, to ensure stability, these methods require a large number of function evaluations per iteration, limiting their applicability in high-dimensional settings with limited evaluation budget. In this work, we propose ZOBA, an efficient finite-difference single-loop algorithm for bilevel optimization. Our method leverages hypergradient approximations based on delayed information and function values reusage to enable parallelization while limiting the per-iteration cost. We analyze the proposed algorithm and establish convergence rates in the non-convex setting, achieving a complexity of $\mathcal{O}(p(d+p{)}^2{\epsilon }^{-2})$, where $p$ and $d$ denote the dimensions of the inner and outer variables, respectively and $\epsilon \in (0,1)$ is the accuracy. This improves upon prior approaches based on Hessian approximation. We further introduce and analyze HF-ZOBA, a Hessian-free variant that yields optimal complexity. Finally, we corroborate our findings with numerical experiments on synthetic functions and a real-world black-box task in adversarial machine learning. Our results show that our methods achieve accuracy comparable to state-of-the-art techniques while requiring significantly less computation time.