Convex optimization in nonpositively curved geodesic spaces

Adrian Lewis
ORIE Cornell

In various disciplines, data sets live in Hadamard spaces: complete metric spaces with nonpositive curvature, meaning that triangles are thinner than their Euclidean analogues.  Examples include manifolds like Euclidean space, hyperbolic space, and the cone of positive-definite matrices with the affine-invariant metric.  However, models ranging from robotics to phylogenetics involve Hadamard spaces that are not manifolds:  one interesting example is the BHV tree space, which is a complex of orthants.  Hadamard spaces invite convex optimization techniques, because squared-distance functions to points are strongly convex along geodesics. We might, for example, seek to compute means or minimum enclosing balls for sets of matrices or phylogenetic trees.  A fundamental challenge is the lack of any duality theory.  Nonetheless, the convex geometry of Hadamard space is rich enough to support practical generalizations of the subgradient method, both in classical and incremental forms, supported by complexity analysis.  In the particular case of CAT(0) cubical complexes (like tree space), practical algorithms can also rely on traditional cutting plane techniques.  We also discuss the tractability of recognizing weighted means of finite sets in Hadamard spaces.

Joint work with A. Goodwin, G. Lopez, and A. Nicolae