Bayesian Kernelized Tensor Factorization as Surrogate for Bayesian Optimization

Mengying Lei, Lijun Sun

Abstract

Bayesian optimization (BO) primarily uses Gaussian processes (GP) as the key surrogate model, mostly with a simple stationary and separable kernel function such as the squared-exponential kernel with automatic relevance determination (SE-ARD). However, such simple kernel specifications are deficient in learning functions with complex features, such as being nonstationary, nonseparable, and multimodal. Approximating such functions using a local GP, even in a low-dimensional space, requires a large number of samples, not to mention in a high-dimensional setting. In this paper, we propose to use Bayesian Kernelized Tensor Factorization (BKTF) -- as a new surrogate model -- for BO in a $D$-dimensional Cartesian product space. Our key idea is to approximate the underlying $D$-dimensional solid with a fully Bayesian low-rank tensor CP decomposition, in which we place GP priors on the latent basis functions for each dimension to encode local consistency and smoothness. With this formulation, information from each sample can be shared not only with neighbors but also across dimensions. Although BKTF no longer has an analytical posterior, we can still efficiently approximate the posterior distribution through Markov chain Monte Carlo (MCMC) and obtain prediction and full uncertainty quantification (UQ). We conduct numerical experiments on both standard BO test functions and machine learning hyperparameter tuning problems, and our results show that BKTF offers a flexible and highly effective approach for characterizing complex functions with UQ, especially in cases where the initial sample size and budget are severely limited.

Introduction

Bayesian optimization (BO) is a standard framework for optimizing expensive "black-box" functions, such as hyperparameter tuning for deep neural networks. Traditionally, BO relies on Gaussian Processes (GPs) as surrogate models. However, standard GPs typically employ simple kernels that assume the underlying function is stationary and separable. In practice, objective functions are often complex—exhibiting sharp peaks, flat plateaus, and intricate dependencies between variables. Standard GPs struggle to capture these nonstationary and nonseparable features without a prohibitive number of samples, often leading to sub-optimal results or slow convergence.

Methodology and Key Insights

To address these limitations, researchers from McGill University introduced Bayesian Kernelized Tensor Factorization (BKTF). BKTF discretizes the search space into a Cartesian product grid and represents the objective function as a multi-dimensional tensor. This tensor is then approximated using a low-rank CANDECOMP/PARAFAC (CP) decomposition, breaking the complex $D$-dimensional function into a sum of products of $D$ latent basis functions.

To ensure smoothness and local consistency, the model places GP priors on these 1D latent basis functions. BKTF adopts a fully Bayesian approach, treating basis functions, weights, and kernel hyperparameters as random variables, with the posterior distribution approximated via Markov chain Monte Carlo (MCMC) sampling. For decision-making, a Bayesian variant of the Upper Confidence Bound (B-UCB) is calculated directly from the MCMC samples.

BKTF demonstrates superior surface estimation and acquisition compared to standard GP models, capturing global structures more effectively.

A primary advantage of BKTF is its implicit "multilinear product kernel," which is naturally nonstationary and nonseparable. This allows the model to adapt its correlation structure to different regions of the search space. Furthermore, the tensor factorization structure enables efficient information sharing; a single observation provides information that is shared not just with immediate neighbors but across entire dimensions, making the model exceptionally sample-efficient.

Experimental Results

The authors evaluated BKTF against standard GP baselines and Tree-structured Parzen Estimators (TPE) using a suite of synthetic benchmark functions (e.g., Branin, Damavandi, Schaffer, Griewank, Hartmann) and real-world machine learning hyperparameter tuning tasks (MNIST and Boston Housing).

BKTF consistently outperforms GP-based methods across various benchmark functions, showing faster convergence to the global optimum.

BKTF demonstrated superior convergence across all benchmarks. Notably, on the "Damavandi" function—where the global optimum is hidden in a tiny area far from a large local optimum—standard GPs failed completely, while BKTF found the global optimum within just 10 iterations. In ML tuning tasks, BKTF achieved 100% accuracy on MNIST neural network tuning in fewer than four evaluations, significantly outperforming baseline methods. The MCMC-based approach also provided robust uncertainty quantification, which is critical for balancing exploration and exploitation in BO.

Discussion and Future Work

While BKTF excels at capturing global structure and handling complex function landscapes, it currently requires the search space to be defined as a Cartesian product grid. This discretization can lead to computational overhead in very high-dimensional spaces. Future research directions include performing acquisition directly using latent basis functions to bypass full tensor reconstruction and integrating local GP components to further refine the model's local precision.

Summary updated

Abstract

Bayesian optimization (BO) primarily uses Gaussian processes (GP) as the key surrogate model, mostly with a simple stationary and separable kernel function such as the squared-exponential kernel with automatic relevance determination (SE-ARD). However, such simple kernel specifications are deficient in learning functions with complex features, such as being nonstationary, nonseparable, and multimodal. Approximating such functions using a local GP, even in a low-dimensional space, requires a large number of samples, not to mention in a high-dimensional setting. In this paper, we propose to use Bayesian Kernelized Tensor Factorization (BKTF) -- as a new surrogate model -- for BO in a $D$-dimensional Cartesian product space. Our key idea is to approximate the underlying $D$-dimensional solid with a fully Bayesian low-rank tensor CP decomposition, in which we place GP priors on the latent basis functions for each dimension to encode local consistency and smoothness. With this formulation, information from each sample can be shared not only with neighbors but also across dimensions. Although BKTF no longer has an analytical posterior, we can still efficiently approximate the posterior distribution through Markov chain Monte Carlo (MCMC) and obtain prediction and full uncertainty quantification (UQ). We conduct numerical experiments on both standard BO test functions and machine learning hyperparameter tuning problems, and our results show that BKTF offers a flexible and highly effective approach for characterizing complex functions with UQ, especially in cases where the initial sample size and budget are severely limited.
BibTeX
@misc{lei2023bayesian,
  author = {Mengying Lei and Lijun Sun},
  title = {{Bayesian Kernelized Tensor Factorization as Surrogate for Bayesian Optimization}},
  year = {2023},
  eprint = {2302.14510},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.14510},
}
Figure