Better Search Methods for Derivative-free Optimization
Non-convex global optimization problems are well-known to be NP-hard, and the practical challenge lies in distinguishing the global optimum from exponentially many potential local optima. Existing approaches to non-convex optimization can be largely categorized into sampling-based methods and tree-search methods. Sampling-based approaches explore the solution space through random sampling and guide search strategies with the minimal assumptions about the objective function.
Sampling methods can be designed to asymptotically converge towards the global optimum, but suffer from the curse-of-dimensionality in practice. Tree search and interval-based optimization methods leverage branch-and-bound techniques that maintain a partition tree over the domain to systematically prune the space towards global optima. The size of the search tree can quickly become exponential in the number of dimensions and is the major bottleneck for scaling up.
Figure 1. Steps in each iteration of the MCIR algorithm.
Figure 2. Overall performance of the baselines of MCIR on Biggsbil, Harkerp, Watson, and Neural Networks.
We propose an approach that combines the benefits of sampling-based and tree-based approaches as well as interval bounding and local optimization techniques, by taking advantage of the recent progress in Monte Carlo Tree Search (MCTS) methods. We assume that the analytic form of the objective function is known over a compact domain, so that we can use interval bounding on the function value and its local first-order and second-order information in different parts of the MCTS design. A key feature of the Monte Carlo trees is that the growth of the tree is driven by samples rather than partitions, and hence the name Sample-and-Bound. By associating the analytic and estimated properties of adjustable neighborhoods around each sample, we design the MCTS algorithm to best balance exploration and exploitation based on the important numerical properties of the objective function.
We evaluated the proposed algorithms against a wide range of existing algorithms and analyze the importance of various hyper parameters. Experiments results on standard benchmark problem sets demonstrated clear benefits of the proposed approach.