Abstract

We introduce a notion of halfspace for Hadamard manifolds that is natural in the context of convex optimization. For this notion of halfspace, we generalize a classic result of Grünbaum, which itself is a corollary of Helly's theorem. Namely, given a probability distribution on the manifold, there is a point for which all halfspaces based at this point have at least 1/(n+1) of the mass. As an application, the subgradient oracle complexity of convex optimization is polynomial in the size of the parameters defining the problem.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Helly's theorem
  • geodesic convexity
  • convex optimization

Mathematics Subject Classification

52A01

References

  1. Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, A. Wigderson: Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing, STOC 50 (2018) 172–181.https://doi.org/10.1145/3188745.3188942Google Scholar
  2. W. Ballmann: Lectures on Spaces of Nonpositive Curvature, Springer, Berlin (1995).https://doi.org/10.1007/978-3-0348-9240-7Google Scholar
  3. I. Benjamini, R. Eldan: Convex hulls in hyperbolic space, Geometriae Dedicata 160(1) (2012) 365–371.https://doi.org/10.1007/s10711-011-9687-8Google Scholar
  4. J. Bennett, A. Carbery, M. Christ, T. Tao: The Brascamp-Lieb inequalities: finiteness, structure and extremals, Geom. Funct. Analysis 17 (2008) 1343–1415.https://doi.org/10.1007/s00039-007-0619-6Google Scholar
  5. J. Cheeger, D. G. Ebin: Comparison Theorems in Riemannian Geometry, AMS Chelsea Publishing, Providence (2008).https://doi.org/10.1090/chel/365Google Scholar
  6. D. Cordero-Erausquin, R. J. McCann, M. Schmuckenschläger: A Riemannian interpolation inequality à la Borell, Brascamp and Lieb, Inventiones Mathematicae 146 (2001) 219–257.https://doi.org/10.1007/s002220100160Google Scholar
  7. B. Grünbaum: Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific J. Math. 10(4) (1960) 1257–1261.https://doi.org/10.2140/pjm.1960.10.1257Google Scholar
  8. S. Ivanov: On Helly’s theorem in geodesic spaces, Electronic Res. Announcements 21 (2014) no. 1935-9179-2014-0-109.https://doi.org/10.3934/era.2014.21.109Google Scholar
  9. Y. Ledyaev, J. S. Treiman, Q. J. Zhu: Helly’s intersection theorem on manifolds of nonpositive curvature, J. Convex Analysis 13(3-4) (2006) 785–798.https://doi.org/10.68381/jca13059Google Scholar
  10. J. Lee: Riemannian Manifolds: An Introduction to Curvature, Springer, Berlin (1997).https://doi.org/10.1007/b98852Google Scholar
  11. P. Petersen: Riemannian Geometry, Springer, New York (2006).Google Scholar
  12. S. Sra, R. Hosseini: Geometric optimisation on positive definite matrices with application to elliptically contoured distributions, in: Proc. of the 26th International Conference on Neural Information Processing Systems. Volume 2, NIPS’13, Lake Tahoe, Curran Associates (2013) 2562–2570.Google Scholar
  13. C. Udriste: Convex Functions and Optimization Methods on Riemannian Manifolds, Kluwer Academic Publishers, Dordrecht (1994).https://doi.org/10.1007/978-94-015-8390-9Google Scholar
  14. H. Zhang, S. J. Reddi, S. Sra: Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds, in: Advances in Neural Information Processing Systems 29, Curran Associates (2016) 4592–4600.Google Scholar
  15. H. Zhang, S. Sra: First-order methods for geodesically convex optimization, in: Proceedings of the 29th Conference on Learning Theory, PMLR (2016) 1617–1638.Google Scholar

Suggested citation

A. Rusciano. “A Riemannian Corollary of Helly's Theorem.” Journal of Convex Analysis 27 (2020), No. 4, 1261–1275. https://doi.org/10.68381/jca27067

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2020. Rights now held by Banach Press LLC.