Optimal order of accuracy of search algorithms in stochastic optimization

Let f: R^N → R¹ be an unknown function with a unique minimum at the point x^*. The problem of estimating x^* from the observations y_n = f(X_n) + ξ_n, n = 1,2,..., where ξ_n are independent random errors and x_n are observations points, is considered in the minimax setting. The best attainable characteristics of stochastic optimization algorithms are investigated, and algorithms with optimal order of accuracy are proposed.