High Dimensional Bayesian Optimization with Kernel Principal Component Analysis

Kirill Antonov, Elena Raponi, Hao Wang, Carola DoerrPPSN 2022 · OpenReview

TL;DR

This paper introduces KPCA-BO, a novel Bayesian Optimization (BO) algorithm that tackles the challenge of optimizing high-dimensional problems by performing the optimization on a learned non-linear sub-manifold of the search space. By leveraging Kernel Principal Component Analysis (KPCA), KPCA-BO significantly improves convergence speed and reduces computational cost compared to standard BO and its linear counterpart, PCA-BO, especially in higher dimensions.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is a powerful technique for optimizing expensive-to-evaluate black-box functions. However, its effectiveness plummets in high-dimensional spaces. This is due to two main issues: (1) Gaussian Process Regression (GPR) models, a core component of BO, require exponentially more data to maintain accuracy as dimensionality increases, and (2) optimizing the acquisition function, which guides the search, becomes computationally prohibitive. Existing approaches have tried to mitigate this by selecting relevant variables or searching on linear sub-manifolds. This paper addresses the limitation of linear sub-manifolds by proposing a method to learn and optimize on non-linear sub-manifolds, which are hypothesized to better capture the complex structures of high-dimensional objective functions.

Methods

The core innovation is the Kernel PCA-assisted Bayesian Optimization (KPCA-BO) algorithm. It builds upon the idea of reducing dimensionality by projecting the problem onto a lower-dimensional sub-manifold.

  • Kernel PCA (KPCA): Instead of linear PCA, KPCA is used to learn a non-linear sub-manifold. KPCA maps data into a high-dimensional feature space where linear relationships can be found, effectively capturing non-linear structures in the original space.
  • Forward Map: A function is learned to map points from the original high-dimensional search space ($S \subseteq \mathbb{R}^d$) to the learned lower-dimensional sub-manifold ($M$). This map is constructed using the eigenfunctions derived from KPCA.
  • Backward Map: A crucial component that maps candidate points found in the lower-dimensional space back to the original high-dimensional space for function evaluation. This is achieved by finding a "pre-image" that minimizes the distance to the mapped candidate point.
  • BO on the Sub-manifold: The GPR model and the acquisition function optimization are then performed entirely within this learned lower-dimensional space. This significantly reduces computational burden.
  • Data Rescaling: To ensure KPCA effectively captures the objective function's landscape, the data points are rescaled based on their objective function values. This prioritizes regions of interest for the dimensionality reduction process.

Datasets

The paper evaluates KPCA-BO on ten multi-modal functions (F15-F24) from the COCO/BBOB benchmark suite. These functions are chosen to be representative of challenging objective functions encountered in real-world applications. The experiments are conducted across three dimensions: 20D, 40D, and 60D.

Key Insights and Ideas

  • Non-linear sub-manifolds are crucial: The paper strongly suggests that for many high-dimensional problems, especially those with non-linearly correlated variables, a non-linear sub-manifold is essential for effective optimization, outperforming linear sub-manifolds.
  • KPCA as a powerful dimensionality reduction tool for BO: KPCA offers a principled way to find a lower-dimensional representation that captures significant variance, making BO more tractable.
  • Computational efficiency gains: Performing GPR training and acquisition function optimization in a reduced space dramatically cuts down computation time, a major bottleneck in high-dimensional BO.
  • Trade-off between manifold complexity and convergence: The non-linear manifold learned by KPCA can sometimes stabilize too quickly, leading to premature convergence (stagnation) on certain functions, which is an interesting area for future research.

Key Results

  • Improved Convergence: KPCA-BO consistently outperforms standard BO in terms of convergence speed on most of the tested multi-modal functions.
  • Dimensionality Matters: The benefits of KPCA-BO become more pronounced as dimensionality increases. For 60D functions, KPCA-BO achieves better results than PCA-BO on many test cases.
  • Significant Speedup: KPCA-BO substantially reduces the CPU time required for GPR training and acquisition function optimization compared to vanilla BO, especially in 60D. While PCA-BO also offers speedups, KPCA-BO's non-linear approach provides an edge in capturing complex function landscapes.
  • Competitive with CMA-ES: In many cases, KPCA-BO matches or outperforms CMA-ES, a state-of-the-art evolutionary algorithm, particularly in higher dimensions.

Limitations and Future Work

  • Premature Convergence/Stagnation: The paper notes that the non-linear manifold learned by KPCA can sometimes stabilize too quickly, leading to stagnation. This is observed on functions like F21 and F22, where KPCA-BO's early convergence is eventually surpassed by PCA-BO.
  • Manifold Learning Strategy: The authors suggest exploring alternative strategies for learning the manifold, such as using random subsets of data points instead of the entire dataset, to potentially mitigate premature convergence.
  • Backward Map Improvement: The current backward map is not unique due to the nature of orthogonal projections. Future work could involve biasing the backward map to favor points that are more exploitative or explorative, potentially improving optimization.
  • Kernel Choice Impact: While the RBF kernel is used for simplicity, the paper acknowledges that the choice of kernel could impact the manifold's smoothness and topological properties, which warrants further investigation.

Summary updated

Abstract

Bayesian Optimization (BO) is a surrogate-based global optimization strategy that relies on a Gaussian Process regression (GPR) model to approximate the objective function and an acquisition function to suggest candidate points. It is well-known that BO does not scale well for high-dimensional problems because the GPR model requires substantially more data points to achieve sufficient accuracy and acquisition optimization becomes computationally expensive in high dimensions. Several recent works aim at addressing these issues, e.g., methods that implement online variable selection or conduct the search on a lower-dimensional sub-manifold of the original search space. Advancing our previous work of PCA-BO that learns a linear sub-manifold, this paper proposes a novel kernel PCA-assisted BO (KPCA-BO) algorithm, which embeds a non-linear sub-manifold in the search space and performs BO on this sub-manifold. Intuitively, constructing the GPR model on a lower-dimensional sub-manifold helps improve the modeling accuracy without requiring much more data from the objective function. Also, our approach defines the acquisition function on the lower-dimensional sub-manifold, making the acquisition optimization more manageable. We compare the performance of KPCA-BO to a vanilla BO and to PCA-BO on the multi-modal problems of the COCO/BBOB benchmark suite. Empirical results show that KPCA-BO outperforms BO in terms of convergence speed on most test problems, and this benefit becomes more significant when the dimensionality increases. For the 60D functions, KPCA-BO achieves better results than PCA-BO for many test cases. Compared to the vanilla BO, it efficiently reduces the CPU time required to train the GPR model and to optimize the acquisition function compared to the vanilla BO.
BibTeX
@inproceedings{antonov2022high,
  author = {Kirill Antonov and Elena Raponi and Hao Wang and Carola Doerr},
  title = {{High Dimensional Bayesian Optimization with Kernel Principal Component Analysis}},
  booktitle = {PPSN},
  year = {2022},
  url = {https://openreview.net/forum?id=Ph5dw89ePP},
}
Figure