most recent 30 from http://mathoverflow.net 2013-05-23T00:49:33Z http://mathoverflow.net/feeds/question/65833 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65833/convergence-in-distribution-of-stochastic-gradient-descent Vedarun 2011-05-24T09:47:29Z 2011-08-22T15:22:12Z

<p>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?</p>

http://mathoverflow.net/questions/65833/convergence-in-distribution-of-stochastic-gradient-descent/66205#66205 vedarun 2011-05-27T17:50:18Z 2011-05-27T17:50:18Z

<p>yes that is exactly what i am looking for.</p>

http://mathoverflow.net/questions/65833/convergence-in-distribution-of-stochastic-gradient-descent/66357#66357 vedarun 2011-05-29T12:11:56Z 2011-05-29T12:11:56Z

<p>@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 non-trivial 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. </p> <p>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?</p>

http://mathoverflow.net/questions/65833/convergence-in-distribution-of-stochastic-gradient-descent/68923#68923 Johannes L 2011-06-27T12:59:36Z 2011-06-27T12:59:36Z

<p>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 Kiefer-Wolfowitz-SA-case.</p>