Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space

DOI10.48550/ARXIV.2610.26815MaRDI QIDQ7400267arXivFDO

Authors Christopher Criscitiello

Publication date 19 October 2026

Published in arXiv

Tldr We prove dimension-independent first-order query complexity lower bound for minimizing Lipschitz geodesically convex functions on hyperbolic space matching known upper bound for the Riemannian subgradient method.

Full work available at URL https://doi.org/10.48550/ARXIV.2610.26815

arXiv classification

math.DGmath.NAmath.OC

Cites work

• A Riemannian corollary of Helly's theorem
• Angular Gaussian and Cauchy estimation
• Conformal and holomorphic barycenters in hyperbolic balls
• Convex analysis and optimization in Hadamard spaces
• Convex analysis on Hadamard spaces and scaling problems
• Convex functions on symmetric spaces, side lengths of polygons and the stability inequalities for weighted configurations at infinity
• Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes
• First-order Methods for Geodesically Convex Optimization
• Geodesic Convexity and Covariance Estimation
• Geodesically Convex Optimization in Hyperbolic Space: Matching Lower Bounds
• Geometrical and statistical properties of M-estimates of scatter on Grassmann manifolds
• Horospherically Convex Optimization on Hadamard Manifolds Part I: Analysis and Algorithms
• Inf-convolution and regularization of convex functions on Riemannian manifolds of nonpositive curvature
• Invariant theory and scaling algorithms for maximum likelihood estimation
• Lower bounds for finding stationary points I
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity
• Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles
• On Geodesically Convex Formulations for the Brascamp-Lieb Constant
• On lower complexity bounds for large-scale smooth convex optimization
• Positive definite matrices
• Riemannian center of mass and mollifier smoothing
• Rigorous Guarantees for Tyler's M-estimator via quantum expansion
• Structured robust covariance estimation
• Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes

This page was built for publication: Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7400267)