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.
| Type: | Proceedings paper |
|---|---|
| Title: | Optimistic tree search strategies for black-box combinatorial optimization |
| Event: | 36th Conference on Neural Information Processing Systems (NeurIPS 2022). |
| ISBN-13: | 9781713871088 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.neurips.cc/paper_files/paper/2... |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10185811 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
