Abstract
Bayesian optimization (BO) is a sample-efficient global optimization algorithm for black-box functions which are expensive to evaluate. Existing literature on model-based optimization in conditional parameter spaces often fails to share information across different branches or suffers from the curse of dimensionality. This paper introduces Add-Tree, a novel covariance function that leverages an additive functional assumption over tree-structured parameter spaces. By modeling the objective function as a sum of components associated with nodes along a path, Add-Tree enables effective information sharing and efficient optimization in low-dimensional subspaces. Empirical results on synthetic benchmarks and real-world model compression tasks demonstrate that Add-Tree significantly outperforms state-of-the-art methods like SMAC and TPE.
Introduction
In many complex optimization scenarios, the relevance of certain parameters is conditional upon the values of others. This is particularly prevalent in machine learning hyperparameter tuning and engineering design. For example, in a model selection task, choosing a "Random Forest" classifier triggers the need to tune max_depth, whereas selecting a "Support Vector Machine" (SVM) requires tuning gamma. These dependencies naturally form a conditional parameter space, often visualized as a tree structure.
Standard BO approaches struggle with such spaces. Treating the entire space as a single high-dimensional block leads to the "curse of dimensionality," where the number of samples required grows exponentially. Conversely, modeling each path in the tree independently prevents the algorithm from sharing information across branches—for instance, a "learning rate" parameter might have a similar effect regardless of the specific classifier chosen. Existing tree-based Gaussian Process (GP) models often fail to strike a balance between flexibility and information sharing.
The Add-Tree Methodology
The authors propose the Additive Tree-Structured (Add-Tree) Covariance Function to address these challenges. The approach is built on two key innovations:
1. The Additive Functional Assumption
The core idea is that the objective function $f$ can be decomposed into a sum of functions, each corresponding to a node in the parameter tree. For any given input $x$, the function value is the sum of contributions from all nodes on the path from the root to the leaf corresponding to $x$. This structure allows the model to explicitly capture the influence of "ancestor" variables that are shared across multiple branches.
2. Add-Tree Kernel and Parallel Optimization
The Add-Tree kernel calculates the similarity between two points based on their shared path in the tree. If two points share a set of parent nodes, the kernel facilitates learning from both points to update the GP's understanding of those shared variables.
To efficiently find the next point for evaluation, the authors developed Add-Tree-GP-UCB. This algorithm leverages the additive structure to parallelize the optimization of the acquisition function (Upper Confidence Bound). Instead of searching the full $d$-dimensional space, the optimization is broken down into independent sub-problems for each node, operating in much lower-dimensional "effective" subspaces.
Experimental Results
The performance of Add-Tree was evaluated against several baselines, including SMAC, TPE, and independent GP models.
Synthetic Benchmark
The first test involved a synthetic tree-structured function with a total dimensionality of 9, but an effective dimensionality of only 2 for any specific path. Add-Tree demonstrated remarkably fast convergence, reaching a near-optimal solution (log-distance of -12) within 100 iterations, while competitors struggled to reach even -4.
Neural Network Model Compression
A real-world application was explored through the compression of a three-layer fully connected network (FC3) trained on the MNIST dataset. The optimizer had to decide between Singular Value Decomposition (SVD) and Weight Pruning (WP) for each layer, subsequently tuning the resulting hyperparameters (rank or threshold).
In this task, Add-Tree again showed superior convergence speed and final performance. Statistical significance was confirmed using pairwise Wilcoxon signed-rank tests ($\alpha = 0.05$), highlighting the robustness of the approach.
Key Insights
- Information Sharing: By explicitly modeling shared ancestor variables, Add-Tree can learn from data points even if they reside in different branches of the parameter tree. This significantly improves sample efficiency; in regression tests, Add-Tree required only 24 observations to reach an error threshold of $10^{-4}$, compared to 44 for independent GPs.
- Dimensionality Reduction: The tree structure allows the algorithm to focus on the "effective dimension" of specific paths, avoiding the overhead of the full parameter space.
- Computational Efficiency: The additive assumption enables the decomposition of the acquisition function optimization, allowing for parallel processing and faster iteration times.
Conclusion and Future Work
Add-Tree represents a significant step forward in Bayesian Optimization for conditional spaces. By combining an additive functional assumption with tree-structured kernels, it achieves high sample efficiency and scalability. However, the method relies on the validity of the additive assumption and requires a predefined tree structure. Future research could investigate ways to relax these requirements, perhaps by learning the tree structure automatically or modeling higher-order interactions between nodes.
This paper was presented at AISTATS 2020.
Summary updated