  In this paper, we study and analyze zeroth-order stochastic approximation
algorithms for solving bilvel problems, when neither the upper/lower objective
values, nor their unbiased gradient estimates are available. In particular,
exploiting Stein's identity, we first use Gaussian smoothing to estimate first-
and second-order partial derivatives of functions with two independent block of
variables. We then used these estimates in the framework of a stochastic
approximation algorithm for solving bilevel optimization problems and establish
its non-asymptotic convergence analysis. To the best of our knowledge, this is
the first time that sample complexity bounds are established for a fully
stochastic zeroth-order bilevel optimization algorithm.
