# Predicting the maximum of a function given a set of samples

The main aspects of the question are highlighted in bold

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a function. Supposing that we have access to a set of samples $(X,Y)$ obtained by sampling the function (eventually with measurement noise). The main goal is to guess both:

• An input $\widehat{x^*}$ which maximize $f(x)$
• A prediction of $f(\widehat{x^*})$

The function $f$ might exhibit discountinuity and might be difficult to represent with classical function approximators.

Example of function $f$ with an input of dimension 3:

f(x): if (x[1] > -3) return abs(x[0]) + x[2] * sin(x[1]) else return 0 

While providing accurate estimation for such arbitraries functions is not possible, I consider that the quality of the guess is highly dependent on the shape of the function and the number of samples available. Since my aim is to study the problem in depth, I am particularly interested in related litterature.

Note that in my setup, it is not possible to learn by using acquiring new samples from the function. However, if a prediction function is built from the original set of samples, it is possible to use it in order to provide estimate. It is also possible to sample the function in order to assess the performance of the predictor. My aim is to provide a quick-learner algorithm which requires a limited number of samples to estimate the maximum of a function without requiring expert knowledge. Since in this setup, it is very unlikely to find the real maximum, the goal is to provide an adequate guess which minimize the difference with the real maximum

Is there any specific litterature focussing on predicting the input which has the highest/lowest output, and its average output? (i.e. finding the arg max and max)

I can easily imagine that it exists, however, I have not been able to find the key words allowing me to find related articles.

Several regression methods allows to train models which fit the data (e.g. linear regression, regression forests, gaussian processes). While for some of these models, the global maximum can be computed analytically, for others this information cannot be extracted easily. However, most of them allows to retrieve the gradient of the output which can easily be used to find a local optimum. In my case, I use a custom approximator based on regression forests which allows to deal with discontinuous functions.

I have read that other methods such as simulated annealing have better chances of converging toward the global optimum. However since this method does not use the extra information provided by the gradient, I guess that more efficient methods exist (i.e. methods requiring a lower computation time for equivalent performance).

Do you know about an article evaluating empirically different methods to find the global optimum?

Finally, since I am talking about equivalent performance. If we note $\widehat{x^*}$ the predicted best input, $\widehat{f(\widehat{x*})}$ the predicted value at $\widehat{x^*}$ and $x^*$ the best input (known). I can describe two different criteria:

• Loss of the solution: $f(x^*) - f(\widehat{x^*})$
• Accuracy of the prediction: $f(\widehat{x^*}) - \widehat{f(\widehat{x^*})}$

Does those criteria of performance seems reasonable? Am I missing known metrics?

UPDATE: Adding information about the shape of $f$, the setup and my aims.

The problem with any maximizing algorithm, like simulated annealing and others, is that you need to be able to evaluate your function at new points, and your question sounds as if this was not possible. This also makes your performance criteria hard to implement, since you can't even evaluate $f(\hat{x^\ast})$. So you can only start annealing or gradient searching once you have an interpolating function.
In interpolating, you will need to find a "good" balance between flexibility and parsimoniousness. You don't say anything about your function's regularity. If $f$ is just "any function", then it could of course be utterly intractable, jumping up and down randomly - in which case your entire project is doomed to failure, since your data points don't say anything about $f$'s behavior even an $\epsilon$ away.
If we can assume at least some regularity, it will probably make sense to fit different interpolators (e.g., splines/smoothers with different bandwidths) and compare their accuracy using cross-validation. In addition, once you have chosen an interpolator, I'd assess the variability of the estimated $\hat{x^\ast}$ using a bootstrap.
• Thank you very much for your quick answer. I realize that I have not been quite clear in my question. Regarding the evaluation of my function at new points, it is not possible to sample $f$ directly, however it is possible to evaluate the predictor. I will update my question in order to add information regarding the shape of the function. – medrimonia May 17 '16 at 8:04
• I'm not entirely clear on what you mean by "it is not possible to sample $f$ directly, however it is possible to evaluate the predictor". Looking at your edit and your example function, you will probably need to tailor your interpolation to what you know of the function, e.g., adding indicator or step functions. – Stephan Kolassa May 17 '16 at 9:22
• What I mean is that acquiring new samples of the $f$ function might not be possible because the function might involve experiment on a real system which is not available during the learning phase. However, it is allowed to create a predictor (e.g. a gaussian process which has $X$ as inputs and $Y$ a outputs). And thus, we can compute an estimation of the value and the gradient of the function $f$ for any input without requiring to interact with the system. However, the focus of this question is not on how to build the predictor, but more on how to estimate the maximum of the predictor. – medrimonia May 17 '16 at 15:03