Bayesian Kernelized Tensor Factorization as Surrogate for Bayesian Optimization

Mengying Lei, Lijun SunSubmission to NeurIPS 2024 · Rejected

TL;DR

Bayesian optimization (BO) usually relies on Gaussian processes (GPs) with stationary, separable kernels that struggle on multi-modal, non-stationary functions. This paper introduces Bayesian Kernelized Tensor Factorization (BKTF), an expressive surrogate model that represents the objective function using low-rank tensor CP decomposition with 1D Gaussian process priors on the latent factors. This architecture enables global information sharing across dimensions, easily accommodates mixed continuous and categorical variables, and avoids getting trapped in local optima under tight evaluation budgets.

What Problem Does This Paper Address?

Traditional BO relies heavily on GP regression paired with standard kernels like Automatic Relevance Determination (ARD) Squared-Exponential or Matérn kernels. Because these kernels are stationary and separable, spatial correlation decays rapidly as distance or dimensionality grows. When the objective function exhibits long-range dependencies, abrupt shifts (non-stationarity), complex interactions (non-separability), or deceptive local optima, standard GP surrogates become shortsighted and waste scarce evaluation budgets.

Furthermore, optimizing functions with mixed variable types (continuous, integer, and categorical) often requires cumbersome ad-hoc kernel configurations.

Methods

The authors recast the search space as a $D$-dimensional tensor grid and model the objective via a fully Bayesian low-rank CANDECOMP/PARAFAC (CP) tensor decomposition:

$$f(\boldsymbol{x}) \approx \sum_{r=1}^R \lambda_r \prod_{d=1}^D g_d^r(x_d)$$

Key components include:

  • GP Priors on Latent Factors: For continuous dimensions, 1D GP priors (Matérn 3/2) are placed directly on each latent factor vector $g_d^r$, with log-normal hyperpriors placed on the lengthscale parameters.
  • Categorical Handling: For categorical dimensions, latent factor covariances are governed by Wishart priors on precision matrices, smoothly incorporating discrete variables.
  • Two-Layer Deep GP Equivalence: Marginalizing out the rank weights $\{\lambda_r\}$ yields an implicit multilinear product kernel that is inherently non-stationary and non-separable across dimensions.
  • MCMC Inference & B-UCB: Without an analytical posterior, model parameters are sampled via Gibbs sampling (factors) and slice sampling (hyperparameters). A Bayesian Upper Confidence Bound (B-UCB) is constructed over the grid using MCMC posterior samples.
  • BKTFrandom: For higher-dimensional problems ($D > 10$) where full tensor construction becomes intractable, a randomized candidate-sampling variant evaluates the acquisition function over a subset of candidate points.

Datasets

The authors evaluated BKTF across synthetic benchmarks and real-world ML hyperparameter tuning problems:

  • Synthetic Benchmarks: Seven global optimization functions spanning $D = 2$ to $D = 10$, including Branin (2D), Damavandi (2D), Schaffer (2D), Griewank (3D, 4D, 10D), Hartmann (6D), and an additional custom non-stationary/non-separable 2D function.
  • Machine Learning Hyperparameter Tuning:
  • MNIST classification: Tuning Random Forest (6 mixed hyperparameters) and Neural Network (6 mixed hyperparameters) architectures.
  • Boston Housing regression: Tuning Random Forest (4 hyperparameters) and Neural Network (3 hyperparameters).

Key Insights and Ideas

  • Information Sharing Across Dimensions: Because BKTF breaks down the response into 1D latent basis curves, an observation at one location updates basis functions across all coordinates. This enables the model to infer trends across unobserved slices of the search space, escaping flat regions and deceptive basins.
  • Interpretable Latent Factors: Visualizing the sampled 1D latent factors reveals underlying global structures—such as periodicity in Griewank—without needing a handcrafted periodic kernel.
  • Robustness to Rank Specification: Unlike many factor models that are brittle to rank hyperparameter choices, fully Bayesian inference protects BKTF from severe overfitting across CP ranks $R \in \{2, 4, 6, 8\}$.

Key Results

  • Escaping Deceptive Basins: On the 2D Damavandi function, standard GP surrogates consistently stalled at a local minimum (regret $\approx 2.00$). BKTF reached the global optimum (regret $0.00$) within roughly 5 evaluations.
  • Benchmark Domination: Across all test functions, BKTF achieved the highest overall Performance Profile Area Under the Curve (AUC = 199.51), outperforming GP-EI (186.49), GP-UCB (185.75), Additive GP (185.40), deepGP, and SAASBO.
  • ML Hyperparameter Tuning:
  • On MNIST, BKTFrandom achieved the top classification accuracy: $96.38\%$ for Random Forest and $98.16\%$ for Neural Networks (surpassing GP-EI's $96.10\%$ and $98.04\%$).
  • On Boston Housing, BKTF achieved the lowest MSE ($25.03$ on Random Forest vs. $26.19$ for GP-EI; $30.84$ on Neural Networks vs. $36.40$ for BO-TPE and $38.46$ for GP-EI).

Limitations and Future Work

  • Curse of Dimensionality on Grid Representations: Dense tensor representations scale exponentially ($\prod_{d=1}^D |S_d|$). While BKTFrandom mitigates this, BKTF currently targets problems where $D \le 10$.
  • MCMC Overhead: Sampling latent basis factors and hyperparameters introduces higher per-iteration computational costs than closed-form GP posterior formulas.
  • Future Directions: Integrating sparse GP methods or Gaussian Markov Random Fields (GMRFs) for large per-dimension grids, and identifying the tensor maximum directly from latent factor vectors without explicitly constructing the dense tensor.

Summary updated

Abstract

Bayesian optimization (BO) mainly uses Gaussian processes (GP) with a stationary and separable kernel function (e.g., the squared-exponential kernel with automatic relevance determination [SE-ARD]) as the surrogate model. However, such localized kernel specifications are deficient in learning complex functions that are non-stationary, non-separable and multi-modal. In this paper, we propose using Bayesian Kernelized Tensor Factorization (BKTF) as a new surrogate model for Bayesian optimization (BO) in a $D$-dimensional grid with both continuous and categorical variables. 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, the information from each sample can be shared not only with neighbors but also across dimensions, thus fostering a more global search strategy. Although BKTF no longer has an analytical posterior, we efficiently approximate the posterior distribution through Markov chain Monte Carlo (MCMC). We conduct numerical experiments on several test functions with continuous variables and two machine learning hyperparameter tuning problems with mixed variables. The results show that BKTF offers a flexible and highly effective approach to characterizing and optimizing complex functions, 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},
}

Loading related content...

Figure