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.

  • $\begingroup$ 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. $\endgroup$ – Nawaf Bou-Rabee Dec 30 '17 at 14:48
  • $\begingroup$ @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? $\endgroup$ – Steve Dec 31 '17 at 17:36

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.