Is it possible to combine SPSA and Adam? In SGD algorithms such as Adam you generally make a bad estimate of the gradient of the loss function and take that gradient to move the parameters in the desired direction. 
Gradient free methods such as SPSA do basically the same, they make a bad estimate of the gradient, by randomly perturbing the parameter vector in two opposite directions. Then they move the parameters along the direction of the gradient. 
My question is: Would it possible to combine the gradient calculation from SPSA with the "step taking" from Adam and are there any papers on such an approach?
SPSA only uses a decaying step sequence, and Adam seems superior it this regard. 
Edit: The resulting combined algorithm is not supposed to be used to train a ANN but for simulation based optimization.
 A: See Robust and efficient algorithms for high-dimensional black-box quantum optimization.
I'll remark from what I understand that the idea of combining SPSA and Adam doesn't seem very good. The issue is immediately seen from the fact that SPSA provides the same magnitude in every component of the gradient, which means one cannot directly get any sense of an "adaptive method" which scales each component individually. Instead it becomes more like a normalized gradient descent, where all parameters are scaled equally.
With a bit more analysis, we could argue that SPSA isn't built at all towards something like Adam, even if we try to average out the gradient estimates to get different magnitudes for each component. With a quick Taylor series, we may see that $\hat g_1$, the gradient for the first component, is estimated as:
$$\hat g_1\simeq(g\cdot e)e_1+\epsilon_1=g_1\pm g_2\pm g_3\pm\dots+\epsilon_1$$
where $g$ is the true gradient, $e$ is the signs of the perturbations, and $\epsilon_1$ is an additional error term (including things like noisy evaluations and the fact that the perturbation step size needs to vanish). This means the main noise in the estimate of the first component depends on all of the other components combined. For components which are large, this noise is negligible and we get an accurate estimate. For components which are small, this noise is significant and we need a large amount of iterations before our averaged estimate starts to look good.
This lack of accuracy for small components in turn causes Adam to significantly over-estimate the magnitude of those components, which would slow them down greatly rather than speed them up. Perhaps this might be beneficial, since it would more greatly slow down noisy gradients, but the overall effects seem to be contrary to that of Adam's original purposes and at best very limited.
