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.
 A: You can attempt to interpolate your function and then maximize the interpolation function. Good possibilities would by splines (e.g., radial basis splines), or other smoothers.
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.
