Approximate function with minimum number of evaluations

Question

I'm trying to approximate an unknown, non-linear function $f: A \to \mathbb{R}$ (in my case: $A = B \times B$ where $B$ is an infinite but compact subset of $\mathbb{R}$). That is, evaluating $f$ is costly and I'm looking for an easy-to-evaluate function $g$ such that $f$ is close to $g$ on $A$. Given an error bound, how can I compute $g$ with as few evaluations of $f$ as possible?

I'm flexible regarding the precise definition of the error. For example, both the expected average error and the expected maximum error would work. Similarly, I don't really care about the type of representation used for $g$ (splines, polynomials, etc.) as long it can be efficiently evaluated. The number of evaluations of $f$ must not necessarily be provably minimal, methods that work well in practice are sufficient.

To me, it sounds like design of experiments might offer suitable tools, however, I'm not sure how to match my setting to that statistical context. Bayesian optimization also seems to have a very similar setting, but I'm not sure how one would adapt it to optimize a general approximation of $f$ instead of its optimization.

Answer 1

You could probably use a surrogate model $g$ of your function $f$ using kriging see for example Engineering design via surrogate model, and GaussianProcess from sklearn for python.

Really briefly; using it you can build a prediction $g(x)$ and its variance $s^2(x)$ for all $x$ from a limited number of samples points $X$ such as :

\begin{equation}\label{eq:pred} g(x) ={p}_x^T\tilde{\beta} + {r_x}^T{R}^{-1}{f_x}-{P}{\tilde{\beta}}) \end{equation}

\begin{equation}\label{eq:var} s^2({x}) = \tilde{\sigma}^2[1+{r_x}^T{R}^{-1}{r_x}] \end{equation}

Where $p_x$ is the response of $x$ to a chosen polynomial regression and $P$ the response of the learning points to this regression. $r_x$ is the correlation vector of $x$ and $R$ the correlation matrix of the learning points $X$. Finally, $\tilde{\beta}$ and $\tilde{\sigma^2}$ are known coefficients.

Then, to save the number of calling to your expensive function $f$ :

1- Build a first surrogate $g$ with a limited and reasonable number of learning point (DOE)

2- Enrich your surrogate with a new learning point chosen by a criterion based on $s$. Add a learning point where the surrogate is the worse, where the error is the biggest.

3- Repeat 2 until obtain a satisfactory $g$, which is easy to evaluate.

So, the number of evaluation is the number of samples points $X$ plus the number of enrichment.