Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently

2025/07/10 by Kenshin Abe, Abe, Kenshin, Yunzhuo Wang +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #DNA and Biological Computing #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2507.08053

openalex publication_date 2025/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Tree-structured Parzen estimator (TPE) is a versatile hyperparameter optimization (HPO) method supported by popular HPO tools. Since these HPO tools have been developed in line with the trend of deep learning (DL), the problem setups often used in the DL domain have been discussed for TPE such as multi-objective optimization and multi-fidelity optimization. However, the practical applications of HPO are not limited to DL, and black-box combinatorial optimization is actively utilized in some domains, e.g., chemistry and biology. As combinatorial optimization has been an untouched, yet very important, topic in TPE, we propose an efficient combinatorial optimization algorithm for TPE. In this paper, we first generalize the categorical kernel with the numerical kernel in TPE, enabling us to introduce a distance structure to the categorical kernel. Then we discuss modifications for the newly developed kernel to handle a large combinatorial search space. These modifications reduce the time complexity of the kernel calculation with respect to the size of a combinatorial search space. In the experiments using synthetic problems, we verified that our proposed method identifies better solutions with fewer evaluations than the original TPE. Our algorithm is available in Optuna, an open-source framework for HPO.

Citations

• Fast Benchmarking of Asynchronous Multi-Fidelity Optimization on Zero-Cost Benchmarks
• Multi-Fidelity Methods for Optimization: A Survey
• Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization
• Python Wrapper for Simulating Multi-Fidelity Optimization on HPO Benchmarks without Any Wait
• Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance
• Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings
• Speeding Up Multi-Objective Hyperparameter Optimization by Task Similarity-Based Meta-Learning for the Tree-Structured Parzen Estimator
• c-TPE: Tree-structured Parzen Estimator with Inequality Constraints for Expensive Hyperparameter Optimization
• On the Importance of Hyperparameters and Data Augmentation for Self-Supervised Learning
• Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer
• On the Importance of Hyperparameter Optimization for Model-based Reinforcement Learning
• Bayesian Variational Optimization for Combinatorial Spaces
• On the Importance of Domain Model Configuration for Automated Planning\n Engines
• Optuna: A Next-generation Hyperparameter Optimization Framework
• Combinatorial Bayesian Optimization using the Graph Cartesian Product
• Tune: A Research Platform for Distributed Model Selection and Training
• BOHB: Robust and Efficient Hyperparameter Optimization at Scale
• Bayesian Optimization of Combinatorial Structures
• Deep Reinforcement Learning that Matters
• The CMA Evolution Strategy: A Tutorial
• CMA-ES for Hyperparameter Optimization of Deep Neural Networks
• Practical Bayesian Optimization of Machine Learning Algorithms
• Rethinking Bias Mitigation: Fairer Architectures Make for Fairer Face Recognition
• Taking the Human Out of the Loop: A Review of Bayesian Optimization

Related

• c-TPE: Tree-structured Parzen Estimator with Inequality Constraints for Expensive Hyperparameter Optimization
• Modified Adaptive Tree-Structured Parzen Estimator for Hyperparameter Optimization
• Speeding Up Multi-Objective Hyperparameter Optimization by Task Similarity-Based Meta-Learning for the Tree-Structured Parzen Estimator
• Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance
• HPO X ELA: Investigating Hyperparameter Optimization Landscapes by Means of Exploratory Landscape Analysis