Wiki
Wiki
Courses and public working groups
Courses and public working groups
Private Working Groups
Private Working Groups
- New!!! Reading Group
- Theatre
- Admin
- Research
- Teaching
Sidebar
world:robbins_monro
Table of Contents
$$ \newcommand{\arginf}{\mathrm{arginf}} \newcommand{\argmin}{\mathrm{argmin}} \newcommand{\argmax}{\mathrm{argmax}} \newcommand{\asconv}[1]{\stackrel{#1-a.s.}{\rightarrow}} \newcommand{\Aset}{\mathsf{A}} \newcommand{\b}[1]{{\mathbf{#1}}} \newcommand{\ball}[1]{\mathsf{B}(#1)} \newcommand{\bbQ}{{\mathbb Q}} \newcommand{\bproof}{\textbf{Proof :}\quad} \newcommand{\bmuf}[2]{b_{#1,#2}} \newcommand{\card}{\mathrm{card}} \newcommand{\chunk}[3]{{#1}_{#2:#3}} \newcommand{\condtrans}[3]{p_{#1}(#2|#3)} \newcommand{\convprob}[1]{\stackrel{#1-\text{prob}}{\rightarrow}} \newcommand{\Cov}{\mathbb{C}\mathrm{ov}} \newcommand{\cro}[1]{\langle #1 \rangle} \newcommand{\CPE}[2]{\PE\lr{#1| #2}} \renewcommand{\det}{\mathrm{det}} \newcommand{\dimlabel}{\mathsf{m}} \newcommand{\dimU}{\mathsf{q}} \newcommand{\dimX}{\mathsf{d}} \newcommand{\dimY}{\mathsf{p}} \newcommand{\dlim}{\Rightarrow} \newcommand{\e}[1]{{\left\lfloor #1 \right\rfloor}} \newcommand{\eproof}{\quad \Box} \newcommand{\eremark}{</WRAP>} \newcommand{\eqdef}{:=} \newcommand{\eqlaw}{\stackrel{\mathcal{L}}{=}} \newcommand{\eqsp}{\;} \newcommand{\Eset}{ {\mathsf E}} \newcommand{\esssup}{\mathrm{essup}} \newcommand{\fr}[1]{{\left\langle #1 \right\rangle}} \newcommand{\falph}{f} \renewcommand{\geq}{\geqslant} \newcommand{\hchi}{\hat \chi} \newcommand{\Hset}{\mathsf{H}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\img}{\text{Im}} \newcommand{\indi}[1]{\mathbf{1}_{#1}} \newcommand{\indiacc}[1]{\mathbf{1}_{\{#1\}}} \newcommand{\indin}[1]{\mathbf{1}\{#1\}} \newcommand{\itemm}{\quad \quad \blacktriangleright \;} \newcommand{\jointtrans}[3]{p_{#1}(#2,#3)} \newcommand{\ker}{\text{Ker}} \newcommand{\klbck}[2]{\mathrm{K}\lr{#1||#2}} \newcommand{\law}{\mathcal{L}} \newcommand{\labelinit}{\pi} \newcommand{\labelkernel}{Q} \renewcommand{\leq}{\leqslant} \newcommand{\lone}{\mathsf{L}_1} \newcommand{\lrav}[1]{\left|#1 \right|} \newcommand{\lr}[1]{\left(#1 \right)} \newcommand{\lrb}[1]{\left[#1 \right]} \newcommand{\lrc}[1]{\left\{#1 \right\}} \newcommand{\lrcb}[1]{\left\{#1 \right\}} \newcommand{\ltwo}[1]{\PE^{1/2}\lrb{\lrcb{#1}^2}} \newcommand{\Ltwo}{\mathrm{L}^2} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mcbb}{\mathcal B} \newcommand{\mcf}{\mathcal{F}} \newcommand{\meas}[1]{\mathrm{M}_{#1}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\normmat}[1]{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert #1 \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}} \newcommand{\nset}{\mathbb N} \newcommand{\N}{\mathcal{N}} \newcommand{\one}{\mathsf{1}} \newcommand{\PE}{\mathbb E} \newcommand{\pminfty}{_{-\infty}^\infty} \newcommand{\PP}{\mathbb P} \newcommand{\projorth}[1]{\mathsf{P}^\perp_{#1}} \newcommand{\Psif}{\Psi_f} \newcommand{\pscal}[2]{\langle #1,#2\rangle} \newcommand{\pscal}[2]{\langle #1,#2\rangle} \newcommand{\psconv}{\stackrel{\PP-a.s.}{\rightarrow}} \newcommand{\qset}{\mathbb Q} \newcommand{\revcondtrans}[3]{q_{#1}(#2|#3)} \newcommand{\rmd}{\mathrm d} \newcommand{\rme}{\mathrm e} \newcommand{\rmi}{\mathrm i} \newcommand{\Rset}{\mathbb{R}} \newcommand{\rset}{\mathbb{R}} \newcommand{\rti}{\sigma} \newcommand{\section}[1]{==== #1 ====} \newcommand{\seq}[2]{\lrc{#1\eqsp: \eqsp #2}} \newcommand{\set}[2]{\lrc{#1\eqsp: \eqsp #2}} \newcommand{\sg}{\mathrm{sgn}} \newcommand{\supnorm}[1]{\left\|#1\right\|_{\infty}} \newcommand{\thv}{{\theta_\star}} \newcommand{\tmu}{ {\tilde{\mu}}} \newcommand{\Tset}{ {\mathsf{T}}} \newcommand{\Tsigma}{ {\mathcal{T}}} \newcommand{\ttheta}{{\tilde \theta}} \newcommand{\tv}[1]{\left\|#1\right\|_{\mathrm{TV}}} \newcommand{\unif}{\mathrm{Unif}} \newcommand{\weaklim}[1]{\stackrel{\mathcal{L}_{#1}}{\rightsquigarrow}} \newcommand{\Xset}{{\mathsf X}} \newcommand{\Xsigma}{\mathcal X} \newcommand{\Yset}{{\mathsf Y}} \newcommand{\Ysigma}{\mathcal Y} \newcommand{\Var}{\mathbb{V}\mathrm{ar}} \newcommand{\zset}{\mathbb{Z}} \newcommand{\Zset}{\mathsf{Z}} $$
Statement
We set $\Xset =\rset$, $\Xsigma=\mc{B}(\Xset)$ and we let $f:\Xset \to \Xset$ and $x_*\in \Xset$ such that
- $f$ is a bounded and continuous function
- $f(x)(x-x_*)>0$ for all $x\neq x_* \in \Xset$
We assume there exist a Markov kernel $K$ on $\Xset \times \Xsigma$ and a sequence $\seq{\gamma_k}{k\in\nset}$ of real numbers such that
- $\int y K(x, \rmd y)=f(x)$
- $\gamma_k>0$ for all $k\geq 0$
- $\sum_{k=0}^\infty \gamma_k=\infty$
- $\sum_{k=0}^\infty \gamma_k^2<\infty$
- there exists $M$ such that for all $x\in \Xset$, $\int y^2 K(x,\rmd y)\leq M<\infty$.
Let $X_0$ be a random variable such that $\PE[X^2_0]<\infty$. Define iteratively the sequence $$X_{n+1}=X_{n}-\gamma_{n+1} U_{n+1}$$ where $U_{n+1}|_{\mcf_n}\sim K (X_n,\cdot)$ and $\mcf_n=\sigma(X_0,\ldots,X_n)$. The aim of this short note is to prove that $X_n \psconv x_*$. We follow a version of the proof proposed by François Roueff.
Proof
The intermediate quantity $S_n$
Write $$ (X_{n+1}-x_*)^2=(X_{n}-x_*)^2-2 \gamma_{n+1} U_{n+1} \lr{X_n-x_*} + \gamma_{n+1}^2 U_{n+1}^2. $$ and set \begin{equation} \label{eq:def:Sn} S_n=2\sum_{k=1}^n \gamma_k U_k (X_{k-1}-x_*)= (X_0-x_*)^2-(X_n-x_*)^2+\sum_{k=1}^n \gamma_k^2 U_k^2. \end{equation}
Convergence of $(X_n-x_*)^2$
Considering \eqref{eq:def:Sn}, to obtain the convergence of $(X_n-x_*)^2$, we only need to prove that $S_n$ and $\sum_{k=1}^n \gamma_k^2 U_k^2$ converge $\PP$-a.s. as $n$ goes to infinity.
- The convergence of $(S_n)$ follows from (see some results on limits of martingales)
- $(S_n)$ is a submartingale since $\CPE{S_n-S_{n-1}}{\mcf_{n-1}}=2\gamma_n f (X_{n-1}) (X_{n-1}-x_*) \geq 0$
- $\sup_n \PE[S_n^+] \leq \PE[(X_0-x_*)^2]+\sum_{k=1}^n \gamma_k^2 \underbrace{\PE[U_k^2]}_{\leq M}<\infty$.
- The convergence of $\sum_{k=1}^n \gamma_k^2 U_k^2$ follows from $\PE[\sum_{k=1}^\infty \gamma_k^2 U_k^2]=\sum_{k=1}^\infty \gamma_k^2 \PE[U_k^2]<\infty$.
Finally, \eqref{eq:def:Sn} implies that $(X_n-x_*)^2 \asconv{\PP} A$ for some $\PP$-a.s. finite random variable $A$. To complete the proof, it remains to show that $A$ is almost surely null.
Proof of $\mathbb{P}(A=0)=1$.
First, write the Doob decomposition for the submartingale $(S_n)$ that is: $S_n=M_n+W_n$ where \begin{align*} & M_n=2\sum_{k=1}^n \lr{\gamma_k U_k (X_{k-1}-x_*)-\gamma_k f (X_{k-1}) (X_{k-1}-x_*)}\\ & W_n=2\sum_{k=1}^n \gamma_k f (X_{k-1}) (X_{k-1}-x_*) \end{align*} Note that $(W_n)$ is a non-decreasing previsible non-negative process and that $(M_n)$ is a martingale.
To conclude, it is sufficient to prove that for any $\delta>0$, $\PP(\delta/2 < |A| <\delta)=0$. To this aim, we will show that
- $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty\eqdef \lim_n W_n=\infty}$
- $\PP(W_\infty=\infty)=0$.
To get the second property (2), note that $M_n\leq S_n$ so that $\sup_{n\in\nset} \PE[M_n^+]\leq \sup_{n\in\nset} \PE[S_n^+]<\infty$. Finally, $(M_n)$ is a martingale, with a positive part which is uniformly bounded in $L^1$. Therefore (see for example some convergence properties for martingales, $(M_n)$ converges $\PP$-a.s. And since $W_n=S_n-M_n$, it also implies that $(W_n)$ converges a.s. so that $\PP(W_\infty=\infty)=0$.
We now turn to the first property (1). Let $\omega \in \lrcb{\delta/2 < |A| <\delta}$. Then, there exists $N(\omega)$ such that for all $n\geq N(\omega)$, $X_n\in B$ where $B=\set{x\in\Xset}{\delta/2 <(x-x_*)^2<\delta}$. Moreover, by continuity of $f$, \begin{equation*} \gamma\eqdef \inf_{x\in B} f(x)(x-x_*) >0 \end{equation*} and this implies that for all $\omega \in \lrcb{\delta/2 < |A| <\delta}$, \begin{equation*} W_\infty \geq \sum_{n=N(\omega)+1}^\infty \gamma_k f (X_{k-1}(\omega)) (X_{k-1}(\omega)-x_*) \geq \gamma \sum_{n=N(\omega)+1}^\infty \gamma_k=\infty \end{equation*} This shows that $\lrcb{\delta/2 < |A| <\delta} \subset \lrcb{W_\infty=\infty}$ and the proof is completed.
world/robbins_monro.txt · Last modified: 2023/02/10 18:17 by rdouc
