On Randomized Approximation of Scattered Data

Let $A$ be a set and $V$ a real Hilbert space. Let $H$ be a real Hilbert space of functions $f:A\to V$ and assume $H$ is continuously embedded in the Banach space of bounded functions. For $i=1,\cdots ,n$, let $(x_i,y_i)\in A\times V$compriseourdataset\mathrm{.}Let$0<q<1$and$f^\in H$ be the unique global minimizer of the functional \begin{equation} u(f) = \frac{q}{2}\Vert f\Vert_{H}^{2} + \frac{1-q}{2n}\sum_{i=1}^{n}\Vert f(x_i)-y_i\Vert_{V}^{2}. \end{equation*} For $x\in A$ and $v\in V$ let $\mathrm{\Phi }(x,v)\in H$ be the unique element such that $(\mathrm{\Phi }(x,v),f{)}_H=(f(x),v{)}_V$ for all $f\in H$. In this paper we show that for each $k\in \mathbb{N}$, $k\ge 2$ one has a random function $F_{k}\in H$ with the structure \begin{equation*} F_{k} = \sum_{h=1}^{N_k} \Lambda_{k, h} \Phi(x_{I_h}, $\mathcal{E}${h}) \end{equation*} (where $0\le N_k\le k-1$ are Binomially distributed with success probability $1-q$, $\Lambda{k, h}\in$\mathbb{R}$$arerandomcoefficients,$1\leq I_{h}\leq n$ are independent and uniformly distributed and ${\mathcal{E}}_h\in V$ are random vectors) such that asymptotically for large $k$ we have \begin{equation*} E\left[ \Vert F_{k}-f^\Vert_{H}^{2} \right] = O(\frac{1}{k}). \end{equation} Thus we achieve the Monte Carlo type error estimate with no metric or measurability structure on $A$, possibly infinite dimensional $V$ and the ingredients of approximating functions are just the Riesz representatives $\mathrm{\Phi }(x,v)\in H$. We obtain this result by considering the stochastic gradient descent sequence in the Hilbert space $H$ to minimize the functional $u$.