Circumcenters and Mean Sets in Hadamard Space: Horospherical Subgradient Methods

The classical Euclidean subgradient algorithm extends, via tangent constructions and exponential maps, to geodesically convex optimization on manifolds. General complexity analysis for manifolds with an upper curvature bound of zero, as developed by Zhang and Sra in 2016 [Zhang H, Sra S (2016) First-order methods for geodesically convex optimization. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Conf. Learn. Theory, vol. 49 (PMLR, New York), 1617–1638] depends unavoidably on an additional lower curvature bound. We present a fresh approach to subgradient-type methods, suitable for objectives with “horospherically convex” level sets. Our method avoids both tangential constructions in its description and lower curvature bounds in its complexity analysis. Furthermore, it applies beyond manifolds to general geodesic metric spaces with curvature nonpositive but possibly unbounded below. As applications in such spaces, which include CAT(0) cubical complexes such as the Billera–Holmes–Vogtmann space of phylogenetic trees, we consider previously inaccessible problems such as recognizing weighted Fréchet means and computing minimal enclosing balls.

Funding: A. Goodwin was supported by the NSERC Postgraduate Fellowship [Grant PGSD-587671-2024]. A. S. Lewis was supported in part by the National Science Foundation [Grant DMS-2405685]. G. López-Acedo was supported in part by Dirección General de Enseñanza Superior e Investigación Científica (DGES) [Grants PID2023-148294NB-I00, PID-2024-156594NB, and CEX2024-00151-M]. A. Nicolae was supported in part by the Ministry of Research, Innovation and Digitization (CNCS/CCCDI – UEFISCDI) [Grant PN-III-P1-1.1-TE-2019-1306] within PNCDI III.