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
BKTFrandommitigates 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