2018/04/28 by Alexander Rusciano, Rusciano, Alexander
Engineering · Mathematics · #52A01 #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Inequalities and Applications #Metric Geometry (math.MG) #Point processes and geometric inequalities #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1804.10738
openalex publication_date 2018/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 gradient oracle complexity of convex optimization is polynomial in the parameters defining the problem.