A lower bound on complexity of optimization on the Wiener space

This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ϵ, on the order of loglog(1/ϵ)log(1/ϵ) function evaluations are required.