# Stochastic approximation in two dimensions

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 $$M^i({\bf x}) = 0, \, i=1, \ldots, k.$$

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 $$\sum_{n=1}^{\infty} a_n = \infty, \,\;\; \sum_{n=1}^{\infty} a_n^2 < \infty \tag{1}$$ 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$: $$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}}.$$

If there exists $a_n$ and $f$ which satisfy (1)-(5), it is proven that the random sequence ${\bf x}_n$ defined by $${\bf x}_{n+1} = {\bf x}_n + a_n {\bf Y}_{{\bf x}_n}$$ 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?

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