Optimal estimation of univariate black-box Lipschitz functions with upper and lower error bounds

We are given an unknown univariate Lipschitz continuous function that we wish to estimate by evaluating the function sequentially at distinct points. We provide a procedure for recursively selecting this sequence of points so that, averaging over points in the domain the resulting worst case error between the estimating and actual functions is minimized. Upper and lower bounds on these errors are also provided.