  Stochastic approximation is a foundation for many algorithms found in machine
learning and optimization. It is in general slow to converge: the mean square
error vanishes as $O(n^{-1})$. A deterministic counterpart known as
quasi-stochastic approximation (QSA) is a viable alternative in many
applications, including gradient free optimization and reinforcement learning.
It was assumed in recent prior research that the optimal achievable convergence
rate is $O(n^{-2})$. It is shown in this paper that through design it is
possible to obtain far faster convergence, of order $O(n^{-4+\delta})$, with
$\delta>0$ arbitrary. Two acceleration techniques are introduced for the first
time to achieve this rate of convergence. The theory is also specialized within
the context of gradient-free optimization, and tested on standard benchmarks.
The main results are based on a combination of recent results from number
theory and techniques adapted from stochastic approximation theory.

Optimization and Control