# Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 7 Mar 2022.

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

- [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)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [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)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [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)
- [Linear Classifiers in Product Space Forms](https://mlsanity.com/paper/2102.10204/) (2021)
- [Network Geometry Inference using Common Neighbors](https://mlsanity.com/paper/1502.05578/) (2015)
- [Highly Scalable and Provably Accurate Classification in Poincare Balls](https://mlsanity.com/paper/2109.03781/) (2021)

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

- [Hyperbolic Random Forests](https://mlsanity.com/paper/2308.13279/) (2023)
- [Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls](https://mlsanity.com/paper/2308.06895/) (2023)

## Abstract (arXiv)

Many high-dimensional practical data sets have hierarchical structures induced by 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 the required learning tasks. For hierarchical data, the space of choice is a hyperbolic space because it guarantees low-distortion embeddings for tree-like structures. The geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. We propose 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 perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. Furthermore, we adapt our approach to accommodate second-order perceptrons, where data is preprocessed based on second-order information (correlation) to accelerate convergence, and strategic perceptrons, where potentially manipulated data arrives in an online manner and decisions are made sequentially. The excellent performance of the Poincar'e second-order and strategic perceptrons shows that the proposed framework can be extended to general machine learning problems in hyperbolic spaces. Our experimental results, pertaining to synthetic, single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet, establish that all algorithms provably converge and have complexity comparable to those of their Euclidean counterparts. Accompanying codes can be found at: https://github.com/thupchnsky/PoincareLinearClassification.