Title: Incremental minimization in spaces of nonpositive curvature

Abstract: Subgradient methods for geodesically convex functions on Hadamard manifolds have gained interest in recent years, but fall short in two respects: their
complexity relies unavoidably on a lower curvature bound for the space, and they do not generalize well to metric spaces in the absence of local linearity. Complete geodesic metric spaces of nonpositive curvature, called Hadamard spaces, prove useful in modelling many applications and have a rich geometric structure enabling theoretical and computational aspects of convex optimization. It has recently been shown that a restricted class of functions on Hadamard spaces can be effectively minimized using an iteration resembling a subgradient method, with the same complexity result as the classical Euclidean subgradient method. In this work we propose a related class of functions which we call Busemann convex, admitting a notion of subgradient that is attuned to the geometry of the space. Many functions defined in terms of basic metric quantities are Busemann convex, and their subgradients are readily computed in terms of geodesics. We address the minimization of sums of Busemann convex functions with an incremental subgradient-style method and associated complexity result. To illustrate the algorithm applied to a weighted sum of distance functions, we numerically compute medians of trees in the BHV phylogenetic tree space.

This is joint work with Adrian Lewis, Genaro López-Acedo, and Adriana Nicolae.