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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I'm not sure what exactly is asked. Are you looking for an example when the convergence in distribution holds and the a.s. one fails, or what? $\endgroup$– fedjaMay 24, 2011 at 19:45
-
$\begingroup$ I do not understand your question very well. What you asked seems to be a question about behavior of certain randomized minimization algorithm. Am I right? As such, one would expect the minimizer to be a constant value (rather than a nontrivial r.v.); am I still right? If so, are you aware of the fact that, in such case the convergence in distribution turns up into convergence in probability? $\endgroup$– Peter SarkociMay 28, 2011 at 19:30
-
$\begingroup$ @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. 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? $\endgroup$– vedarunMay 29, 2011 at 12:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ yes that is exactly what i am looking for. $\endgroup$– vedarunMay 27, 2011 at 17:50
-
$\begingroup$ @Johanness L, Thanks a lot for the reply. It would be great if you could point me to the first paper on SPGD by Vorontsov. $\endgroup$– VedarunJun 29, 2011 at 5:33
-
$\begingroup$ Here would be one: Adaptive wavefront control with asynchronous stochastic parallel gradient descent clusters Mikhail A. Vorontsov and Gary W. Carhart JOSA A, Vol. 23, Issue 10, pp. 2613-2622 (2006) doi:10.1364/JOSAA.23.002613 $\endgroup$ Jul 4, 2011 at 7:38