Extrinsic Bayesian Optimization on Manifolds

Yihao Fang, Mu Niu, Pokman Cheung, Lizhen LinAlgorithms 2023 · DOI

TL;DR

This paper introduces "Extrinsic Bayesian Optimization" (eBO), a novel framework for optimizing functions defined on complex geometric spaces called manifolds. By embedding these manifolds into a higher-dimensional Euclidean space, eBO leverages existing Bayesian optimization techniques to efficiently find optimal solutions, even when gradients are unavailable or expensive to compute.

What Problem Does This Paper Address?

Many real-world problems involve optimizing functions where the input variables are constrained to lie on specific geometric structures, known as manifolds. These can include things like shapes, orientations, or positive definite matrices, which don't behave like simple flat Euclidean spaces. Traditional optimization methods, especially those that rely on gradients, struggle with these geometric constraints. While some methods exist for optimizing on manifolds, they often require explicit knowledge of gradients, which can be difficult or impossible to obtain. Bayesian Optimization (BO) is a powerful gradient-free optimization technique, but adapting it to manifolds is challenging due to the difficulty of defining appropriate probabilistic models (Gaussian Processes) on these curved spaces.

Methods

The core innovation of this paper is the extrinsic Bayesian optimization (eBO) framework. The key idea is to:

  • Embed the Manifold: The manifold $M$ is mapped into a higher-dimensional Euclidean space $\mathbb{R}^D$ using an embedding map $J$. This map preserves the local geometry of the manifold.
  • Extrinsic Gaussian Processes (eGPs): A standard Gaussian Process (GP) is then defined on the embedded manifold in $\mathbb{R}^D$. This allows for the construction of valid covariance kernels by leveraging kernels defined on Euclidean spaces. The covariance kernel on the manifold $R(x,z)$ is defined based on the kernel on the embedded space $\tilde{R}(J(x), J(z))$.
  • Bayesian Optimization Loop: The standard Bayesian Optimization loop is then applied:
  • A probabilistic model (the eGP) is built for the objective function.
  • An acquisition function (e.g., probability of improvement) is used to intelligently select the next point to evaluate.
  • The objective function is evaluated at the chosen point.
  • The model is updated, and the process repeats.
  • Mapping Back: Crucially, the optimization of the acquisition function happens in the embedded Euclidean space. The resulting optimal point in the embedded space is then mapped back to the original manifold using the inverse embedding map $J^{-1}$.

This "extrinsic" approach circumvents the need to develop complex intrinsic kernels directly on the manifold.

Datasets

The paper evaluates the eBO framework on simulated data and real-world datasets across several types of manifolds:

  • Sphere ($S^2$): Used for simulating Fréchet mean estimation.
  • Grassmann Manifold: Used for a matrix approximation problem.
  • Manifold of Positive Definite Matrices (SPD(p)): Used for a kernel regression problem on diffusion tensor imaging (DTI) data. The DTI dataset consists of 46 subjects (28 HIV+ and 18 healthy controls), with diffusion tensors extracted along an atlas fiber tract.

No new datasets were introduced; existing benchmarks and real-world data were utilized.

Key Insights and Ideas

  • Bridging Manifolds and Euclidean BO: The extrinsic approach elegantly allows us to leverage the well-developed theory and algorithms of Bayesian Optimization in Euclidean spaces for problems on manifolds.
  • Gradient-Free Power on Curved Spaces: eBO provides a powerful gradient-free optimization tool for manifolds, which is crucial when gradient information is unavailable or computationally prohibitive.
  • Flexibility of Embedding: The choice of embedding map is key. The paper highlights that different manifolds (sphere, SPD matrices, Grassmannian) require specific embedding strategies (e.g., identity map for sphere, log-map for SPD matrices).
  • Fréchet Mean Estimation: eBO can efficiently estimate Fréchet means on manifolds, demonstrating its utility in statistical inference.
  • Data-Driven Insights: The application to DTI data shows eBO can reveal subtle differences between groups (HIV+ vs. healthy) by modeling diffusion tensors on the SPD manifold.

Key Results

  • Sphere: The eBO method demonstrated convergence to the true Fréchet mean, showing comparable accuracy to gradient descent (GD) but with a different convergence profile.
  • Grassmann Manifold: For a matrix approximation problem, eBO converged to the optimal subspace significantly faster (around 10 steps) than the Nelder-Mead method (around 25 steps).
  • Positive Definite Matrices (DTI Data): eBO was used for kernel regression on diffusion tensor data. The estimated diffusion tensors showed observable differences between HIV+ and healthy groups, and a two-sample test yielded a very small p-value ($O(10^{-5})$), indicating a significant difference between the groups.

Limitations and Future Work

  • Extrinsic vs. Intrinsic: The paper acknowledges that the extrinsic approach relies on the quality of the embedding. While effective, it might not always be the most geometrically faithful representation.
  • Future Work: The authors suggest investigating intrinsic Bayesian optimizations on manifolds, which would involve developing Gaussian Processes directly on the manifold using intrinsic kernels (e.g., based on heat kernels). This could potentially offer further advantages in certain scenarios.

Summary updated

BibTeX
@article{fang2023extrinsic,
  author = {Yihao Fang and Mu Niu and Pokman Cheung and Lizhen Lin},
  title = {{Extrinsic Bayesian Optimization on Manifolds}},
  journal = {Algorithms},
  year = {2023},
  doi = {10.3390/a16020117},
}
Figure