Circumcenters and Mean Sets in Hadamard Space: Horospherical Subgradient Methods

• 成果类型: Article; Early Access
• 署名作者: Goodwin, Ariel; Lewis, Adrian S.; Lopez-Acedo, Genaro; Nicolae, Adriana
• 署名单位: Cornell University; Cornell University; University of Sevilla; Babes Bolyai University from Cluj
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2025.1025
• 发表日期: 2026-07-13
• 关键词: convex; subgradient method; horoball; Hadamard space; complexity; minimal enclosing ball; CAT(0) cubical complex; weighted Frechet mean; hypersurfaces; algorithm; polygons; geometry

摘要

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 Frechet means and computing minimal enclosing balls.