Bi-ZOL: Bilevel Zeroth-Order Learning with Nonsmooth Responses
Abstract
This paper studies lower-level-constrained bilevel optimization in a response-oracle setting, where lower-level model information is unavailable and the induced response mapping is locally Lipschitz but potentially nonsmooth. In this setting, the classical response Jacobian and reduced hypergradient may fail to exist. We propose Bilevel Zeroth-Order Learning (Bi-ZOL), a structure-guided zeroth-order method for finding stationary points of the nonsmooth reduced problem. Instead of estimating the gradient of a fully smoothed reduced hyperobjective, Bi-ZOL separates the bilevel chain-rule structure: it keeps the exact upper-level partial gradients at the queried response and uses zeroth-order sampling only to estimate the response Jacobian. This construction yields an approximate hypergradient that is more directly aligned with the Clarke chain-rule subdifferential. We show that the Bi-ZOL direction admits a partial-smoothing interpretation, quantify its pointwise structural bias, and prove finite-time convergence to a (δ,ε)-Bi-ZOL Frank--Wolfe stationary point. The bias is O(δ) for piecewise C1,1 responses under local regularity and vanishes for piecewise affine responses on active-cell neighborhoods. Experiments on incentive-based tracking problems show that Bi-ZOL achieves smaller stationarity gaps and lower hyperobjective values than vanilla zeroth-order smoothing under comparable response-oracle budgets.
Related
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
- Observability as a constraint qualification for a nonsmooth bilevel PDE-constrained problem
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation
- Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds
BibTeX
@misc{jiang2026bizol,
title = {{Bi-ZOL: Bilevel Zeroth-Order Learning with Nonsmooth Responses}},
author = {Zhisen Jiang and Saverio Bolognani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08021},
eprint = {2609.08021},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08021},
}
RIS
TY - UNPB
TI - Bi-ZOL: Bilevel Zeroth-Order Learning with Nonsmooth Responses
AU - Zhisen Jiang
AU - Saverio Bolognani
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.08021
UR - https://arxiv.org/abs/2609.08021
AB - This paper studies lower-level-constrained bilevel optimization in a response-oracle setting, where lower-level model information is unavailable and the induced response mapping is locally Lipschitz but potentially nonsmooth. In this setting, the classical response Jacobian and reduced hypergradient may fail to exist. We propose Bilevel Zeroth-Order Learning (Bi-ZOL), a structure-guided zeroth-order method for finding stationary points of the nonsmooth reduced problem. Instead of estimating the gradient of a fully smoothed reduced hyperobjective, Bi-ZOL separates the bilevel chain-rule structure: it keeps the exact upper-level partial gradients at the queried response and uses zeroth-order sampling only to estimate the response Jacobian. This construction yields an approximate hypergradient that is more directly aligned with the Clarke chain-rule subdifferential. We show that the Bi-ZOL direction admits a partial-smoothing interpretation, quantify its pointwise structural bias, and prove finite-time convergence to a (δ,ε)-Bi-ZOL Frank--Wolfe stationary point. The bias is O(δ) for piecewise C^1,1 responses under local regularity and vanishes for piecewise affine responses on active-cell neighborhoods. Experiments on incentive-based tracking problems show that Bi-ZOL achieves smaller stationarity gaps and lower hyperobjective values than vanilla zeroth-order smoothing under comparable response-oracle budgets.
ER -