DOO Algorithm

Introduction

paper, code

Title: Optimistic Optimization of a Deterministic Function without the Knowledge of its Smoothness

Authors: Remi Munos

Abstract: We consider a global optimization problem of a deterministic function f in a semi-metric space, given a finite budget of n evaluations. The function f is assumed to be locally smooth (around one of its global maxima) with respect to a semi-metric l. We describe two algorithms based on optimistic exploration that use a hierarchical partitioning of the space at all scales. A first contribution is an algorithm, DOO, that requires the knowledge of l. We report a finite-sample performance bound in terms of a measure of the quantity of near-optimal states. We then define a second algorithm, SOO, which does not require the knowledge of the semi- metric l under which f is smooth, and whose performance is almost as good as DOO optimally-fitted.

../../../_images/DOO.png

Algorithm Parameters

  • n (int) – The total number of rounds (budget)

  • delta (function) – The function to compute the delta value for each depth

  • domain (list(list)) – The domain of the objective to be optimized

  • partition – The partition choice of the algorithm. Default: BinaryPartition.

Usage Example

Note

Make sure to use get_last_point() to get the final output

from PyXAB.synthetic_obj.Garland import Garland
from PyXAB.algos.DOO import DOO

domain = [[0, 1]]               # Parameter is 1-D and between 0 and 1
target = Garland()
algo = DOO(domain=domain)

for t in range(1000):
    point = algo.pull(t)
    reward = target(point)
    algo.receive_reward(t, reward)

algo.get_last_point()