Stochastic approximation: Difference between revisions

Revision as of 17:01, 15 May 2020

Revision as of 17:03, 15 May 2020

Line 66:

We then define a recursion analogously to Newton's Method in the deterministic algorithm:

: <math display="block">\theta_{n+1} = \theta_n - \epsilon_nvarepsilon_n H(\theta_n,X_{n+1}).</math>

==== Convergence of the Algorithm ====

Line 73:

</math> for the algorithm to converge:<ref>{{Cite book|title=Numerical Methods for stochastic Processes|last=Bouleau|first=N.|last2=Lepingle|first2=D.|publisher=John Wiley|year=1994|isbn=9780471546412|___location=New York|pages=|url=https://books.google.com/books?id=9MLL2RN40asC&printsec=frontcover#v=onepage&q&f=false}}</ref>

C1) <math>\epsilon_nvarepsilon_n \geq 0, \forall\; n\geq 0 </math>.

C2) <math>\sum_{n=0}^{\infty} \epsilon_nvarepsilon_n = \infty

</math>

C3) <math>\sum_{n=0}^{\infty}\epsilon_nvarepsilon_n^2 <\infty

</math>

Line 98:

</math> almost surely.

Here are some intuitive explanations about these conditions. Suppose <math>H(\theta_n, X_{n+1})</math> is a uniformly bounded random variables. If C2) is not satisfied, i.e. <math>\sum_{n=0}^{\infty} \epsilon_nvarepsilon_n < \infty

</math> , then<math display="block">\theta_n - \theta_0 = -\sum_{i=0}^{n-1} \epsilon_ivarepsilon_i H(\theta_i, X_{i+1})

</math>is a bounded sequence, so the iteration cannot converge to <math>\theta^*

Line 111:

</math> then

<math display="block">\theta_{n+1} - \theta_n = -\epsilon_nvarepsilon_n H(\theta_n, X_{n+1}) \rightarrow 0,\text{as}\; n\rightarrow \infty.

</math>so we must have <math>\epsilon_nvarepsilon_n \downarrow 0

</math> ，and the condition C3) ensures it. A natural choice would be <math>\epsilon_nvarepsilon_n = 1/n

</math>. Condition C5) is a fairly stringent condition on the shape of <math>g(\theta)</math>; it gives the search direction of the algorithm.

Line 130:

** There exists <math>\beta>0</math> and <math>B>0</math> such that <math display="block">|x'-\theta|+|x''-\theta|<\beta \quad \Longrightarrow \quad |M(x')-M(x'')|<B|x'-x''|</math>

** There exists <math> \rho>0 </math> and <math> R>0 </math> such that <math display="block">|x'-x''|<\rho \quad \Longrightarrow \quad |M(x')-M(x'')|<R</math>

** For every <math> \delta>0 </math>, there exists some <math> \pi(\delta)>0 </math> such that <math display="block">|z-\theta|>\delta \quad \Longrightarrow \quad \inf_{\delta/2>\epsilonvarepsilon>0}\frac{|M(z+\epsilonvarepsilon)-M(z-\epsilonvarepsilon)|}{\epsilonvarepsilon}>\pi(\delta)</math>

*The selected sequences <math>\{a_n\}</math> and <math>\{c_n\}</math> must be infinite sequences of positive numbers such that

**<math>\quad c_n \rightarrow 0\quad \mboxtext{as}\quad n\to\infty </math>

**<math> \sum^\infty_{n=0} a_n =\infty </math>

**<math> \sum^\infty_{n=0} a_nc_n <\infty </math>