I have a question about a stochastic approximation method presented in J. R. Blum, Ann. Math. Stat. 25(4): 737 (1954).

Given a $k$-dimensional vector $\bf x$ and $k$ random variables $Y^1_{\bf x}, \ldots, Y^k_{\bf x}$ with respective cumulative distribution functions $F^1_{\bf x}(y), \ldots, F^k_{\bf x}(y)$ and given $ M^i({\bf x}) = \int_{-\infty}^{\infty} dF^i_{\bf x}(y) \, y, $ it is desired to find an approximating random vector $\bf x$ which solves \begin{equation} M^i({\bf x}) = 0, \, i=1, \ldots, k. \end{equation}

Without losing generality, the author assumes ${\bf M}({\bf 0}) = \bf 0$ and proves the following. Consider a sequence $a_n$ of positive numbers such that \begin{equation} \sum_{n=1}^{\infty} a_n = \infty, \,\;\; \sum_{n=1}^{\infty} a_n^2 < \infty \tag{1} \end{equation} and a real-valued function $f({\bf x})$ such that \begin{eqnarray} f({\bf x}) &\geq& 0\tag{2}\\ \sup_{|{\bf x}|\geq \epsilon} \left( \sum_{i=1}^k \frac{\partial f}{\partial x_i} M^i({\bf x}) \right)&<&0 \;\;\; \forall \epsilon >0,\tag{3}\\ \inf_{|{\bf x}| \geq \epsilon}\left|f({\bf x}) - f(\bf 0)\right| & > & 0 \; \; \; \forall \epsilon > 0, \tag{4}\\ {\mathbb E}\left[ \sum_{i,j=1}^k \left. \frac{\partial^2 f}{\partial x_i \partial x_j}\right|_{{\bf x} + \theta a {\bf Y}_{\bf x}} Y^i_{\bf x} Y^j_{\bf x}\right] \leq V &<& \infty \;\;\; \text{for every number } a,\tag{5} \end{eqnarray} where $\mathbb E$ denotes the expectation with respect to all random variables, and the number $0 \leq \theta\leq 1$ is defined by Taylor's theorem for $f$: \begin{equation} f({\bf x} + \theta a {\bf Y}_{\bf x}) = f({\bf x}) + a \sum_{i=1}^k \frac{\partial f}{\partial x_i} Y^i_{\bf x} + \frac{a^2}{2}\sum_{i,j=1}^k Y^i_{\bf x} Y^j_{\bf x} \left. \frac{\partial^2 f}{\partial x_i \partial x_j}\right|_{{\bf x} + \theta a {\bf Y}_{\bf x}}. \end{equation}

If there exists $a_n$ and $f$ which satisfy (1)-(5), it is proven that the random sequence ${\bf x}_n$ defined by \begin{equation} {\bf x}_{n+1} = {\bf x}_n + a_n {\bf Y}_{{\bf x}_n} \end{equation} converges almost surely to the solution ${\bf x}_n = {\bf 0}$ for $n \rightarrow \infty$.

I would like to use this theorem in a toy example with $k=2$, where \begin{eqnarray} \frac{dF^i_{\bf x}}{d y} = \frac{1}{\sqrt{2 \pi}} e^{-\frac{(x_i+y)^2}{2}}, \;\;\; i=1,2. \end{eqnarray} In this example everything can be computed exactly, in particular ${\bf M}({\bf x}) = -{\bf x}$. Do you know how to construct explicitly $a_n$ and $f$ that satisfy Eqs. (1)-(5) for this toy example?

  • $\begingroup$ If this can help, the choice $a_n=1/n$, $f({\bf x}) = |{\bf x}|^2$ satisfies (1)-(4), but not (5). $\endgroup$ – James Dec 22 '16 at 12:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.