# Highly Scalable and Provably Accurate Classification in Poincare Balls

arXiv: https://arxiv.org/abs/2109.03781 · HTML: https://mlsanity.com/paper/2109.03781/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 8 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Meta-Learning with Differentiable Convex Optimization](https://mlsanity.com/paper/1904.03758/) (2019)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Hyperbolic Image Embeddings](https://mlsanity.com/paper/1904.02239/) (2019)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Poincar'e GloVe: Hyperbolic Word Embeddings](https://mlsanity.com/paper/1810.06546/) (2018)
- [Continuous Hierarchical Representations with Poincar'e Variational Auto-Encoders](https://mlsanity.com/paper/1901.06033/) (2019)
- [Mixed-curvature Variational Autoencoders](https://mlsanity.com/paper/1911.08411/) (2019)
- [Large-Margin Classification in Hyperbolic Space](https://mlsanity.com/paper/1806.00437/) (2018)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Robust Large-Margin Learning in Hyperbolic Space](https://mlsanity.com/paper/2004.05465/) (2020)
- [Network Geometry Inference using Common Neighbors](https://mlsanity.com/paper/1502.05578/) (2015)

## Built on by (most cited first, 8 of 8)

- [The Numerical Stability of Hyperbolic Representation Learning](https://mlsanity.com/paper/2211.00181/) (2022)
- [Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space](https://mlsanity.com/paper/2302.06807/) (2023)
- [Hyperbolic Random Forests](https://mlsanity.com/paper/2308.13279/) (2023)
- [Principal Component Analysis in Space Forms](https://mlsanity.com/paper/2301.02750/) (2023)
- [HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering](https://mlsanity.com/paper/2205.09721/) (2022)
- [Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces](https://mlsanity.com/paper/2203.03730/) (2022)
- [Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls](https://mlsanity.com/paper/2308.06895/) (2023)
- [Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space](https://mlsanity.com/paper/2405.17198/) (2024)

## Abstract (arXiv)

Many high-dimensional and large-volume data sets of practical relevance have hierarchical structures induced by trees, graphs or time series. Such data sets are hard to process in Euclidean spaces and one often seeks low-dimensional embeddings in other space forms to perform required learning tasks. For hierarchical data, the space of choice is a hyperbolic space since it guarantees low-distortion embeddings for tree-like structures. Unfortunately, the geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. Here, for the first time, we establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. The gist of our approach is to focus on Poincar'e ball models and formulate the classification problems using tangent space formalisms. Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. All algorithms provably converge and are highly scalable as they have complexities comparable to those of their Euclidean counterparts. Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet.