# Approximate function with minimum number of evaluations

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.

• What's the regularity? Continuous? Continuously Differentiable? Smooth? This matters a lot. – Chris Rackauckas Sep 20 '17 at 17:58
• When you say infinite subset you mean the cardinality of it, right? – nicoguaro Sep 20 '17 at 18:10
• Have you tried just straightforward interpolation from an existing library, like in scipy, or something like chebfun? Did it fail somehow for you? It's important to know, because in the general case of a truly arbitrary function on an arbitrary domain this can be quite difficult, but most common cases are reasonably straightforward. You don't say anything about your function's properties. – Kirill Sep 21 '17 at 0:27
• @ChrisRackauckas: I don't have any theoretic guarantees aside from continuitiy, but I'm open for methods that have stricter requirements (e.g. smoothness) to see how well they work in my case. – Florian Brucker Sep 21 '17 at 7:15
• @nicoguaro: Yes (since I also said bounded ;). I added "infinite" to make it clear that my question is not about a discrete setting. – Florian Brucker Sep 21 '17 at 7:17

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 :

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

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

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.

• Thanks for your input! How would I choose the number and location of the initial nodes for step 1? Ideally I'd like to start from one single node and then let the method guide me in the selection of further nodes. Secondly, how can I estimate the error in places where I don't have nodes (step 2)? – Florian Brucker Sep 21 '17 at 14:05
• You can choose the first learning points using a design of experiment ( the [Latin Hypercube Sampling][1] is easy to implement and efficient). I don't know how many initial points you need but one seems not be enough. For evaluate the error in any points you have to use the expression of the variance. For example $3s(x)$ gives a tolerance interval at 95% of $x$ evaluation. [1] : en.wikipedia.org/wiki/Latin_hypercube_sampling – Shka Sep 21 '17 at 14:22