  We consider the minimization of an $L_0$-Lipschitz continuous and
expectation-valued function, denoted by $f$ and defined as $f(x)\triangleq
\mathbb{E}[\tilde{f}(x,\omega)]$, over a Cartesian product of closed and convex
sets with a view towards obtaining both asymptotics as well as rate and
complexity guarantees for computing an approximate stationary point (in a
Clarke sense). We adopt a smoothing-based approach reliant on minimizing
$f_{\eta}$ where $f_{\eta}(x) \triangleq \mathbb{E}_{u}[f(x+\eta u)]$, $u$ is a
random variable defined on a unit sphere, and $\eta > 0$. In fact, it is
observed that a stationary point of the $\eta$-smoothed problem is a
$2\eta$-stationary point for the original problem in the Clarke sense. In such
a setting, we derive a suitable residual function that provides a metric for
stationarity for the smoothed problem. By leveraging a zeroth-order framework
reliant on utilizing sampled function evaluations implemented in a
block-structured regime, we make two sets of contributions for the sequence
generated by the proposed scheme. (i) The residual function of the smoothed
problem tends to zero almost surely along the generated sequence; (ii) To
compute an $x$ that ensures that the expected norm of the residual of the
$\eta$-smoothed problem is within $\epsilon$ requires no greater than
$\mathcal{O}(\tfrac{1}{\eta \epsilon^2})$ projection steps and
$\mathcal{O}\left(\tfrac{1}{\eta^2 \epsilon^4}\right)$ function evaluations.
These statements appear to be novel and there appear to be few results to
contend with general nonsmooth, nonconvex, and stochastic regimes via
zeroth-order approaches.
