Hyperbolic SVM vs. Euclidean SVM: Comparing Optimization Challenges

Table of Links

Abstract and 1. Introduction

1. Related Works

2. 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

3. Experiments

   4.1 Synthetic Dataset

   4.2 Real Dataset

4. Discussions, Acknowledgements, and References

   \

A. Proofs

B. Solution Extraction in Relaxed Formulation

C. On Moment Sum-of-Squares Relaxation Hierarchy

D. Platt Scaling [31]

E. Detailed Experimental Results

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.

\

:::info 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).

:::

:::info This paper is available on arxiv under CC by-SA 4.0 Deed (Attribution-Sharealike 4.0 International) license.

:::

\