Circumcenters and Mean Sets in Hadamard Space: Horospherical Subgradient Methods

References

• [1] Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [2] Ardila-Mantilla F (2020) CAT(0) geometry, robots, and society. Notices Amer. Math. Soc. 67(7):977–987.Crossref, Google Scholar
• [3] Arnaudon M, Nielsen F (2013) On approximating the Riemannian 1-center. Comput. Geometry 46(1):93–104.Crossref, Google Scholar
• [4] Bačák M (2014a) Computing medians and means in Hadamard spaces. SIAM J. Optim. 24(3):1542–1566.Crossref, Google Scholar
• [5] Bačák M (2014b) Convex Analysis and Optimization in Hadamard Spaces (De Gruyter, Berlin).Crossref, Google Scholar
• [6] Bǎdoiu M, Clarkson KL (2003) Smaller core-sets for balls. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 801–802.Google Scholar
• [7] Bergmann R, Ferreira OP, Németh SZ, Zhu J (2025) On projection mappings and the gradient projection method on hyperbolic space forms. IMA J. Numer. Anal., ePub ahead of print November 30, https://doi.org/10.1093/imanum/draf097.Crossref, Google Scholar
• [8] Bertsekas D (2011) Incremental proximal methods for large scale convex optimization. Math. Programming Ser. B 129:163–195.Crossref, Google Scholar
• [9] Billera L, Holmes S, Vogtmann K (2001) Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4):733–767.Crossref, Google Scholar
• [10] Borisenko AA, Miquel V (1999) Total curvatures of convex hypersurfaces in hyperbolic space. Illinois J. Math. 43(1):61–78.Crossref, Google Scholar
• [11] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [12] Bridson M, Haefliger A (1999) Metric Spaces of Non-Positive Curvature, Grundlehren der mathematischen Wissenschaften, vol. 319 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [13] Burago D, Burago Y, Ivanov S (2001) A Course in Metric Geometry (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [14] Criscitiello C, Boumal N (2023) Curvature and complexity: Better lower bounds for geodesically convex optimization. Neu G, Rosasco L, eds. Proc. 36th Conf. Learn. Theory, vol. 195 (PMLR, New York), 2969–3013.Google Scholar
• [15] Criscitiello C, Kim J (2025) Horospherically convex optimization on Hadamard manifolds, part I: Analysis and algorithms. Preprint, submitted May 22, https://arxiv.org/abs/2505.16970.Google Scholar
• [16] de C Bento G, Neto JC, Melo IDL (2023) Fenchel conjugate via Busemann function on Hadamard manifolds. Appl. Math. Optim. 88(83).Google Scholar
• [17] Fan X, Yang CH, Vemuri BC (2023) Horospherical decision boundaries for large margin classification in hyperbolic space. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. NIPS’23: Proc. 37th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 11194–11204.Google Scholar
• [18] Ferreira OP, Oliveira PR (1998) Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97:93–104.Crossref, Google Scholar
• [19] Gallego E, Solanes G, Teufel E (2013) Linear combinations of hypersurfaces in hyperbolic space. Monatshefte Für Mathematik 169:329–354.Crossref, Google Scholar
• [20] Goodwin A, Lewis AS, López-Acedo G, Nicolae A (2025a) Convex optimization on CAT(0) cubical complexes. Adv. Appl. Math. 165:102849.Crossref, Google Scholar
• [21] Goodwin A, Lewis AS, López-Acedo G, Nicolae A (2025b) Recognizing weighted means in geodesic spaces. Foundations Comput. Math., ePub ahead of print September 26, https://doi.org/10.1007/s10208-025-09733-7.Crossref, Google Scholar
• [22] Goodwin A, Lewis AS, López-Acedo G, Nicolae A (2026) Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces. Math. Programming Ser. A, ePub ahead of print March 4, https://doi.org/10.1007/s10107-026-02334-4.Crossref, Google Scholar
• [23] Hayashi K (2021) A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes. Discrete Comput. Geometry 65:636–654.Crossref, Google Scholar
• [24] Hirai H (2023) Convex analysis on Hadamard spaces and scaling problem. Foundations Comput. Math. 24:1979–2016.Crossref, Google Scholar
• [25] Huckemann S, Mattingly JC, Miller E, Nolen J (2015) Sticky central limit theorems at isolated hyperbolic planar singularities. Electronic J. Probab. 20(78):1–34.Google Scholar
• [26] Kapovich M, Leeb B, Millson JJ (2009) Convex functions on symmetric spaces, side lengths of polygons and the stability inequalities for weighted configurations at infinity. J. Differential Geometry 81(2):297–354.Crossref, Google Scholar
• [27] Kiwiel K (2001) Convergence and efficiency of subgradient methods for quasiconvex minimization. Math. Programming 90:1–25.Crossref, Google Scholar
• [28] Krivošija A, Munteanu A (2019) Probabilistic smallest enclosing ball in high dimensions via subgradient sampling. 35th Internat. Sympos. Comput. Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 129 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 47:1–47:14.Google Scholar
• [29] Lewis AS, López-Acedo G, Nicolae A (2024) Horoballs and the subgradient method. Preprint, submitted April 2, https://arxiv.org/abs/2403.15749.Google Scholar
• [30] Li H, Wan Y, Xu B (2024) The discrete horospherical p-Minkowski problem in hyperbolic space. Adv. Math. 453:1–31.Crossref, Google Scholar
• [31] Miller E (2015) Fruit flies and moduli: Interactions between biology and mathematics. Notices Amer. Math. Soc. 62(10):1178–1184.Crossref, Google Scholar
• [32] Miller E, Owen M, Provan JS (2015) Polyhedral computational geometry for averaging metric phylogenetic trees. Adv. Appl. Math. 68:51–91.Crossref, Google Scholar
• [33] Nesterov Y (2004) Introductory Lectures on Convex Optimization (Kluwer Academic, Dordrecht, Netherlands).Crossref, Google Scholar
• [34] Ohta S, Palfia M (2015) Discrete-time gradient flows and law of large numbers in Alexandrov spaces. Calculus Variations Partial Differential Equations 54:1591–1610.Crossref, Google Scholar
• [35] Owen M, Provan JS (2011) A fast algorithm for computing geodesic distances in tree space. IEEE/ACM Trans. Comput. Biol. Bioinformatics 8(1):2–13.Crossref, Google Scholar
• [36] Santaló A, Yañez I (1972) Averages for polygons formed by random lines in Euclidean and hyperbolic planes. J. Appl. Probab. 9(1):140–157.Crossref, Google Scholar
• [37] Shor NZ (1962) Application of the method of gradient descent to the solution of the network transportation problem. Materials of the Scientific Seminar on Theoretical and Applied Questions of Cybernetics and Operations Research (Ukrainian Academy of Science, Kiev, Ukraine), 9–17. [In Russian.]Google Scholar
• [38] Sylvester JJ (1857) A question in the geometry of situation. Quart. J. Math. 1:79.Google Scholar
• [39] Tumpach AB, Larotonda G (2024) Totally geodesic submanifolds in the manifold SPD of symmetric positive-definite real matrices. Inform. Geometry 7:913–942.Crossref, Google Scholar
• [40] Tyler DE (1987) A distribution-free M-estimator of multivariate scatter. Ann. Statist. 15(1):234–251.Crossref, Google Scholar
• [41] Udriste C (1994) Convex Functions and Optimization Methods on Riemannian Manifolds (Kluwer Academic, Dordrecht, Netherlands).Crossref, Google Scholar
• [42] 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. Google Scholar