Table of Links Abstract and 1. Introduction Abstract and 1. Introduction Related Works


Convex Relaxation Techniques for Hyperbolic SVMs
3.1 Preliminaries
3.2 Original Formulation of the HSVM
3.3 Semidefinite Formulation
3.4 Moment-Sum-of-Squares Relaxation


Experiments
4.1 Synthetic Dataset
4.2 Real Dataset


Discussions, Acknowledgements, and References Related Works Related Works Related Works Convex Relaxation Techniques for Hyperbolic SVMs
3.1 Preliminaries
3.2 Original Formulation of the HSVM
3.3 Semidefinite Formulation
3.4 Moment-Sum-of-Squares Relaxation Convex Relaxation Techniques for Hyperbolic SVMs 3.1 Preliminaries 3.1 Preliminaries 3.2 Original Formulation of the HSVM 3.2 Original Formulation of the HSVM 3.3 Semidefinite Formulation 3.3 Semidefinite Formulation 3.4 Moment-Sum-of-Squares Relaxation 3.4 Moment-Sum-of-Squares Relaxation Experiments
4.1 Synthetic Dataset
4.2 Real Dataset Experiments Experiments 4.1 Synthetic Dataset 4.1 Synthetic Dataset 4.2 Real Dataset 4.2 Real Dataset Discussions, Acknowledgements, and References Discussions, Acknowledgements, and References Discussions, Acknowledgements, and References A. Proofs A. Proofs B. Solution Extraction in Relaxed Formulation B. Solution Extraction in Relaxed Formulation C. On Moment Sum-of-Squares Relaxation Hierarchy C. On Moment Sum-of-Squares Relaxation Hierarchy D. Platt Scaling [31] D. Platt Scaling [31] E. Detailed Experimental Results E. Detailed Experimental Results F. Robust Hyperbolic Support Vector Machine F. Robust Hyperbolic Support Vector Machine 2 Related Works Support Vector Machine (SVM) is a classical statistical learning algorithm operating on Euclidean features [10]. This convex quadratic optimization problem aims to find a linear separator that classifies samples of different labels and has the largest margin to data samples. The problem can be efficiently solved through coordinate descent or Lagrangian dual with sequential minimal optimization (SMO) [11] in the kernelized regime. Mature open source implementations exist such as LIBLINEAR [12] for the former and LIBSVM [13] for the latter. Less is known when moving to statistical learning on non-Euclidean spaces, such as hyperbolic spaces. The popular practice is to directly apply neural networks in both obtaining the hyperbolic embeddings and perform inferences, such as classification, on these embeddings [2, 3, 14–20]. Recently, rising attention has been paid on transferring standard Euclidean statistical learning techniques, such as SVMs, to hyperbolic embeddings for both benchmarking neural net performances and developing better understanding of inherent data structures [4–7]. Learning a large-margin solution on hyperbolic space, however, involves a non-convex constrained optimization problem. Cho et al. [4] propose and solve the hyperbolic support vector machine problem using projected gradient descent; Weber et al. [7] add adversarial training to gradient descent for better generalizability; Chien et al. [5] propose applying Euclidean SVM to features projected to the tangent space of a heuristically-searched point to bypass PGD; Mishne et al. [6] reparametrize parameters and features back to Euclidean space to make the problem nonconvex and perform normal gradient descent. All these attempts are, however, gradient-descent-based algorithms, which are sensitive to initialization, hyperparameters, and class imbalances, and can provably converge to a local minimum without a global optimality guarantee. Another relevant line of research focuses on providing efficient convex relaxations for various optimization problems, such as using semidefinite relaxation [8] for QCQP and moment-sum-ofsquares [21] for polynomial optimization problems. The flagship applications of SDP includes efficiently solving the max-cut problem on graphs [22] and more recently in machine learning tasks such as rotation synchronization in computer vision [23], robotics [24], and medical imaging [25]. Some results on the tightness of SDP have been analyzed on a per-problem basis [26–28]. On the other hand, moment-sum-of-squares relaxation, originated from algebraic geometry [21, 29], has been studied extensively from a theoretical perspective and has been applied for certifying positivity of functions in a bounded domain [30]. Synthesizing the work done in the control and algebraic geometry literature and geometric machine learning works is under-explored. Authors:
(1) Sheng Yang, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (shengyang@g.harvard.edu);
(2) Peihan Liu, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (peihanliu@fas.harvard.edu);
(3) Cengiz Pehlevan, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, Center for Brain Science, Harvard University, Cambridge, MA, and Kempner Institute for the Study of Natural and Artificial Intelligence, Harvard University, Cambridge, MA (cpehlevan@seas.harvard.edu). Authors: Authors: (1) Sheng Yang, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (shengyang@g.harvard.edu); (2) Peihan Liu, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (peihanliu@fas.harvard.edu); (3) Cengiz Pehlevan, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, Center for Brain Science, Harvard University, Cambridge, MA, and Kempner Institute for the Study of Natural and Artificial Intelligence, Harvard University, Cambridge, MA (cpehlevan@seas.harvard.edu). This paper is available on arxiv under CC by-SA 4.0 Deed (Attribution-Sharealike 4.0 International) license. This paper is available on arxiv under CC by-SA 4.0 Deed (Attribution-Sharealike 4.0 International) license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

NEAR Protocol

Hyperbolic SVM vs. Euclidean SVM: Comparing Optimization Challenges

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

Darwin's Hybrid Intelligence to Align AI & Human Goals for Startups & VCs

100+ Free Pluralsight Courses to learn Python, Java, and Spring Boot

100 Days of AI Day 1: From Newsletter to Podcast, Leveraging AI for Audio Transformation

10 Ways AI Has Changed Our Lives

100 Days of AI Day 3: Leveraging AI for Prompt Engineering and Inference

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

Darwin's Hybrid Intelligence to Align AI & Human Goals for Startups & VCs

100+ Free Pluralsight Courses to learn Python, Java, and Spring Boot

100 Days of AI Day 1: From Newsletter to Podcast, Leveraging AI for Audio Transformation

10 Ways AI Has Changed Our Lives

100 Days of AI Day 3: Leveraging AI for Prompt Engineering and Inference

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps