Stochastic Simultaneous Optimistic Optimization
StoSOO is an algorithm for global optimization of stochastic functions. It can optimize extremely difficult functions (nonsmooth, no derivatives, noisy evaluations) with theoretical guarantees. The main application is hyper-parameter tuning.
Abstract
We study the problem of global maximization of a stochastic function given a finite budget of n evaluations. We provide for the first time an algorithm with an analysis in terms of the local smoothness of the objective function around one of its global maxima. This algorithm, called StoSOO, is based on a hierarchical partitioning of the search space and alternates between expansion of the partitioning, estimation of the function on promising cells, and exploration of unexplored cells. The algorithm is analyzed in terms of the number of cells required to be explored, and we show that the rate of convergence to the global maximum value depends on the local smoothness of the function at one of the global maxima rather than on its global smoothness.
Code
MATLAB implementation of StoSOO and related algorithms:
Related Work
See also our other work on black-box optimization and Monte-Carlo planning: