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