Zeroth-order (derivative-free) optimization attracts a lot of attention in
machine learning, because explicit gradient calculations may be computationally
expensive or infeasible. To handle large scale problems both in volume and
dimension, recently asynchronous doubly stochastic zeroth-order algorithms were
proposed. The convergence rate of existing asynchronous doubly stochastic
zeroth order algorithms is $O(\frac{1}{\sqrt{T}})$ (also for the sequential
stochastic zeroth-order optimization algorithms). In this paper, we focus on
the finite sums of smooth but not necessarily convex functions, and propose an
asynchronous doubly stochastic zeroth-order optimization algorithm using the
accelerated technology of variance reduction (AsyDSZOVR). Rigorous theoretical
analysis show that the convergence rate can be improved from
$O(\frac{1}{\sqrt{T}})$ the best result of existing algorithms to
$O(\frac{1}{T})$. Also our theoretical results is an improvement to the ones of
the sequential stochastic zeroth-order optimization algorithms.

本文提出了一种使用方差缩减的异步双随机零阶优化算法 (AsyDSZOVR)，应用于光滑但不一定是凸函数的有限和问题，证明了该算法将收敛速度从 O（1 /√T）提高到了 O（1 / T），优于现有算法的最佳结果，并且也超越了顺序随机零阶优化算法的理论结果。