TLDR: A new algorithm for Tree-structured Parzen Estimator (TPE) improves its efficiency in black-box combinatorial optimization by introducing user-defined distance metrics and modifications for large search spaces, leading to better solutions with fewer evaluations compared to the original TPE.
Hyperparameter optimization (HPO) is crucial for machine learning, especially with the rise of deep learning. Tools like Optuna, Hyperopt, and RayTune widely support the Tree-structured Parzen Estimator (TPE) as a core algorithm for HPO. While TPE has proven effective in many applications, its performance in black-box combinatorial optimization, a field important in areas like chemistry and biology, has been limited.
Traditionally, TPE treats each combination in a combinatorial search space as equally similar, which leads to inefficiencies. A recent research paper, titled “Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently,” addresses this challenge by proposing a novel algorithm to enhance TPE’s capabilities in these complex scenarios. The authors, Kenshin Abe, Yunzhuo Wang, and Shuhei Watanabe from Preferred Networks Inc., have made their algorithm available in Optuna, an open-source framework for HPO.
Bridging the Gap in TPE
The core innovation lies in generalizing TPE’s categorical kernel with its numerical kernel. This allows for the natural introduction of a user-defined distance structure between categories, such as the Hamming distance. By incorporating these distance metrics, the algorithm can better understand the relationships between different combinations, moving beyond the previous assumption of equal similarity.
Addressing Large Search Spaces
For practical applications involving very large combinatorial search spaces, the researchers introduced two key modifications. First, they developed an efficient approximation method for calculating the maximum distance, significantly reducing the computational time required. Second, they modified the combinatorial kernel to prevent “overexploration” during optimization. Overexploration can lead to poor performance, especially in vast search spaces, as the algorithm might spend too much time exploring less promising areas. This modification helps TPE focus more effectively, leading to better solutions with fewer evaluations.
Experimental Validation
The proposed method was rigorously tested using synthetic problems, including “EmbeddingCosine” and “PermutationShiftL1.” These experiments compared the new algorithm against the original TPE and random search. The results consistently showed that the proposed method identified superior solutions with significantly fewer evaluations. This improvement was particularly noticeable in problems with larger combinatorial search spaces, where the original TPE and random search often performed indistinguishably. The modifications also proved to enhance the sample efficiency and robustness of the proposed method without degrading performance.
Also Read:
- Navigating Dynamic Software: A New Approach to Online Performance Prediction
- Keeping AI Models Reliable: A New Approach to Monitoring Performance During Adaptation
Implications and Future Directions
The availability of this algorithm in Optuna means that users can more efficiently tackle black-box combinatorial optimization problems, potentially accelerating research and development in various domains. However, the paper also acknowledges limitations. For extremely large combinatorial search spaces, such as permutations of 15 or more elements, both the original TPE and the new approach can still face memory and time complexity challenges. Future work aims to address these limitations through further methodological evaluations, extensive benchmarking, and exploring solutions like limiting combinations during sampling or using parallel setups. You can find more details about this research in the full paper available here.
