Timezone: »

 
Spotlight
Optimistic Tree Searches for Combinatorial Black-Box Optimization
Cedric Malherbe · Antoine Grosnit · Rasul Tutunov · Haitham Bou Ammar · Jun Wang

Wed Dec 07 09:00 AM -- 11:00 AM (PST) @
in Lightning Talks 3B-1 »

The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and lack of natural ordering pose significant challenges for current techniques from a theoretical and practical perspective, and require new algorithmic ideas. In this paper, we propose to adapt the recent advances in tree searches and partitioning techniques to design and analyze novel black-box combinatorial solvers. A first contribution is the analysis of a first tree-search algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the function to be known. Linear convergence rates are provided for this algorithm under specific conditions, improving upon the logarithmic rates of baselines. An adaptive version, called Optimistic Combinatorial Tree Search (OCTS), is then introduced for the more realistic setup where we do not have any information on the Lipschitz constant of the function. Similar theoretical guarantees are shown to hold for OCTS and a numerical assessment is provided to illustrate the potential of tree searches with respect to state-of-the-art methods over typical benchmarks.

Keywords: Optimization · tree search · combinatorial · Black-box

Author Information

Cedric Malherbe (Huawei Noah's Ark Lab)
Antoine Grosnit (Huawei Technologies Ltd.)
Rasul Tutunov (Massachusetts Institute of Technology)
Haitham Bou Ammar (Huawei R&D UK)
Jun Wang (UCL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors