Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization

Xingchen Ma, Matthew B. Blaschko

TL;DR

This paper introduces a novel "Additive Tree-Structured Covariance Function" (Add-Tree) for Bayesian Optimization (BO) that effectively leverages conditional parameter spaces structured as trees. By combining the tree structure with an additive assumption, their method achieves improved sample efficiency and broader applicability compared to existing state-of-the-art techniques, particularly in low-data regimes.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is a powerful technique for optimizing expensive-to-evaluate black-box functions. However, its performance can degrade significantly in high-dimensional parameter spaces. Many real-world problems exhibit a conditional structure in their parameter spaces, where the relevance of certain parameters depends on the values of others. Existing BO methods often treat these spaces as flat or rely on tree-like structures in restrictive ways. This paper addresses the challenge of efficiently optimizing functions over such tree-structured conditional parameter spaces, aiming to improve sample efficiency and flexibility by explicitly modeling this structure.

Methods

The core contribution is the Additive Tree-Structured Covariance Function (Add-Tree). This covariance function is designed to work with Gaussian Processes (GPs) within the BO framework. It leverages two key ideas:

  1. Tree Structure: The parameter space is explicitly represented as a tree, where nodes represent parameters and edges represent conditional dependencies. This allows the model to understand how parameters relate to each other.
  2. Additive Assumption: For each path from the root to a leaf in the tree, the function is assumed to be an additive combination of its constituent parameters. This is a common assumption in GP literature for dimension reduction and information sharing.

By combining these, the Add-Tree covariance function enables information sharing across different branches of the tree, even for parameters at shared nodes. The authors also propose a parallel algorithm for optimizing the acquisition function, which further enhances efficiency by operating in lower-dimensional spaces derived from the tree structure.

Datasets

The paper evaluates its method on:

  • A synthetic tree-structured benchmark function (originally presented in Jenatton et al., 2017).
  • A real-world application: neural network model compression for a three-layer fully connected network (FC3) on the MNIST dataset.

No new datasets were introduced.

Key Insights and Ideas

  • Information Sharing is Crucial: The Add-Tree covariance function's main advantage stems from its ability to share information between different data points, especially in low-data scenarios. This is achieved by exploiting the additive structure and the shared nodes in the tree.
  • Structure is Power: Explicitly modeling the tree structure of the parameter space, rather than treating it as flat, leads to significant improvements in sample efficiency. This allows the model to focus its search more effectively.
  • Flexibility Beyond Restrictions: Unlike some prior work, Add-Tree is more flexible in how it handles conditional structures, allowing for continuous variables at shared nodes and not imposing overly restrictive assumptions.
  • Parallelism for Efficiency: The proposed parallel acquisition function optimization algorithm is a practical enhancement, making the overall BO process faster.

Key Results

  • Synthetic Experiments: Add-Tree significantly outperformed competing methods (SMAC, TPE, random search, standard GP-based BO, and Jenatton et al.'s tree-based approach) on a synthetic tree-structured function, achieving much better performance in fewer iterations.
  • Regression Performance: In a regression setting, Add-Tree demonstrated superior sample efficiency compared to independent GPs, especially when training data is scarce, highlighting its effective information sharing.
  • Model Compression: On a neural network model compression task, Add-Tree converged significantly faster than other methods, showcasing its practical utility in optimizing complex, structured problems.
  • Statistical Significance: Wilcoxon signed-rank tests confirmed that Add-Tree performed significantly better than other methods on both the synthetic and model compression tasks.

Limitations and Future Work

  • Additive Assumption: The paper acknowledges that if there are significant interaction effects between variables along a single path (beyond the additive assumption), the proposed method might lose some potential sample efficiency. They suggest combining Add-Tree with higher-order additive kernels to address this, but note that modeling covariances between interaction terms can be challenging.
  • Time Complexity: While Add-Tree requires fewer black-box calls (which are expensive), its inference time complexity can be higher than some other methods in certain tree structures (e.g., dense gram matrices when the root has a shared continuous parameter). However, this is often a worthwhile trade-off given the reduction in expensive function evaluations.
  • Future Work: The authors mention that in Appendix E, they discuss the case where the additive assumption is not enough to model the objective function, suggesting avenues for extending the framework to handle more complex interactions.

Summary updated

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 are usually built on trees. In this work, we generalize the additive assumption to tree-structured functions and propose an additive tree-structured covariance function, showing improved sample-efficiency, wider applicability and greater flexibility. Furthermore, by incorporating the structure information of parameter spaces and the additive assumption in the BO loop, we develop a parallel algorithm to optimize the acquisition function and this optimization can be performed in a low dimensional space. We demonstrate our method on an optimization benchmark function, as well as on a neural network model compression problem, and experimental results show our approach significantly outperforms the current state of the art for conditional parameter optimization including SMAC, TPE and Jenatton et al. (2017).
BibTeX
@inproceedings{ma2020additive,
  author = {Xingchen Ma and Matthew B. Blaschko},
  title = {{Additive Tree-Structured Covariance Function for Conditional Parameter Spaces in Bayesian Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=UUS4IBUmWAz7},
}
Figure