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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
2
|
|
||||||
|
|
1
|
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. |
||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
0
|
yes that is exactly what i am looking for. |
||
|
|
|
0
|
@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? |
||
|
|
