Timezone: »

 
Poster
Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel
Changyong Oh · Roberto Bondesan · Efstratios Gavves · Max Welling

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #503
in Poster Session 6 »

In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. We then apply the framework to permutation problems, which have so far received little attention in the Bayesian Optimization literature, despite their practical importance. We call this method LAW2ORDER. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret is sublinear. Empirically, we assess the method on several standard combinatorial problems involving permutations such as quadratic assignment, flowshop scheduling and the traveling salesman, as well as on a structure learning task.

Keywords: Bayesian optimization · bandit · Regret Analysis · Permutation · Batch Acquisition · Determinantal Point Processes · Information Gain

Author Information

Changyong Oh (University of Amsterdam)
Roberto Bondesan (Imperial College London)
Efstratios Gavves (University of Amsterdam)

Dr. Efstratios Gavves is an Associate Professor at the University of Amsterdam in the Netherlands, an ELLIS Scholar, and co-founder of Ellogon.AI. He is a director of the QUVA Deep Vision Lab with Qualcomm, and the POP-AART Lab with the Netherlands Cancer Institute and Elekta. Efstratios received the ERC Career Starting Grant 2020, and NWO VIDI grant 2020 to research on the Computational Learning of Time for spatiotemporal sequences and video. His background is in Computer Vision. Currently, his research interests lie in the Machine Learning of Time and Dynamics, and its applications to Vision and Sciences.

Max Welling (Microsoft Research AI4Science / University of Amsterdam)

More from the Same Authors