@inproceedings{318698f892014320bb0e1b7b168626b7,
title = "Highly Scalable and Provably Accurate Classification in Poincar{\'e} Balls",
abstract = "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 hyperbolic 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, 1 Fashion-MNIST and mini-ImageNet. ",
keywords = "Hyperbolic, Perceptron, Support Vector Machine",
author = "Eli Chien and Chao Pan and Puoya Tabaghi and Olgica Milenkovic",
note = "Funding Information: ACKNOWLEDGMENT The work was supported in part by the NSF grant 1956384. Publisher Copyright: {\textcopyright} 2021 IEEE.; 21st IEEE International Conference on Data Mining, ICDM 2021 ; Conference date: 07-12-2021 Through 10-12-2021",
year = "2021",
doi = "10.1109/ICDM51629.2021.00016",
language = "English (US)",
series = "Proceedings - IEEE International Conference on Data Mining, ICDM",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "61--70",
editor = "James Bailey and Pauli Miettinen and Koh, {Yun Sing} and Dacheng Tao and Xindong Wu",
booktitle = "Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021",
address = "United States",
}