The stochastic gradient descent algorithm where only a noisy gradient (zero mean noise) is used to update current estimate is known to converge almost surely to the minimizer. However, if one is interested only in convergence in distribution (I understand this requirement is a weaker notion) and NOT almost sure convergence, how should the step sizes chosen so that only distributional convergence and not a.s is guaranteed?

yes that is exactly what i am looking for. 


@peter Sarkoci you are right that the question is about the behaviour of a randomized algorithm. However, i would want the minimizer to be a nontrivial random variable rather than a constant. Any r.v with expected value as the actual minimizer would do. For instance, a Gaussian with mean at the minimizer and low variance would be fine. I think for such a condition to be satisfied depends only on the possible values of the gradients of the original function and not on the choice of step sizes. Am i right? 


I think you're talking about the SPGD algorithm as mentioned in Vorontsov's papers. As far as I now there is no real mathematical background theory directly for this, but there exist theory about SPSA which is very close to SPGD, for example Spall "Introduction to Stochastic Search and Approximation" (who only talks about a.s. convergence). In Kushner and Yin,"Stochastic Approximation and Recursive Algorithms and Applications" is some theory about weaker convergence, but more for the general KieferWolfowitzSAcase. 

