Problem statement: Assume that I have an objective function $f(x)$ which takes as input a $D$-dimensional vector $x\in\mathbb{R}^D$, and that $f(x)$ is sufficiently smooth. Assume further that I have a set of $N$ samples $\{x_1,x_2,...,x_N\}$ for which I know the output of the objective functions $\{f(x_1),f(x_2),...,f(x_N)\}$. It is my task to minimize the objective function $f(x)$ by moving the samples towards its minimum.
Complication: Now assume that I cannot evaluate the partial derivatives of the objective function $\nabla f(x)$ analytically, and that evaluations of $f(x)$ are very expensive and $D$ is very large, so that obtaining $\nabla f(x)$ through local finite differences is not an option. Assume further that the points are distributed arbitrarily.
Question: I am looking for methods which would permit me to approximate the partial derivatives of the objective function $\{\nabla_{x_1}f(x_1),\nabla_{x_2}f(x_2),...,\nabla_{x_N}f(x_N)\}$ at each sample point $x_i, i=1,...,N$, using only the evaluations of the objective function at the sample points. Do you know of any methods which could be used towards this end?