  Derivative-free optimization (DFO) has recently gained a lot of momentum in
machine learning, spawning interest in the community to design faster methods
for problems where gradients are not accessible. While some attention has been
given to the concept of acceleration in the DFO literature, existing stochastic
algorithms for objective functions with a finite-sum structure have not been
shown theoretically to achieve an accelerated rate of convergence. Algorithms
that use acceleration in such a setting are prone to instabilities, making it
difficult to reach convergence. In this work, we exploit the finite-sum
structure of the objective in order to design a variance-reduced DFO algorithm
that provably yields acceleration. We prove rates of convergence for both
smooth convex and strongly-convex finite-sum objective functions. Finally, we
validate our theoretical results empirically on several tasks and datasets.
