  In this paper, we consider a stochastic distributed nonconvex optimization
problem with the cost function being distributed over $n$ agents having access
only to zeroth-order (ZO) information of the cost. This problem has various
machine learning applications. As a solution, we propose two distributed ZO
algorithms, in which at each iteration each agent samples the local stochastic
ZO oracle at two points with a time-varying smoothing parameter. We show that
the proposed algorithms achieve the linear speedup convergence rate
$\mathcal{O}(\sqrt{p/(nT)})$ for smooth cost functions under the
state-dependent variance assumptions which are more general than the commonly
used bounded variance and Lipschitz assumptions, and $\mathcal{O}(p/(nT))$
convergence rate when the global cost function additionally satisfies the
Polyak--{\L}ojasiewicz (P--{\L}) condition in addition, where $p$ and $T$ are
the dimension of the decision variable and the total number of iterations,
respectively. To the best of our knowledge, this is the first linear speedup
result for distributed ZO algorithms, which enables systematic processing
performance improvements by adding more agents. We also show that the proposed
algorithms converge linearly under the relative bounded second moment
assumptions and the P--{\L} condition. We demonstrate through numerical
experiments the efficiency of our algorithms on generating adversarial examples
from deep neural networks in comparison with baseline and recently proposed
centralized and distributed ZO algorithms.
