Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  fedja May 24 '11 at 19:45
    
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? –  Peter Sarkoci May 28 '11 at 19:30
add comment

3 Answers 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.

share|improve this answer
    
@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. –  Vedarun Jun 29 '11 at 5:33
    
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 –  Johannes L Jul 4 '11 at 7:38
add comment

yes that is exactly what i am looking for.

share|improve this answer
add comment

@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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.