Global stochastic optimization with low-dispersion point sets

This study concerns a generic model-free stochastic optimization problem re quiring the minimization of a risk function defined on a given bounded doma in in a Euclidean space. Smoothness assumptions regarding the risk function are hypothesized, and members of the underlying space of probabilities are presumed subject to a large deviation principle; however, the risk functio n may well be nonconvex and multimodal. A general approach to finding the r isk minimizer on the basis of decision/observation pairs is proposed. It co nsists of repeatedly observing pairs over a collection of design points. Pr inciples are derived for choosing the number of these design points on the basis of an observation budget, and for allocating the observations between these points in both prescheduled and adaptive settings. On the basis of t hese principles, large-deviation type bounds of the minimizer in terms of s ample size are established.