Malherbe, C; Grosnit, A; Tutunov, R; Wang, J; Bou-Ammar, H; (2022) Optimistic tree search strategies for black-box combinatorial optimization. In: Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS 2022). NeurIPS

Preview

PDF 513_optimistic_tree_searches_for_c.pdf - Published Version Download (2MB) | Preview

Abstract

The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and the lack of natural ordering pose significant challenges for the current techniques from both theoretical and practical perspectives. In this paper, we propose to introduce and analyze novel combinatorial black-box solvers that are based on the recent advances in tree search strategies and partitioning techniques. A first contribution is the analysis of an algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the objective function to be known. We provide linear convergence rates for this algorithm which are shown to improve upon the logarithmic rates of the baselines under specific conditions. Then, an adaptive version of OLTS, called Optimistic Combinatorial Tree Search (OCTS), is introduced for a more realistic setup where we do not have any information on the Lipschitz constant of the function. Again, similar linear rates are shown to hold for OCTS. Finally, a numerical assessment is provided to illustrate the potential of tree searches with respect to state-of-the-art methods over typical benchmarks.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item