Randomized learning of the second-moment matrix of a smooth function

Figure 1.  Visualization of the problem setup. The probability measure $ \mu $ is supported on the domain $ \mathbb{D}\subseteq \mathbb{R}^n $ of a smooth function $ f(\cdot) $. Here, $ N = 3 $ and $ X = \{x_i\}_{i = 1}^N $ are drawn independently from $ \mu $. For sufficiently small $ \epsilon $, we let $ \mathbb{B}_{x_i, \epsilon} $ denote the $ \epsilon $-neighborhood of each $ x_i $ and set $ \mathbb{B}_{X, \epsilon} = \cup_{i = 1}^N \mathbb{B}_{x_i, \epsilon} $. On $ \mathbb{B}_{X, \epsilon} $, $ \mu $ induces the conditional measure $ \mu_{X, \epsilon} $, from which $ N_{X, \epsilon} $ points are independently drawn and collected in $ Y_{X, \epsilon} = \{y_{ij}\}_{i, j} $. Here, $ x_1 $ has $ N_{x_1, \epsilon} = 2 $ neighbors in $ Y_{X, \epsilon} $ and we set $ Y_{x_1, \epsilon} = \{y_{1, j} \}_{j = 1}^{N_{x_1, \epsilon}} $. Similarly, $ Y_{x_2, \epsilon} $ and $ Y_{x_3, \epsilon} $ are formed. Note that $ Y_{X, \epsilon} = \cup_{i = 1}^N Y_{x_i, \epsilon} $. Our objective is to estimate the second-moment matrix of $ f(\cdot) $ (with respect to the probability measure $ \mu $) given $ \{x_i, f(x_i)\} $ and $ \{y_{ij}, f(y_{ij})\} $

Figure 2.  A simulation study using a 500-dimensional ($ n = 500 $) quadratic function for the relative error in the approximation (7) as a function of the number $ N_{X, \epsilon} $ of total samples. All simulations use $ \epsilon = 10^{-4} $. Each subfigure uses a different value for the minimum number $ N_{X, \text{min}, \epsilon} $ of points in the $ \epsilon $-neighborhood of each center point in $ X $, and varies the number $ N $ of centers. Each of the five groups of blue dots in each subfigure indicates a different number $ N $. Within each group, there are ten replications. The slope of each line is $ -1/2 $, which verifies the expected convergence rate from (6)