# Stochastic Approximation in Reproducing Kernel Hilbert Space

Consider an iterative algorithm with incremental updates \begin{align} x_{t+1} = x_t + \alpha_t \cdot [ h(x_t) + M_{t+1}], \end{align} where $\{x_t \}_{t \geq 0}$ is in a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$, $\alpha_t>0$ is the stepsize, $h \colon \mathcal{H} \rightarrow \mathcal{H}$ is a Lipschitz continuous mapping, and $\{ M_{t+1} \}$ is a Martingale difference sequence.

In classical stochastic approximation theory (e.g.,[1]), if $\mathcal{H}$ is the $n$-dimensional Euclidean space $\mathbb{R}^n$ equipped with the Euclidean norm, it is well known that $\{ x_t\}_{t\geq 0}$ converges almost surely to the stable equilibria of an ordinary differential equation (ODE) \begin{align} \dot{x} = h(x). \end{align}

I was wondering if the theory in classical ODE approximation theory can be readily extended to RKHS by replacing the Euclidean norm in $\mathbb{R}^n$ by the RKHS norm $\| \cdot \|_{\mathcal{H} }$ in $\mathcal{H}$. Any pointer to relevant works of literature would be appreciated.

[1]. Stochastic Approximation: A Dynamical Systems Viewpoint. The basic theory for stochastic approximation in $\mathbb{R}^n$ is in Chapter 2.

• It depends on your approach. There are two general ways to proceed. (1) One can formulate a stochastic approximation algorithm directly in the Hilbert space, but this might be a bit different from Euler’s rule and quite involved. (2) A simpler approach is to introduce a finite dimensional truncation and then prove that the finite dimensional error estimates (which you already have) are uniform in the continuum limit. Lots of work has been done in the related but different problem of sampling perturbations of Gaussian measures on Hilbert spaces. – Nawaf Bou-Rabee Dec 30 '17 at 14:48
• @NawafBou-Rabee Thanks very much for your comment. I found a relevant paper "Abstract stochastic approximations and applications" which study the ODE method of stochastic approximation in Banach spaces. It appears that the key point is that the path of the update stays in a compact domain in the Banach space. Given this condition, the ODE method still works given the similar assumptions made in the Euclidean space. This paper does not use truncation, I was wondering if this is the first way that you mentioned? – Steve Dec 31 '17 at 17:36