ZOBA: An Efficient Single-loop Zeroth-order Bilevel Optimization Algorithm
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908798062428160 |
|---|---|
| author | Rando, Marco Vaiter, Samuel |
| author_facet | Rando, Marco Vaiter, Samuel |
| contents | 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 ({\it the hypergradient}). In several practical settings, however, first-order information is unavailable ({\it zeroth-order setting}), rendering these methods inapplicable. Finite-difference methods provide an alternative by approximating hypergradients using function evaluations along a set of directions. Nevertheless, such surrogates are notoriously expensive, and existing finite-difference bilevel methods rely on two-loop algorithms that are poorly parallelizable. In this work, we propose ZOBA, the first finite-difference single-loop algorithm for bilevel optimization. Our method leverages finite-difference hypergradient approximations based on delayed information to eliminate the need for nested loops. We analyze the proposed algorithm and establish convergence rates in the non-convex setting, achieving a complexity of $\mathcal{O}(p(d + p)^2\varepsilon^{-2})$, where $p$ and $d$ denote the dimension of inner and outer spaces respectively, which is better than prior approaches based on Hessian approximation. We further introduce and analyze HF-ZOBA, a Hessian-free variant that yields additional complexity improvements. 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 less computation time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21836 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | ZOBA: An Efficient Single-loop Zeroth-order Bilevel Optimization Algorithm Rando, Marco Vaiter, Samuel Optimization and Control 90C56 (Primary) 90C46, 90C15, 90C26, 90C30 (Secondary) 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 ({\it the hypergradient}). In several practical settings, however, first-order information is unavailable ({\it zeroth-order setting}), rendering these methods inapplicable. Finite-difference methods provide an alternative by approximating hypergradients using function evaluations along a set of directions. Nevertheless, such surrogates are notoriously expensive, and existing finite-difference bilevel methods rely on two-loop algorithms that are poorly parallelizable. In this work, we propose ZOBA, the first finite-difference single-loop algorithm for bilevel optimization. Our method leverages finite-difference hypergradient approximations based on delayed information to eliminate the need for nested loops. We analyze the proposed algorithm and establish convergence rates in the non-convex setting, achieving a complexity of $\mathcal{O}(p(d + p)^2\varepsilon^{-2})$, where $p$ and $d$ denote the dimension of inner and outer spaces respectively, which is better than prior approaches based on Hessian approximation. We further introduce and analyze HF-ZOBA, a Hessian-free variant that yields additional complexity improvements. 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 less computation time. |
| title | ZOBA: An Efficient Single-loop Zeroth-order Bilevel Optimization Algorithm |
| topic | Optimization and Control 90C56 (Primary) 90C46, 90C15, 90C26, 90C30 (Secondary) |
| url | https://arxiv.org/abs/2601.21836 |