Classifiers in High Dimensional Hilbert Metrics
Aditya Acharya, Auguste H. Gezalyan, David M. Mount · 2026
Read Classifiers in High Dimensional Hilbert Metrics by Aditya Acharya, Auguste H. Gezalyan, David M. Mount (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13410.txt.
Introduction
Aditya Acharya, Auguste Gezalyan, and David Mount classify points in a high dim space bent by the Hilbert metric. That metric grows the Cayley-Klein hyperbolic span to any convex body. It has wide use in learning and convex shape work. Classify is a core task, to split points by kind in such a bent space.
The team works in the polygonal form of the metric, where the body is a polygon like form in many dims. They give rules to classify points there with care for cost as dims grow. Bent spaces fit data whose ranks bend, so sound rules there aid real tasks. The work links pure shape to a stock learning act.
Catalog record
| CREATOR | Aditya Acharya, Auguste H. Gezalyan, David M. Mount |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-13410
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Classifiers in High Dimensional Hilbert Metrics Aditya Acharya, Auguste H. Gezalyan, David M. Mount Abstract Classifying points in high dimensional spaces is a fundamental geometric problem in machine learning. In this paper, we address classifying points in the d d -dimensional Hilbert polygonal metric. The Hilbert metric is a generalization of the Cayley-Klein hyperbolic distance to arbitrary convex bodies and has a diverse range of applications in machine learning and convex geometry. We first present an efficient LP-based algorithm in the metric for the large-margin SVM problem. Our algorithm runs in time polynomial to the number of points, bounding facets, and dimension. This is a significant improvement on previous works, which either provide no theoretical guarantees on running time, or suffer from exponential runtime. We also consider the closely related Funk metric. We also present efficient algorithms for the soft-margin SVM problem and for nearest neighbor-based classification in the Hilbert metric. Department of Computer Science, University of Maryland, College Park, USA and https://www.cs.umd.edu/~acharya/ [email protected]://orcid.org/0000-0002-0359-1913 Department of Computer Science, University of Maryland, College Park, USA and ~ [email protected]://orcid.org/0000-0002-5704-312X Department of Computer Science, University of Maryland, College Park, USA and https://www.cs.umd.edu/~mount/ [email protected]://orcid.org/0000-0002-3290-8932 ccs Theory of computation Computational geometry keywords Support vector machines, Hilbert geometry, classification, machine learning † † runningtitle: Classifiers in High Dimensional Hilbert Metrics † † runningauthor: A. Acharya, A. H. Gezalyan, and D. M. Mount † † copyright: Aditya Acharya, Auguste H. Gezalyan, and David M. Mount 1 Introduction In machine learning, binary classification is a supervised learning task where an algorithm learns to map input data (features points) to one of two mutually exclusive classes or labels, often denoted as positive and negative . The primary objective is to train a model that can accurately predict which of the two predefined classes a new, unseen data point belongs to. Binary classification is one of the most fundamental geometric problems in machine learning [ 9 , 29 , 28 , 6 ] as it is related to a wide range of empirical decision problems. Support vector machines (SVMs) were introduced by Vapnik and Chervonenkis [ 31 ] as a type of binary classification algorithm [ 8 ] . We are given two sets of training points P^{+} and P^{-} , representing feature vectors in \mathbb{R}^{d} , that are sampled from two distinct spatial distributions. SVM solves this classification problem by computing a hyperplane that separates the two training sets, such that the minimum distance from each point set to the separating hyperplane, called the margin , is as large as possible. SVMs are widely used in a diverse set of fields such as computer vision [ 30 , 19 ] , natural language processing [ 11 , 15 ] , and computational biology [ 13 , 3 ] . They have been well studied in Euclidean and hyperbolic geometry [ 7 ] , but classification in other non-Euclidean geometries is less well studied. In this paper, we study this problem from the perspective of the Hilbert geometry and the closely related Funk geometry. The Hilbert metric (which will be defined in Section 2 ) is a generalization of the Cayley-Klein model of hyperbolic geometry to arbitrary convex sets. It has several desirable properties, such as having straight line geodesics and being invariant under projective transformations [ 26 ] . The Hilbert metric has a diverse array of applications including: quantum information theory [ 27 ] , real analysis [ 5 ] , and machine learning [ 25 , 24 , 17 ] . Note that the hyperbolic metric (under the Beltrami-Klein model) is a special case of the Hilbert metric when the defining convex body is a Euclidean ball. The Hilbert and Funk geometries are applicable whenever the domain of interest is a convex body and distances are sensitive to the proximity to the boundary. As an example, consider objects that are discrete probability distributions over a domain of size m . Each point in this space is a vector (p_{1},\ldots,p_{m}) , where 0\leq p_{i}\leq 1 and \sum_{i=1}^{m}p_{i}=1 . These constraints imply that the points lie within a convex domain, specifically the (m-1) -dimensional probability simplex. Euclidean distances are not well suited for this context, because they are not sensitive to variations in probabilities that are very close to the critical values of 0 and 1 as compared with those that are far from these extremes. In contrast, the Hilbert distance is very sensitive as points approach the boundary. Nielsen and Sun provided empirical evidence that the Hilbert metric is competitive with other widely-used distance functions for clustering in the probability simplex [ 24 ] . Other applications of Hilbert and related metrics include the analysis of networks through hyperbolic geometry [ 20 ] , the analysis of positive definite matrices in deep learning [ 14 , 21 ] , and lattice-based cryptosystems [ 2 ] . 1.1 Related Work In the Euclidean metric, SVMs are typically solved by formulating them as a convex optimization problem [ 4 ] . The authors of [ 7 ] were among the first to consider SVMs in hyperbolic geometry. They demonstrated that, in practice, their approach significantly outperforms Euclidean classifiers on various benchmarks by respecting the intrinsic geometry of the data. However, their method involved solving a non-convex optimization problem, unlike the convex formulation of Euclidean SVMs. Hence, without careful initialization, it neither guarantees a global optimum nor a worst-case polynomial running time. Recently, the authors of [ 1 ] presented an algorithm for the same polytopal SVM problem that we consider here. They showed that SVM could be modeled as an LP-type problem. Their algorithm’s running time is linear in the number of points but grows polynomially in the total complexity of the polytope defining the metric. Unfortunately, the total complexity of this polytope generally grows exponentially in the dimension of the space. As such, their method remains unsuitable for high dimensions, where most applications in machine learning lie. In contrast, in this work, our running times are polynomial in dimension. 1.2 Our Contributions In this paper, we explore an alternative viewpoint of Hilbert geometry to develop an efficient algorithm for the Hilbert SVM problem. The main feature of our approach is that the running time increases only polynomially with the dimension of the space. Further, our algorithms involve reductions to linear programming, for which efficient and practical software solutions exist. Because of our reliance on numerical solutions to linear programming, we need to assume that the number of bits needed to represent our inputs is bounded, and our output is computed to within a given user-supplied approximation error. The following theorem formalizes our main result. Theorem 1 . Consider a polytope \Omega in \mathbb{R}^{d} defined by m hyperplanes, and two linearly separable point sets P^{+} and P^{-} of total size n contained within \Omega ’s interior. Assume further that all of the defining coordinates and coefficients are representable as B -bit rational numbers. Then there exists an algorithm running in time O(\text{poly}\,(n,m,d,B,\log(1/\varepsilon)) that computes a separating hyperplane whose margin in the Hilbert metric defined by \Omega is within an additive error \varepsilon of the optimum. The notable feature of our approach is the polynomial dependence on the dimension of the