Optimization on Manifolds via Graph Gaussian Processes

Optimization problems on manifolds are ubiquitous in science and engineering. For instance, lowrank matrix completion and rotational alignment of 3D bodies can be formulated as optimization problems over spaces of matrices that are naturally endowed with manifold structures. These matrix manifolds belong to agreeable families [56] for which Riemannian gradients, geodesics, and other geometric quantities have closed-form expressions that facilitate the use of Riemannian optimization algorithms [19, 1, 9]. In contrast, this paper is motivated by optimization problems where the search space is a manifold that the practitioner can only access through a discrete point cloud representation, preventing direct use of Riemannian optimization algorithms. Moreover, the hidden manifold may not belong to an agreeable family, further hindering the use of classical methods. Illustrative examples where manifolds are represented by point cloud data include computer vision, robotics, and shape analysis of geometric morphometrics [33, 23, 25]. Additionally, across many applications in data science, high-dimensional point cloud data contains low-dimensional structure that can be modeled as a manifold for algorithmic design and theoretical analysis [14, 3, 27]. Motivated by these problems, this paper introduces a Bayesian optimization method with convergence guarantees to optimize an expensive-to-evaluate function on a point cloud of manifold samples.