2020/06/24 by Nika, Andi, Elahi, Sepehr, Ararat, Çağın +1
#Applications (stat.AP) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2006.14061
We consider the problem of optimizing a vector-valued objective function \boldsymbolf sampled from a Gaussian Process (GP) whose index set is a well-behaved, compact metric space (\cal X,d) of designs. We assume that \boldsymbolf is not known beforehand and that evaluating \boldsymbolf at design x results in a noisy observation of \boldsymbolf(x). Since identifying the Pareto optimal designs via exhaustive search is infeasible when the cardinality of \cal X is large, we propose an algorithm, called Adaptive \boldsymbolε-PAL, that exploits the smoothness of the GP-sampled function and the structure of (\cal X,d) to learn fast. In essence, Adaptive \boldsymbolε-PAL employs a tree-based adaptive discretization technique to identify an \boldsymbolε-accurate Pareto set of designs in as few evaluations as possible. We provide both information-type and metric dimension-type bounds on the sample complexity of \boldsymbolε-accurate Pareto set identification. We also experimentally show that our algorithm outperforms other Pareto set identification methods.