  In this paper, we study the standard formulation of an optimization problem
when the computation of gradient is not available. Such a problem can be
classified as a "black box" optimization problem, since the oracle returns only
the value of the objective function at the requested point, possibly with some
stochastic noise. Assuming convex, and increased smoothness of the objective
function, this paper provides a zero-order accelerated stochastic gradient
descent (ZO-AccSGD) method for solving this problem, which exploits the
increased smoothness information via kernel approximation. As theoretical
results, we show that the ZO-AccSGD algorithm proposed in this paper improves
the convergence results of state-of-the-art algorithms, namely the estimate of
iteration complexity. In addition, our theoretical analysis provides an
estimate of the maximum allowable noise level at which the desired accuracy can
be achieved. We validate the theoretical results with an example of optimizing
the negative logarithm of the likelihood function. We also provide a discussion
in which we explain the results obtained and the superiority of the proposed
algorithm over SOTA algorithms for solving the original problem.
