Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space
Authors: Sheng Yang
Peihan Liu
Cengiz Pehlevan
Venue: Accepted by TMLR ()

Abstract: Hyperbolic spaces have increasingly been recognized for their outstanding performance in handling data with inherent hierarchical structures compared to their Euclidean counterparts. However, learning in hyperbolic spaces poses significant challenges. In particular, extending support vector machines to hyperbolic spaces is in general a constrained non-convex optimization problem. Previous and popular attempts to solve hyperbolic SVMs, primarily using projected gradient descent, are generally sensitive to hyperparameters and initializations, often leading to suboptimal solutions. In this work, by first rewriting the problem into a polynomial optimization, we apply semidefinite relaxation and sparse moment-sum-of-squares relaxation to effectively approximate the optima. From extensive empirical experiments, these methods are shown to achieve better classification accuracies than the projected gradient descent approach in most of the synthetic and real two-dimensional hyperbolic embedding dataset under the one-vs-rest multiclass-classification scheme.

Published in Transactions on Machine Learning Research (04/2025)
Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space
Sheng Yang John A. Paulson School of Engineering and Applied Sciences
shengyong@g. www.gig..arrrr.coo eduu
Harvard University
Peihan Liu
Trihankku@ffshharraarer edu
John A. Paulson School Engineering and Applied Sciences
Harvard University
Cengiz Pehlevan
opehlerann@seas.harre
John A. Poulson School of Engineering and Applied Sciences Center for Brain Science
Kempner Institute for the Study of Natural and Artificial Intelligence Harvard University
Reviewed on OpenReview: https: // openreview. net/ forum? id= eIPwJgadfZ
Abstract
Hyperbolic spaces have increasingly been recognized for their outstanding performance in handling data with inherent hierarchical structures compared to their Euclidean counter- parts. However, learning in hyperbolic spaces poscs significant challenges. In particular, ex- lending support vector machines to hyperbolic spaces is in general a constrained non-convex optimization problem. Previous and popular attempts to solve hyperbolic SVMs, primarily using projected gradient descent, are generally sensitive to hyperparameters and initializa- lions, often leading lo suboptimal solutions. In this work, by first rewriting the problem into a polynomial optimization, we apply semidefinite relaxation and sparse moment-sum- of-squares relaxation effectively approximate the optima. From extensive empirical ex- periments, these methods are shown to achieve better classification accuracies than the projected gradient descent approach in most of the synthetic and real two-dimensional hy- perbolic embedding dataset under the one-vs-rest multiclass-classificttion scheme.
1 Introduction
The d-dimensional hyperbolic space Hd is the unique simply-connected Riemannian manifold with constant negative sectional curvature -1. Tts exponential volume growth with respect to radius motivates representa- tion learning of hierarchical data using the hyperbolic space. Representations embedded in the hyperbolic spaces have demonstrated significant improvements over their Euclidean counterparts across a variety of datasets, including images (Khrulkov et al. 2020), natural languages (Nickel Kiela 2017,, and complex tabular data such as singlo-cell sequencing Klimovskaia al. 2020).
On the other hand, learning and optimization hyperbolic spaces typically more involved than that Euclidean spaces. Problems that convex in Euclidean spaces become constrained non-convex problems in hyperbolic spaces. The hyperbolic Support Vector Machine (HSVM), as explored in recent studies Cho et al. (2019); Chien et al. (2021), exemplifies such challenges by presenting as a non-convex constrained pro- gramming problem that has been solved predominantly based on projected gradient descent. Attempts have been made alleviate its non-convex nature through reparamctrization (Mishne et al. (023) or developing hyperbolic perceptron algorithm that converges a separator with finetuning using adversarial samples to approximate the large-margin solution (Weber et al. 2020 To best knowledge, these attempts are

---

Published in Transactions on Machine Learning Research (04/2025)
grounded in the gradient descent dynamics, which is highly sensitive to initialization and hyperparameters and cannot certily optimality.
As efficiently solving for the large-margin solution on hyperbolic spaces to optimality provides performance gain in downstream data analysis, we explore two convex relaxations to the original HSVM problem and examine their empirical tightness through their optimality gaps. Our contributions can be summarized as follows: in Section g we briefly introduce the necessary concepts for large-margin learning in hyperbolic space, transform the original HSVM formulation into quadratically constrained quadratic programming (QCQP) problem, and later apply the standard semidefinite relaxation (SDP) (Shor) 1987) to this QCQP. Empirically, SDP does not yield tight enough solutions, which motivates us to apply the moment-sum-of- squares relaxation (Moment) (Nie) 2023). The problem with the Moment approach is its limited scalability as it empirically requires a long runtime and large computation memory. However, there is a special shaped sparsity structure in the HSVM problem. By exploiting such a sparcity pattern, we successfully reduce the number of decision variables in the original coneen-ssum-o--sqquee but sparse moment--smm-of-qqureee relaxation. In Section | we test the performance of our methods in both simulated and real datasets, We observe small optimality gaps for various tasks (in the order of 10-2 relaxation and obtain better max-margin scparators
relaxation and propose an equivalent
to 10-") by using the sparse noment-sum-oofsqqee in terms of test accuracy in a one-vs-rest 5-fold train-test scheme than projected gradient descent (PGD). SDP relaxation, on the other hand, is not tight, but still yields better solutions than PGD, particularly in the one-vs-one training framework. The section then ends with the limitations of our proposed method and a brief practical guidance of when to use our methods. Lastly, we conclude and point out some future directions in Section 5 Additionally, we propose without testing robust version of HSVM in Appendix F The code to our implmentations is http:://ghhbbbbooom///gggggggg//
2 Related Works
Support Vector Machine (SVM) is a classical statistical learning algorithm operating on Euclidean features Cortes & Vapnik (1995). 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) Platt (1998) in the kernelized regime. Mature open source implementations exist such as LIBLINEAR Fan et al. 2008) for the former and LIBSVM Chang & Lin 2011) for the latter.
Less is known when moving to statistical learning 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 Ganea et al. (2018); Klimovskaia et al. (2020);
Nickel & Kicla/ (2017); Chami et al. (2020 2019); Lensink et al. (2022): Skliar & Weiler (2023): : Shimizu ct al. (2020); Peng et al. (2021). Recently, increasing altention has been paid to 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 Mishne et al. (2023) Weber et al. (020)); Cho et al. (2019): Chien et al. (2021). Learning a large-margin solution on hyperbolic space, however, involves a non-convex constrained optimization problem. Cho et al. (2019) propose and solve
the hyperbolic support vector machine problem using projected gradient descent: Weber et al. (2020) add
adversarial training to gradient descent for better generalizability; Chien et al.
Fuclidean SVM to features projected to the tangent space of a hearistically-seariin (2021) propose applying point to bypass PGD;
Mishne et al. (2023) reparametrize parameters and fcatures back to Euclidean space to make the problem nonconvex and perform normal gradient descent. All these attempts are, however, gradient-descent- based algorithms, which sensitive to initialization, hyperparameters, and class imbalances, and can provably converge to a local minimum without global optimality guarantee.
Another relevant line of research focuses on providing efficient convex relaxations for various optimization problems, such as using semidefinite relaxation (Shor 1987) for QCQP and nomeent-sum--f-squaae man et al. 2012) for polynomial optimization problems. The flagship applications of SDP includes efficiently solving the max-cut problem on graphs Goemans & Williamson (1995) and more recently in machine learn- ing tasks such as rotation synchronization in computer vision (Eriksson al. 2018), robotics (Rosen et al.
(Blekher-
2

---

Published in Transactions on Machine Learning Research (04/2025)
2020,, and medical imaging (Wang & Singer
2013
Some results on the tightness of SDP have been ana-
lyzed on per-problem basis (Bandeira et al. 2017 Brynte et al. 2022 Zhang 2020 On the other hand. moment-sum-of-sqqae
relaxation, originated from algebraic geometry (Blekherman et al. 2012 Lasserre 2001), has been studied extensively from a thcoretical perspective and has been applied for certifying pos- itviity of functions in bounded domain (Henrion Laassrree 2005). Synthesizing the work done in the control and algebraic geometry literature and geometric machine learning works is under-explored.
3 Convex Relaxation Techniques for Hyperbolic SVMs
In this section, we first introduce fundamentals on hyperbolic spaces and the original formulation of the hyperbolic Support Vector Machine (HSVM) due to Cho et al. (2019). Next, we present two relaxations techniques, the semidefinite relaxation and the momeentsuun-of-squarre relaxation, that can be solved ef- ficiently with convergence guarantees. Our discussions center the Torentz manifold the choice of hyperbolic space, since it has been shown in Mishne et al. 2023 that the Lorentz formulation offers greater numerical advantages in optimization.
3.1 Preliminaries
Hyperbolic Space (Lorentz Manifold): define Minkowski product of two vectors x, Rd+1 as x+y=
Toz0 Σi= Rith- A d-dimensional hyperbolic space (Lorentz formulation) submanifold embedded gd+1 defined by,
Hd {ar (ro, x) E TRd+1 x 1, 0).
(1)
Tangent Space: a tangent space to manifold at given point E Hd is the local linear subspace approximation to the manifold, denoted Tg H.H this case the tangent space a Euclidean vector space of dimension d written as
T. (w E Rd+1 w 0}.
(2)
Exponential & Logarithmic Map: the exponential map expx(.) Ta TH - TH is transformation that sends vectors in the tangent space to the manifold. The logarithmic map log (.) 1H + THd is the inverse operation. Formally, given x E Hd, HdH we have
exp, (v) co + sinh([[e/]aea) ||
||>/| v 1/--0-
(3)
Exponential and logarithmic maps serve as bridges between Eu- clidean and hyperbolic spaces, enabling the transfer of notion, such distances and probability distributions, between these spaces. One way is to consider Euclidean fcatures residing within the langent space of the hyperbolic manifold's origin. From this standpoint, distributions on hyperbolic space can be obtained through exPo-
w
Hyperbolic Decision Boundary: straight lines in the hy- perbolic space are intersections between d-dimensional hyper- planes passing through the origin and the manifold Hd. Sup- pose w E Bd+1 is the normal dircction of the plane, then the plane and hyperbolic manifold intersect if and only if wow < O. From this viewpoint, each straight line in the hyperbolic space can be parameterized by w and can be considered a lincar sep- arator for hyperbolic embeddings. Hence, we can define a de- cision function hnd by the Minkowski product of the feature
Figure Straight line (red) on Lorentz manifold H² as the intersection between hyperplane and the manifold, presented similarly in Cho et al. 2019
3

---

Published in Transactions on Machine Learning Research (04/2025)
with the decision plane, as the following,
1, * x = - 0,
hww (z) = -1, otherwise,
(4)
where w' = Wo w1.... wal. A visualization is presented in Figure
Stereographic Projection: visualize H by projecting Lorentz features isometrically to the Poincaré space B". Denote Lorentz features as a = [20 .i,...,. Øz], then its projection is given by ã = T+mp" ... [ E
=
B Rd. Decision boundaries on the Lorentz manifold are mapped ares the Poincaré space. The proof is deferred to Appendix A.2
3.2 Original Formulation of the HSVM
Cho al. (2019) proposed the hyperbolic support vector machine which finds max-margin separator where margin is defined the hyperbolic point to line distance. We demonstrate our results in a binary classification sctting. Extension to multi-class classification is straightforward using Platt-scaling (Platt
ct al. 1999 in the one-vs-rest scheme or majority voting in one-vs-one setting,
Suppose we are given {(zi, y:) æz E Hd, V/s E (1, -1,11) The mard-margin HSVM formulated as,
min 1 = w Gw s.l. v. Gwv > 1, Vi E [n],
(HARD)
(5)
MERa+1 and Gw>0 2
whereas the margin version allows misclassificatiin using
(SOFT)
min WER R0 Gw>0 2
w Gw + C ((((((G)))))
(6)
1=1
where G E R(d+1)x(d+1) is diagonal matrix with diagonal elements d-a,())= but the first being -1), to represent the Minkowski product in Euclidean matrix-vector product manner and is the source of indefiniteness of the problem. In the soft-margin case, the hyperparameter C' > 0 controls the strength of penalizing misclassification. This penalty scales with hyperbolic distances, defined by I(z) = max(0, arcsinh(1) arcsinh(z)).
(i.e. all ones
As C approaches infinity, we recover the hard-margin formulation from the soft-margin one. In the rest of the paper we focus analyzing relaxations to the soft-margin formulation in Equation (6) as these relaxations can be applied to both pyperbolic-lineatty separable unseparable data.
To solve the problem efficiently, we have two observations that lead to two adjustments in our approach. Firstly, although the constraint involving w is initially posited as strict inequality, practical considerations allow for a relaxation. Specifically, when equality is achieved, w" G"" = 0, the separator is not on the manifold and assigns the same label to all data samples. However, with sufficient samples for cach class the training set and an appropriate regularization constant C, the solver unlikely to default to such a trivial may substitute the strict inequality with non-strict one during implementation.
solution. Therefore, Secondly, the penalization function, I, is not polynomial. Although projected gradient descent is able to tackle non-polynomial terms in the loss function, solvers typically only accommodate constraints and objectives expressed as polynomials. We thus take a Taylor expansion of the arcsinh term to the first order so that every term in the formulation is a polynomial. This also helps with constructing our semidefinite and noment-suumoo-sqquee
relaxations later on, which presented in Appendix A.I in detail. The new formulation of the mafgin HSVM outlined in Equation ( then given by,
1 -T Gw + C
min wER4tigER"
2
1=1
s.t. & > 0, Vi E [n]
(7)
(G, TT w & V28,
[n]
T Gw > 0
4

---

Published in Transactions on Machine Learning Research (04/2025)
where for i E [n] are the slack variables. More specifically, given sample (i); if & O, the sample has been classified correctly with a large margin; if & E (0, /2) the sample falls into the right region but with a small hyperbolic margin; and if & > V2 the sample sits in the wrong side of the separator. We defer detailed derivation of Equation
I
Appendix A.1 and its extension curvatures other than -1
in Appendix A.3
3.3 Semidefinite Formulation
Note that Equation 7 is a non-convex ceteratiicallyoonsraainnn quadratic programming (QCQP) problem, The SDP formulation is given by
we can apply a semidefinite relaxation (SDP) (hhr 1987.
(SDP)
min WER(++Dx(-1) WERdiL EER"
Tr(G, W) + C
Σ &
1=1
s.t. & > 0, Vi [n]
(8)
(Gx,)) _ w & v2g, - 1, Vi [n]
Tr W) > 0
w" 7
w W 0
where decision variables are highlighted in bold and that the last constraint stipulates the concatenated matrix being positive semidefinite, which is equivalent to W- www" Σ by Schur's complement lemma. In this SDP relaxation, all constraints and the objective become linear (W, E), which could be easily solved. Note that if additionally we mandate W to be rank 1, then this formulation would be equivalent to Equation 7 otherwise relaxation. Moreover, it is important to note that this SDP does not directly yield decision boundaries. Instead, need to extract w" from the solutions (W, w, obtained from Equation A detailed discussion of the extraction methods is deferred to Appendix B.1
3.4 Moment-Sum-of-SSune Sqquress Relaxation
The SDP relaxation in Equation S may not be tight, particularly when the resulting W has a rank much larger than 1. Indeed, we often find W to be full-rank empirically. In such cases, moment-sun-of- squares relaxation may be beneficial. Specifically, it can certifiably find the global optima, provided that the solution exhibits special structure, known the flat-extension property (Curto & Fialkow 2005 Henrion & Lasserre 2005).
We begin by introducing some necessary notions, with more comprehensive introduction available in Appendix C
We define the relaxation order as x >> and our decision variables as q = 0(w, E Ra+d+1 Our objective, p(q), is a polynomial of degree 2x with input q, where its coefficient is defined such that p(q)= = w Gw+C G
- 1-2=1,, S,, thus matching the original objective. Hence, the polynomial p(.) has s(m, 2x) == (mut2a) number of coefficients, where m = n d + 1 is the dimension of decision variables. Additionally, we define 2 (=(m.2x) the Truncated Multi-Sequence (TMS) of degree 2x, and we denote linear functional f associated with this sequence
fz(p) = (fz.p) (z, vec(p)).
(9)
which is the inner product between the coefficients of polynomial p and the vector or real numbers 2. The vector of monomials up to degree x generated by q is denoted as [q].. With all these notions established, we can then define the moment matrix of k-th degree, Ma [z], and localizing matrix of k-th degree for polynomial g, [z], as the followings,
Mx(z] = (J2. (g))
(10)
Lr. [z] (fz. lgl.
(11)
5

---

Published in Transactions on Machine Learning Research (04/2025)
where is the max degree such that 2s deg(g) & 2n. 19]<1972 is matrix of polynomials with size s(m,k) by s(m, k); and all the inner products are applied element-wise above. For example, if n = and d = (i.e. 1 data sample from 2-dimensional hyperbolic space), the degree-2 monomials generated by
q = (Wo, W1, W2, 51) are
2 = [1, wo, wi, w2, E w wi, w2: Si woWi, wow2, woLl, wi w2, w w2L1].
(12)
With all these definitions established, we can present the moment-sum-of squuresss relaxation Nie the HSVM problem, outlined in Equation as
2023
(Moment)
min (vec(p), 2) (em,mm))
s.t. Mn z ビ 0
Ln [2] = O, Vi [n]
(13)
L L (v: w- wot -
Vi [n]
T |=| 2 0
Note that s(4) > O, previously defined, serves as constraints in the original formulation. Additionally, when forming the moment matrix, the degree of generated monomials is = --1 1, since all constraints in Equation 7 has maximum degree 1. Consequently, Equation (13) is a convex programming and can be implemented as a standard SDP problem using mainstream solvers. We further emphasize that by progressively increasing the relaxation order K, we can find increasingly better solutions theoretically, suggested by Lasserre 20188).
((1)
relaxation does not scale with the data size due to the combinatorial factors in the dimension of truncated multi-eeeeence 2, leading to prohibitively slow runtimes and excessive memory consumption. To address this issuc, we exploit the sparsity pattern inherent in this problom: many generated monomial terms do not appear in the objective or constraints. For instance, there is no cross-terms among the slack variables, such as &LE for j E [n]. Specifically, in this problem, we observe star-shaped sparsity structure, ilustrated in Figure 2 We observe that, by defining sparsity groups as (+)) = &w, two nice structural properties can be found: first, the objective function involves all the sparsity groups, {q() Jizi and can be decomposed as sum of polynomials p(o) which involves only qd) and thus has a smaller number of coefficients s(m', 2n), where m' = + 2. Second, each constraint is exclusively associated with single group (()) for a specific i. For the remaining constraint, w Gw, we could assign it group i without loss of generality. Hence, by leveraging this sparsity property, we can reformulate the its sparse version,
However, moment--sun-----qque
t1
g(0)
(
w
E
q
Figure 2: Star-shaped Sparsity pattern in Equa- tion [3 with 44
relaxation equivalently into
n
(Sparse-Moment)
min (0) (m
Σ
(v) 20)
viein]
1=1
s.l. Mn (1) 2 0, Vi E [n]
LR,g, Lx [0] 0, vie [n|
(14)
L " (0) 2 0, [
w+ -+v -
Lu.wToul (2 (2) - 0 (MA(2(0)a (Mx( Vi (k
where is an index set the moment matrix to entries generated by w along, ensuring that each moment matrix with overlapping regions share the same values as required. We refer the last constraint as the sparse-
binding constraint. The nice thing about Equation 14 is that is equivalent to Equation (13 and has a fewer number of decision variables.

---

Published in Transactions on Machine Learning Research (04/2025)
Unfortunately, solution empirically does not satisfy the flat-extension property and cannot not cer- tily global optimality. Nonetheless, in practice, it achieves significant performance improvements in selected datasets over both projected gradient descent and the SDP-relaxed formulation. Similarly, this formula- tion does not directly yield decision boundaries and we defer discussions on the extraction mothods to Appendix B.2
4 Experiments
We validate the performances of semidefinite relaxation (SDP) and sparse moneent-sum--f-squaree relaxations (Moment) by comparing various metrics with that of projected gradient descent (PGD) combination of synthetic and real datasets. The PGD implementation follows from adapting the MATLAB code in Cho et al. (2019), with learning rate 0.001 and 2000 epochs for synthetic and 4000 epochs for real dalaset and warm-starrtd with a Euclidean SVM solution.
Datasets. For synthetic datasets, construct Gaussian and tree embedding dalasets following Cho el al. (219 Mishne et al. (2023); Weber et al. (2020). Regarding real datasets, our experiments include two
machine learning benchmark datascts, CIFAR-10 Krizhevsky et al. (2009) and Fashion-MNIST Xiao et al.
2017 with their hyperbolic embeddings obtained through standard hyperbolic embedding procedure (Chien et al. 2021 Khrulkov et al. 2020 Klimovskaia al.] (0200) to assess image classífication performance. Ad- ditionally, we incorporate three graph embedding datasets, such as football, karate, and polbooks obtained from Chicn et al. (2021), to evaluate the effectiveness of our methods on graph-structured data. We also ex- plore cell embedding datasets, including Paul Myeloid Progenilors developmental datasel. (Paul et al. 2015
Olsson Single-Cell RNA sequencing dataset (Olsson et al., 2016), Krumsick Simulated Mycloid Progenitors dataset (otaaee(Krunnsiek Krumsiek et al. 2011). and Moignard blood cell developmental trace dataset from single-cell gene expression (Moignard et al. 2015), where the inherent geometry structures well fit into our methods.
We emphasize that all features are on the Lorentz manifold, but visualized in Poincaré manifold through stereographie projection if the dimension 2.
Evaluation Metrics. The primary metrics for assessing model performance are average training and testing loss, accuracy, and weighted F1 score under a stratified 5-fold train-lest split scheme. Furthermore, assess the tightness of the relaxations, we examine the relative suboptimality gap, defined
f-pp1 1+ 1 + +
(15)
where f* is the unknown optimal objective value, p² is the objective value of the relaxed formulation, and f is the objective associated the max-margin solution recovered from the relaxed model. Clearly p² < f < so if 0, we can certify the exactness of the relaxed model.
Implementations Details, We use MOSEK (ApS) 2022 in Python as our optimization solver without any
intermediate parser, since directly interacting with solvers save substantial runtime parsing the problem. MOSEK uses interior point method to update parameters inside the feasible region without projections. All experiments are run and timed a machine with 8 Intel Broadwell Ice Lake CPUs and 40GB of memory. Results over multiple random seeds have been gathered and reported.
We first present the results on synthetic Gaussian and tree embedding datasets in Section 4.1 followed by results on various real datasets in Section 4.2
4.1 Synthetic Dataset
Synthetic Gaussian. To generate a Gaussian dataset on Hd, we first generate Euclidean features Rd and lift to hyperbolic space through exponential map at the origin, expo, as outlined in Equation B We adjust the number of classes K E (2,3,5) and the variance of the isotropic Gaussian E (0.4, 0.6, 0.8, 1.0).
7

---

Published in Transactions on Machine Learning Research (04/2025)
Three Gaussian embeddings in d 2 are selected and visualized in Figure 3 and performances with C 10 for the three dataset are summarized in Table
In general, we observe a small gain in average test accuracy and weighted Fl score from SDP and Moment relative to PGD. Notably, we observe that Moment often shows more consistent improvements compared SDP, across most of the configurations. In addition, Moment gives smaller optimality gaps if than SDP. This matches our expectation that Moment tighter than the SDP.
Although in some case, for example when K 5, Moment achieves significantly smaller losses compared to both PGD and SDP, it is generally not the case. We emphasize that these losses are not direct measure- ments of the max-margin hyperbolic separators' generalizability; rather, they are combinations of margin maximization and penalization for misclassification that scales with C. Hence, the observation that the per- formance in test accuracy and weighted Fl score is better, even though the loss computed using extracted solutions from SDP and Moment is somctimes higher than that from PGD, might be due the complicated loss landscape. More specifically, the observed increases in loss can be attributed to the intricacies of the landscape rather than the effectiveness of the optimization methods. Based the accuracy and F1 score results, empirically SDP and Moment methods identify solutions that generalize better than those obtained by running gradient descent alone. We provide more detailed analysis on the effect of hyperparameters in Appendix F.2 and runtime in Table Decision boundary for Gaussian is visualized in Figure as an example.
(a) Gaussian with K = 2
(b) Gaussian with K =
(c) Gaussian with K = 5
(d) Tree
(e) Tree 2
(f) Tree 3
Figure 3: Three Synthetic Gaussian (top row) and Three Tree Embeddings (bottom row). All features are in HP but visualized through stereographic projection on B Different colors represent different classes. For tree dataset, the graph connections are also visualized but not used in training. The selected tree embeddings come directly from Mishne et al. (2023).
Synthetic Tree Embedding. As hyperbolic spaces are good for embedding trees, we generate random tree graphs and embed them H following Mishne al. (2023). Specifically, we label nodes as positive if they are children of specified node and negative otherwise. Our models are then evaluated for subtree classification, aiming to identify boundary that includes all the children nodes within the same subtree.
8

---

Published in Transactions on Machine Learning Research (04/2025)
Such task has various practical applications. For example, if the tree represents set of tokens, the decision boundary can highlight semantic regions in the hyperbolic space that correspond to the subtrees of the data graph. We emphasize that a common feature in such subtree classification task is data imbalance, which usually lead to poor gencralizability. Honce, we aim to use this task to assess our methods' performances under this challenging setting. Three embeddings are selected and visualized in Figure 3 and performance is summarized in Table The runtime of the selected trees can be found in Table Decision boundary of tree 2 is visualized in Figure
Similar to the results of synthetic Gaussian datsets, observe better performance from SDP and Moment compared to PGD, and due to data imbalance that gradient-based methods typically struggle with, we have a larger gain in weighted Fl score in this case. In addition, we observe large optimality gaps for SDP but very tight gap for Moment, certifying the optimality of Moment even when maas-imbalance is severe.
Table 1: Performance synthetic Gaussian and tree dataset for C' 10.0: 5-fold test accuracy and weighted Fl score plus and minus 1 standard deviation, and the average relative optimality gap 17 for SDP and Moment.
test acc
test (micro)
data
PGD
SDP
Moment
PGD
SDP
Moment
SDP
Moment
gaussian
84.50% + 7.31%
85.50% = 8.28%
85.50% = 8.28%
0.84 = 0.07
0.85 + 0.08
0.85 +: 0.08
0.0847
0.0834
ganssian 2
85.33% +: 4.88%
84.00% + 5.12%
86.33% + 4.76%
0.86 = 0.05
0.84 + 0.06
0.87 :: 0.05
0,2046
0.0931
gaussian
75.8% + 3.31%
72.80% 3.37%
77.40% = 2.65%
0.75 0.03
0.71 = 0.04
0.77
0.03
0.2204
0.0926
tree
96.11% + 2.95%
100.0% = 0.00%
100.0% = 0.00%
0.94 = 0.04
1.00 = 0.00
1.00
+ 0.00
0.9984
0.0640
tree 2
96.25% +: 0.00%
99.71% + 0.23%
99.91% + 0.05%
0.94 = 0.00
1.00 + 0.00
1.00 +: 0.00
0.3985
0.0205
tree
99.86%
0.16%
0.16% 99.86%
99.93%
0.13%
0.00
0.99
0.00
0.00
0.3321
0.0728
4.2 Real Dataset
Real datasets consist of embedding of various sizes and number of classes in H2, visualized in Figure 4 We first report performances of three models using ose-vs- training scheme, described in Appendix D in Tables 6 for C Ce {0.1, 1.0, 10} respectively, and report aggregated performances, by selecting the one with the highest average test weighted F1 score, in Table _ In general, we observe that Moment achieves the best test accuracy and weighted F1 score, particularly in biological datascts with clear hyperbolic structures, and have smaller optimality gaps compared to SDP relaxation, for nearly all selected dala. However, it is important to note that the optimality gaps of these two methods remain distant from zero, suggesting that these relaxations are not tight enough for these datascts. Nevertheless, both relaxed models significantly outperform projected gradient descent (PGD) by a wide margin. Furthermore, our observations reveal that in the one-vs-rest training scheme, PGD shows considerable sensitivity to the choice of the regularization parameter C from Tables 0 B whereas SDP and Moment are less affected, demonstrating better stability and consistency across different C's.
One critical drawback of semidefinite and sparse moment-summ-o--xquarrs relaxation is that they do not scale efficiently with an increase in data samples, resulting in excessive consumption of time and memory, for example, CIFAR10 and Fashion-MNIST using a one-vs-rest training scheme. The workaround is one-vs- one training scheme, where we train for ((22) number of classifiers among data from each pair of classes and make final prediction docision using majority voting. We summarize the performance in Table D by aggregating results for different C in Tables g to I1 as in the one-vs-rest case. We observe that in one-vs- one training, the improvement in general from the relaxation is not as significant as it in the one-vs-rest scheme, and SDP relaxation now gives the best performance in average test accuracy and test F1, albeit with large optimality gaps. Note that in the one-vs-one scheme, PGD is more consistent across different C's, polentially because each subproblem-binary classifying one class against another-contains less data compared to one-vs-rest, making it easier to identify solutions.
A more detailed analysis on the effect of regularization C' and runtime comparisons are provided in Ap- pendix F.3 and Table 12
9

---

Published in Transactions on Machine Learning Research (04/2025)
football
karate
polbooks
dltrr
bahiio-mmiit
molgnard
p36l
myelidarogentorrs
Figure 4: Real datasets embedded on H² visualized in B Different colors represent different classes. The first three (football, karate, polbooks) are graph embeddings; the latter two (cifar10, fashion mnist) on the top row standard MT. benchmarks; the last 5 dataset are single-cell sequencing data embedded H for cell type discovery and miscellaneous biomedical usages.
Table 2: Real dataset 5-fold test accuracy, F1, and optimality gap with re-rstt training. Best metrics based on weighted Fl reported here aggregating from Tables to
data
Lest acc SDP
Lest fl (micro)
PGD
Moment
PGD
SDP
Moment
SDP
Moment
football
40.87%
4.43%
32.17%
4.43%
37.39%
4.43%
0.29
0.03
0.23
0.0999
karate
50.00%
6.39%
50.00%
6.39%
50.00%
6.39%
0.66 + 0.06
0.06
0.06
0.66 = 0.06
0.9155
0.0818
polbookss
84.76%
1.90%
84.76%
1.90%
84.76%
1.90%
0.79 + 0.02
0.80
0.03
0.80 0.03
0.1711
0.0991
krunsšck
81.78%
2.66%
82.56%
2.01%
86.47%
0.64%
0.79 1 0.03
0.80 0.03
0.84
0.00
0.7519
0.0921
moiguard
63.37%
0.70%
63.68%
1.73%
63.78%
1.57%
0.62 0.01
0.60
0.0325
U.0396
olsson
74.27%
5.15%
79.63%
3.54%
81.20%
3.68%
0.69 + 0.07
0.77 - 0.04
0.79
0.04
0.4118
0.0976
panl
54.85%
1.26%
2.42% 53.72%
2.36% 76.84%
64.71%
0.48 + 0.02
0.47 + 0.03
0.61
+ 0.02
0.4477
0.0861
myeloidprogemitors
69.34%
3.81%
70.12%
3.28%
2.04%
0.06 + 0.05
0.67 0.04
0.75 0.02
0.6503
0.1074
4.3 Limitations
Although our proposed SDP and sparse moment relaxation methods achieve generally better classification performance compared to the PGD baseline the one-vs-rest setting and slightly less so the one-vs-one setting the computational cost is significant due to their longer runtimes, as previously mentioned. One naturally suspects that given equivalent computational resources (including time and memory), PGD might achieve performance comparable to the sparse moment relaxation methods. This scenario becomes especially
Table 3: Real dataset 5-fold test accuracy, F1, and optimality gap with one-vs-one training. Best metrics
based on weighted F1 is reported here aggregating from Tables to
data
test acc SDP
test f1 (micro)
PGD
Moment
PGD
SDP
Moment
SDP
Moment
football
40.00% = 5.07%
42.61% = 5.07%
11.74%
7.06%
0.32 = 0.06
0.35 = 0.06
0.33 0.07
0.6099
0.2805
karate
50.00% 6.39%
500.00%
6.19%
30.00%
6.39%
0.34 = 0.07
0.34 1 0.077
0.34 0.07
0,9986
0.0921
polbooks
83.81% = 3.81%
86.67% + 1.90%
83.81% 2.33%
0.80 = 0.04
0.84 = 0.03
0.81 + 0.03
0.3353
0.1051
krunssikk
89.76% = 0.80%
90.46% 1 1.18%
90.38%
1.49%
0.90 1 0.01
0.90 : 0.01
0.90 0.02
0.5843
0.3855
moignaed
63.50%
1.35%
535
1.10%
62 66%
1.17%
0.62 0.01
0.61 0.01
0.61
0.0312
0.0101
alsson
93.40%
2.70%
94.03%
+ 2.12%
94.36%
0.78%
0.03 + 0.03
0.94 + 0.02
0.94 + 0.01
0.9266
0.2534
panl
66.98%
8.80%
68.85% 1 2.26%
52%
2.30%
0.64 1 0.03
0.66 1 0.02
0.66 0.03
0.7863
0.2130
myyloidpprogeiiioos
79.81%
2.0056
28% 2.50%
80.60%
2.58%
0.8911
0.1960
cilar
98.38%
0.145%
98% # 0.17%
98.42%
0.17%
0.98 = 0.00
0.98 = 0.00
0.98 0.00
0.0825
0.0550
fushion-mnist
94.42%
1.10%
95.28% + 0.16%
05.23%
0.16%
0.94 + 0.01
0.95 + 0.00
0.95 0.00
0.3492
0.0054
10

---

Published in Transactions on Machine Learning Research (04/2025)
plausible considering the large hyperparameter space available for PGD: more aggressive grid search learning rates, total number of epochs, regularization parameters, and initializations could potentially yield results that rival or even surpass those of the moment-based method.
To explore this further, we provide an additional comparison between our methods and PGD under ap- proximately equal computational time constraints using the one-vs-rest scheme. Specifically, according to Table []] the average runtime per training fold for the Moment method is approximately two orders of mag- nitude larger than that for PGD. Therefore, we randomly generated 100 different initializations for PGD, with each initialization vector drawn uniformly from the unit sphere subject to the condition w² G'u > 0, and report the best performance among these random initializations in Table below.
Table 4: Synthetic and real dataset accuracy, F1, and optimality gap with one-vs-rest training. PGD (RANDOM INIT) results are the best among 100 random initializations.
data
PGD
PGD (random In36)
tsed
SDP
Moneut
PGD
PGD (condom Init)
(micer))
SDP
Monscut
SDP
Monseut
troe
0.217%
100.0%
0.00%
100.0%
0.00%
[U00
0.9054
tree
90.2566
0.01%%
0.23%
09.91%
0.007%
0.00
1.00
1.00
0.00
1.00
0.00
0.9465
0.0205
teor
00.365
0.1633
96.07%
5.21%5
00.865
0.103
90.03%
0.13%
0.00
0.34
0.06
0.00
0.00
0.00
0.00
0.5921
0.0728
Soutball
40.87%
4.4355
37.39%
0.36
kezete
5000066
0.05
0.07
0.0 6 3.06
0.00
0.9135
0.0818
polbooks
$4.70%6
2.3375
1.9066
81.707%
0.02
0.0
0.00
0.1711
krumeadk
0.03
0.02
0.00
0.7519
0.0021
meignaed
0.00
0.0825
74.775
5.16
76.17%
6.885
81.20%
0.06
0.4118
0.0070
It's worth noting that for PGD, we follow Cho et al. (2019), where the initialization w is determined based the solution w' of a soft-margin SVM in the ambient Euclidean space of the Lorentz model. This choice typically ensures better initialization, contributing to the stability of optimization, especially when numerous local optima may exist. Consequently, we observed that the best PGD performance among 100 different random initializations do not significantly improve its performance in this regime. Nevertheless, we do not exclude the possibility that more strategic hyperparameter tuning under similar computational constraints might yield improved PGD performance
Based on these insights, we offer practical recommendations for method selection tailored to dataset char- acteristics and scale. For small-scale, low-dimensional hyperbolic datasets, particularly in 2D, where a hyperparameter-fres solution is desired, the SDP and sparse moment relaxation methods clearly excel. Ad- ditionally, we advocate exhibiting significant class overlap. For instance, arguably Gaussian 1 and 3 have greater overlap compared to Gaussian 2 (Figure 3), leading to a notable performance drop in the PGD method. We suspect that more mixing likely leads PGD to poor local minima, although this conjecture war- rants further quantitative investigation. For larger dataset such as MNIST or comparable modern machine learning benchmarks, in which generalization to unseen data takes priority over strict global optimality, we recommend PGD due to its significantly lower computational demands compared to our relaxed proposals.
5 Discussions
In this paper, we provide a stronger classification performance on hyperbolic support vector machine using semidefinite and sparse monent-sum-ofssquree relaxations on the hyperbolic support vector machine prob- lem compared to projected gradient descent. In the one-vs-rest settings, we observe that they achieve better classification accuracy and Fl score than the existing PGD approach on both simulated and real dataset. Additionally, we discover small optimality gaps for cooment-sum-ofsppeee relaxation, which approximately certifies global optimality of the moment solutions.
Perhaps the most critical drawback of SDP and sparse moment--uum-ffssquarre relaxations is their limited scalability. The runtime and memory consumption grows quickly with data size and dimension. We at- tempted dividing this challenge into sub-tasks, such as using onc-vs-one training scheme, to cut overall runtime and memory, but observe smaller performance advantage over the PGD bascline as they seem to perform better in this alternative setting. Also, if given the same computational resources as moment-sum-
11

---

Published in Transactions on Machine Learning Research (04/2025)
of-squares, suspect that PGD may be able perform par with the moment-relaxation method using rather greedy hyperparameter hunt such specifically tunning the learning rates and regularization factors.
But it is not completely without hope. For relatively large datasets, we could develop more heuristic approaches for solving our relaxed optimization problems to achieve runtime comparable with projected gradient descent. Combining the GD) dynamic with interior point iterates in a problen-dependent manner could be useful Yang al. (2023).
It remains to show if have performance gain in either runtime optimality by going through the dual of the problem or by designing feature kernels that map hyperbolic features to another set of hyperbolic features (Lensink et al. 2022). Nonetheless, we believe that our work introduces a valuable perspective applying SDP and Moment relaxations - to the geometric machine learning community.
References
Mosek ApS. Mosek optimizer api for python. Version, 9(17)66 4, 2022.
Afonso S Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163:145-167, 2017.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28. Princcton university press, 2009.
Dimitris Bertsimas and Dick den Hertog, Robust and adaplive oplimizaaionn Dynamic Ideas LLC, 2022.
Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinile oplimizalion and convex algebraic geometry. SIAM, 2012.
Lucas Bryute, Viktor Larsson, José Pedro Iglesias, Carl Olsson, and Fredrik Kahl. On the tightness of semidefinite relaxations for rotation estimation. Journal of Mathematical Imaging and Vision, pp. 1-11, 2022.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural net- works. Advances in neural information processing systems, 32, 2019.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. ar preprint XXi::205500044, 2020.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1 27, 2011.
Eli Chien, Chao Pan, Puoya Tabaghi, and Olgica Milenkovie. Highly scalable and provably accurate clas- sification in poincaré balls. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 61-70. |EEE, 2021.
Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-margin classification in hyperbolic space. In The 22nd international conference on artificial intelligence and statistics, pp. 1832-1840. PMLR, 2019.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273 297, 1995.
Raúl E Curto and Lawrence A Fialkow. Truncated k-moment. problems in several variables. Journal of Operator Theory, pp. 189 226, 2005.
Anders Eriksson, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin. Rotation averaging and strong duality. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 127-135, 2018.
Rong-Eb En Fan, Kai-Wet Chang, Cho-Jui Hsich, Xiang-Ri Rui Wang, and Chih-Jen Lin. Liblinear: library for large linear classification. the Journal of machine Learning research, 9:1871-1874, 2008.
12

---

Published in Transactions on Machine Learning Research (04/2025)
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Advances in neural information processing systems, 31, 2018.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(0):1115-1145, 1995.
Charles R. Harris, K. Jarrod Millman, StAlfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapcau, Eric Wieser, Julian Taylor, Scbastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime FernAgudez del RAyo, Mark Wiebe, Pearu Peterson, Pierre GAlrard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weekesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585:357aA$366 2020. doi:
Didier Henrion and Jean-Bernard Lasserre. Detecting global optimality and extracting solutions in gloptipoly. Tn Positive polynomials in control, pp. 293-33 -30.0. Springer, 2005.
J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9(3):90 95, 2007. doi: 10.1109/MCSE..2 M0009/MCSF.2000.555..
Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Tvan Oseledets, and Victor Lempitsky. Hyper- bolic image embeddings. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 6418-6428, 2020.
Anna Klimovskaia, David Lopez-Paz, Léon Bottou, and Maximilian Nickel. Poincaré maps for analyzing complex hierarchies in single-cell data. Nature communicalions, 11(1):2666 2020.
Alex Krizhevsky, Geoffrey Hinton,
Learning multiple layers of features from tiny images. 2009.
Jan Krumsick, Carsten Marr, Timm Schroeder, and Fabian J Theis. Hicrarchical differentiation of myeloid progenitors is encoded in the transcription factor network. PloS one, 6(8)xe2264, 2011.
Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal optimization, 11(3):796-88 817, 2001.
Jean B Lasserre. The moment-sos hierarchy. Proceedings of the International Congress of Mathemalicians: Rio de Joneiro 2018, pp. 3773 3794. World Scientific, 2018
Keegan Lensink, Bas Peters, and Eldad Haber. Fully hyperbolic convolutional neural networks. Research in the Mathematical Sciences, 94)):60, 2022.
Wes McKinney et al. Data structures for statistical computing in python. In Proceedings of the 9th Python in Science Conference, volume 445, pp. 51-56. Austin, TX, 2010.
Gal Mishne, Zhengchao Wan, Yusu Wang, and Shong Yang. The numerical stability of hyperbolic represen- (ation learning. In International Conference on Machine Learning, pp. 24925 24949. PMLR, 2023.
Victoria Moignard, Steven Woodhouse, Lalch Haghverdi, Andrew J Lilly, Yosuke Tanaka, Adam C Wilkin- son, Florian Buettner, Iain C Macaulay, Wajid Jawaid, Evangelia Diamanti, et al. Decoding the regulatory network of early blood development from single-cell gene expression measurements. Nature biotechnology, 33(3):269 276, 2015.
Maximillan Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Ad- vances in neural information processing systems, 30, 2017.
Jiawang Nie. Moment and Polynomial Optimization. SIAM, 2023.
Andre Olsson, Moenakshi Venkatasubramanian, Viren K Chaudhri, Bruce J Aronow, Nathan Salomonis, Harinder Singh, and H Leighton Grimes. Single-cell analysis of mixed -incage states leading a binary cell fate choice. Nature, 537(7622)6698 600, 2016.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Franziska Paul, YaáĀZara Arkin, Amir Giladi, Diego Adhemar Jaitin, Ephraim Kenigsberg, Hadas Keren- Shaul, Deborah Winter, David Tara-Astiaso, Meital Gury, Assaf Weiner, et al. Transcriptional hetero- geneity and lineage commitment in myeloid progenitors. Cell, 163(7):1663 1677, 2015.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Wei Peng, Thomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey, IEEE Transactions on pottern analysis and machine intelligence, 44(12))10023 10044, 2021.
John Platt. Sequential minimal optimization: fast algorithm for training support vector machines. 1998.
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large maryin classifiers, 10(3):61-77 74, 1999.
David M Rosen, Luca Carlone, Afonso S Bandeira, and John Leonard. certifiably correct algorithm for synchronization over the special euclidean group. In Algorithmicc Foundations of Roboties XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics, pp. 64-79. Springer, 2020.
Ryohei Shimizu, Yusuke Mukuta, and Tatsuya Harada. Hyperbolic neural networks arXiv preprint arXiv:2006.0880 08210, 2020.
Naum Shor. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25: 1-11, 1987.
Andrii Skliar and Maurice Weiler. arXiv:2308.1500 2023.
Hyperbolic convolutional neural networks. ar preprint
Ondrej Skopek, Octavian-Eugen Ganea, and Gary Bécigneul. Mixed-curvature variational autoencoders. arXiv preprint erXio:1911.0844 2019.
Lanhui Wang and Amit Singer. Exact and stable recovery of rotations for robust synchronization. Information and Inference: A Journal of the IMA, 2(2):145-19)) 193, 2013.
Melanie Weber, Manzil Zaheer, Ankit Singh Rawat, Aditya K Menon, and Sanjiv Kumar. Robust large- margin learning in hyperbolic space. Advances in Neural Information Processing Systems, 33:17863 17873, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Pashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1 708.077777 2017.
Heng Yang, Ling Liang, Luca Carlone, and Kim-Chuan Toh. An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization. Mathematical Programming, 201(1):40944P) 472, 2023.
Richard Zhang. On the tightness of semidefinite relaxations for certifying robustness to adversarial examples. Advances in Newral Information Processing Systems, 33:3808 38200, 2020.
A Proofs
A.1 Deriving Soft-Margin HSVM with polynomial constraints
This section describe the key steps to transform from Equation (6) Equation 7 for an efficient implemen- tation in solver as well as theoretical feasibility derive semidefinite and moment -um-of-squares relaxations subsequently.
14

---

Published in Transactions on Machine Learning Research (04/2025)
By introducing the slack variable &, the penalty term in Equation
rewrite Equation
6
into
min wERd+1
w Gw + C &
Gu
222
i=1 s.t. & > 0, vi E [n]
(16)
& > arcsinh(1) arcsinh(((bl))) w), vi [n]
w² Gw 3 0
then by rearranging terms and taking sinh both sides, it follows that
1+ 12 e g(
-T w e sinh(aresinh(1)) E.) = 2
ei +
(17)
2
where the last equality follows from hyperbolic trig identities. To make it ready for moment-suun----qqual relaxation, we turn the function into polynomial constraint by taking the taylor expansion up to some odd orders (we need monotonic decreasing approximation to g(-), so we need odd orders).
If taking up to the first order, we relax the problem into Equation relax the original problem to,
If taking up to the third order, we
min wER SER" 2
w Gw +
>
&
1=1
s.t. & > Vi E [n]
(18)
(b(0)TTM 21
22 +
V2 2
vi E [n]
T Go 00 0
It's worth mentioning that we expect the lower bound gets tighter as we increase the order of Taylor ex- pansion. However, once we apply the third order Taylor expansion, the constraint is no longer quadratic, climinating the possibility of deriving a semidefinite relaxation. Instead, we must rely on moment-sum-on squares relaxation, potentially requiring higher order of relaxation, which may be highly time-costly.
It is also worth noting that such Taylor expansion is consistent with the aresinh when allow the curvature of the hyperbolic space to vary. Specifically, one can show that as the curvature approaches 0 (i.c. as the hyperbolic space tends to Euclidean), both the aresinh formulation in Equation (6) and Equation ( formulation recovers the standard Euclidean SVM problem. This further justifies the naturalness of taking such a Taylor expansion.
A.2 Stereographic projection maps a straight line on HP to an arc on Poincaré ball B²
Suppose w [Wo W1, W2] is a valid hyperbolic decision boundary (i.e. w * w < 0), and suppose a point on the Lorentz strihttt line, x = [wo, x22 with u x 0, is mapped to point, v = [vi, 22].1 in Poincaré space, then have
Wi
W 11
W222 = 0
2
222
(19)
0i
I+20
.11
1/
1+20
If w. > O, we further have
W/
w
+ w 1,
U1
+
02
(20)
We
Wo
w
'ntte that in Cho 2019), authors outliers than the former formulation.
E, instead of V2C..
We consider formulation less sensitive
15

---

Published in Transactions on Machine Learning Research (04/2025)
/
/wi+u3 w
i.e. the straight line on Poincaré space is an are on circle centered at
w2 with radius wne
1.
One could show that if wi O, then it is the "arc" of infinitely large circle, or just Euclidean straight line passing through the origin with normal vector (w), With this simplification, one could plot the decision boundary on the Poincaré ball easily.
A.3 An extension curvature other than -1
Throughout the paper, assume that the hyperbolic space has constant negative curvature -1 without loss of generality. Our analysis and relaxation easily extend to curvature other than -1.
Define as the negative curvature. That is, all the discussions in the main text are about c c= 1. To derive the prooblem formulation and associated relaxation, we can follow Table in Skopek et al. (2019) and retrace the proof the supplemental material in Chien et al. (2021), then we see that the decision function, the objective, and many constraints stay the same except the following slack variable constraint Equation [16
1 arcsinh(1) - -aresin w) Vi e [m],
& >
(21)
c
and with some rearrangements, we have
(b(0)T > sinh(aresin(()--eE)) 1 V2 E +
1 1+ /2
cf. =: =:Gc(E)),
(22)
2
whose Taylor expansion around &: = 0 gives
ge(Ei) R 22c;,
(23)
Essentially, this is nothing but adding curvature factor e into the problem formulation, so that solving the SVM problem in other curvature has additional theoretical challenges. The rest follows likewise in Appendix A.1
The intuition behind why only this single constraint is affected can be made as follows: SVM cares about direction of the decision boundary, and if the optimal direction is found for an embedding in one c, the "same" direction is also optimal for the same embedding stretched to other C; but since the slack variables are associated to distance measures, they need to be scaled accordingly.
Solution Extraction in Relaxed Formulation
In this section, we detail the heuristic methods for extracting the linear separator from the solution of the relaxed model.
B.1 Semidefinite Relaxation
For SDP, we initially construct a set candidates v derived from (W, w. Then, among candidates in this set, we choose the one that minimizes the loss function in Equation
(W,w,E)
The candidates, denoted as w's, include
Scaled top eigendirection: to Amaxx where Anax and umax are the largest eigenvalue and the eigenvector associated with the largest eigenvaue;
Gaussian randomizations: sample v ~ N(w, W ww T We empirically generate 10 samples
from this distributions;
2 method mentioned slide 14 http::/wwweeoooooeeeaeeeeee/eees
16

---

Published in Transactions on Machine Learning Research (04/2025)
3. Scaled matrix columns: if it were the case that W ww"" then each column of W contains scaled by some entry within itself. Using columns of W divided by the corresponding entry of w (e.g. divide first column by wo, second column by w1, and so on), we get d + 1 many candidates
t w's:
4. Nominal solution: き w, i.c. include w itself as candidate.
Typically the top eigendirection is selected the best candidate.
B.2 Moment-Sum-of-S of- Sq-ares Relaxation
In monent--sum-oo-qquare relaxation, the decision variable is the truncated multi-scquence z, but could decode the solution from the moment matrix Mn[zz] it generates. We are able to extract the part in TMS that corresponds to w = [wo, Wi,.., by reading off these entries from the moment matrix, which is already a good enough solution.
For example, in d 2, A - 2, one of the sparcity group, say ga)) consists of [w, which has monomials generated Equation 12p. Define @ as a binary operator between two vectors of monomials that generates another vector with monomials given by the unique combinations of the product into vectors, such that
(w x w
-w wi, w WoWl, WoW2, w|w2].
(24)
Then, monomials generated can be more succinctly expressed as
oo = [1, u² E1, (w u²)"" (un(1) -.],
(25)
and the moment matrix can be expressed in block form
w
(w @ w) w(w @ w)"
E 8 ff
ww? (we())
w(wEi) yr EI (
{1
?
(ww @ w)
Ma(z(1)]
f2())
(26)
@ w
(w @ w)w"
w @ w(w @ w)
w @ wi (mwE)) )m whi (wo() )² cl"""
w[1
wLww T
w
wC (w @ w) <i(w @ w)
w
st
Note that the value for w (the red part) is contained close to the top left corner of the moment matrix, which provides good linear separator w in this problem.
C On Moment Sum-of-Squares Relaxation Hierarchy
In this section, provide necessary background on moment-ssum--ffsqquree hierarchy. We start by con- sidering a general Polynomial Optimization Problem (POP) and introduce the sparse version. This section borrows substantially from the course note
C.1 Polynomial Optimization and Dual Cones
Polynomial optimization problem (POP) in the most generic form can be presented as
(POP) p² min m(x) rER"
s.t. h₂(2) 0 for i 1,2, .... (x(x) > 0 for = 1,2,
where p(z) is our polynomial objective and h,(x), (x) are our polynomial equality and inequality constraints respectively. However, in general, solving such POP to global optimality is NP-hard (Lasserre
2001 Nie
SChapter 5 Moment Relaxation: htees/aoooottpp/////aaaggegeeee http::///hwuknnooooooooaaaaaaiae
17

---

Published in Transactions on Machine Learning Research (04/2025)
2023
To address this challenge, we leverage methods from algebraic geometry [Blekherman et al. 2012 Nie 2023 allowing us to approximate global solutions using convex optimization methods.
To start with, we define sum-of-squares (SOS) polynomials as polynomials that could be expressed as a sum of squares some other polynomials, and we define Σ[z] to be the collection SOS polynomials. More formally, we have
p(x) E Σ|a] 3/ 92. Im E R(x] p(x) = Σ (
k=1
where R[æ] denotes the polynomial ring over I.
Next, we recall the definitions of quadratic module and its dual. Given a of polynomials g (0i, 92.---9 2), the quadratic module generated by is defined as
Qmodule(ge gg] foo + 119 + + orgi or's are SOS for i e [
ogg oo E E[r] for i e [1]
and its degree 2d-truncation is defined as,
Emodulelgl2d
oigs deg(a,g)) S 2d, 0, E Σ[ø] for i E [1]
where 9o = 1. It has been shown that the dual cone of Qmodulelg|2a is exactly the convex cone defined by the PSD conditions of the localizing matrices, M(g]2a (= (R) |Ma[[>] > 0, In..g [=] i for [T], where Ma[s] = [<[]aa]<]]] refers to the tt order moment matrix, Ld [2] fz(g(()) [x]] refers the dth order localizing matrix of 9i generated by 2, and f=(x)) = (J2.9.) (z, vec(g:)) refers to the linear functional associated with applied functional f= to the symmetric polynomial matrix g(r) [>]][>]] is clement-wise. Formally speaking, for all g' E Qmodule(g)az and for all g E Mig]aa, we have (g' g) 2 0.
Ji E R[x]aa- It is worth mentioning that the application of the linear
Similarly, given a set of polynomials h = [/1, he....,.mml the ideal generated by h defined as,
Ideal[h]
Σ Ashu X₂
R|x] for i 11] 10)
and its degree 2d-trumcation is defined as,
m
[d]al 2d
Σ
Achi Ae E R[oo) 2d for E [4]
where ' are also called polynomial multipliers. Interestingly, it is shown that can perfectly characterize the dual of the sum of idcal and quadratic module,
(Ideal[b]24 2a + Qmodule|g]2s) = Z n Migglas
where 2[1]2a = (z E (n( [= = 0 for i E [?] is the linear subspace that linear functionals vanish on Ideal[h]2d and M[g]es {a E (m)).2)) Ma[=] >= 0, I.d.g. [z] > O for E [1] is the convex cone defined by the PSD conditions of the localizing matrices.
With these notions setup, we can reformulate the POP above into the following SOS program for arbitrary K N the relaxataion order,
2 max ?
s.t. p(z) E [d]al[ + Qmodule|g]a..
18

---

Published in Transactions on Machine Learning Research (04/2025)
whose optimal value produces lower bound to p", ie. 72 S p", and its dual problem of the SOS program above is.
8 min (fs.P) (n))(n.2d)
8.1. E 2 2 n Miglea
1 =1
This pair of SOS programs is called the noment-suumoof-qquaee hierarchy first proposed in Lasserre h001h. It particularly useful as has been shown that
1 for all N,
and be and {Bx*]r Jrc are two monotonically increasing soquences. In our work, we implement our SOS programs following the dual roule.
C.2 Sparse Polynomial Optimization
In this section, we briefly discuss how sparse moment-suu--of-qquree is formulated. Using the same sparsity
pattern defined in Section 3 (i.e. q (w), we first introduce the notion of correlated sparsity.
Definition Correlated Sparsity for an objective p R[xe] and associated set of constmaints means
Por any construint gı(g), E [1], il only involves term in one sparsily group g for some E [r]
2. The objective can be splil inlo
p(q) Σ ()) for pi R Vie [n]
The grouping satisfies the running inlesection properly (RIP), i.e. for all E 21, 1}, we have
(U
n (g c (()), for some &
In our casc, the first property is straightforward. For the second, we may define explicitly ()()()) Pi(w, = 2m w +w+++C Ct2 so that we get back the original objective after summation. The last property direct follows from the star-shaped structure, i.e. Vi E {1,2, ..., 1}, we indeed have (U, (()) (+++) w C ()) Hence, our sparsity group indeed satisfies all three property and thus we have correlated sparsity in the problem.
With correlated sparsity and data regularity (Putinar's Positivestellentz outlined in Nie 2023
are able to decompose the Qmodule generated by the entire set of decision variables into the Minkowski sum of Qmodules generated by each sparsity group of variables, effectively reducing the number of decision variables in the implementations. For a problem with only inequality constraints, which our case for HSVM, the sparse POP for our problem reads as
max 7
s.t. p(x) - E E Σ Qmodule[g(q'))
and we could derive its dual accordingly and present the SDP form for implementation in Equation
14
19

---

Published in Transactions on Machine Learning Research (04/2025)
D Platt Scaling (Platt et al., 1999)
Platt scaling (Platt et al. 1999 is common way to calibrate binary predictions to probabilistic predictions in order to generalize binary classification to multiclass classification, which has been widely used along with SVM. The key idea is that once a separator has been trained, an additional logistic regression is fitted on scores of the predictions, which can be interpreted as the closeness to the decision boundary.
In the context of HSVM, suppose w" is the linear separator identified by the solver, then we find two scalars, A, B E R, with
P(y = 1/2,) = + exp(A(wu * x;) + B}
(27)
where * refers to the Minkowski product defined in Equation I The value of A and B are trained on the trained set using logistic regression with some additional empirical smoothing. For one-vs-rest training, we will then have K sets of (A, B) to train, and at the end we classify sample to the class with the highest probability. See detailed implementation here https:/hhome.wwrccclleeeeeee platt.py in LIBSVM.
malin/program/iiine /wwbs/bbbbm/oo /do//-
E
Detailed Experimental Results
This section documents the experiment details. The code base is adapted partly from LIBSVM D with a ASD-3-Clause license for Platt scaling, hyplinear| with an MIT license for PGD implementation, and stable-hyperbolic with an MIT license for hyperbolic related functions and obtaining tree embeddings. The data used is described in Section
Our Python code also uses some common publicly available packages, including NumPy (Harris et al. 2020 with BSD license, Matplotlib (Hunter) 2007) with a BSD license, Pandas (McKinney et al. 2010) under a BSD license, scikit-learn (Pedregosa et al. 2011) with a BSD license, MOSEK (ApS) 2022) a closed-source commercial solver, and toml with an MIT license.
E.1 Visualizing Decision Boundaries
Here we visualize the decision boundary of for PGD, SDP relaxation and sparse moment-suu--ofssquare relaxation (Moment) on one fold of the training to provide qualitative judgements.
We first visualize training on the first fold for Gaussian dataset from Figure 3 in Figure 5 train set with circles and test set with triangles, and color the decision boundary obtained by three methods with different colors. In this case, note that SDP and Moment overlap and give identical decision boundary up to machine precision, but they are different from the decision boundary of PGD method. This slight visual difference causes the performance difference displayed in Table
We mark the
We next visualize the decision boundary for tree 2 from Figure 3 in Figure Here the difference is dramatic: we visualize both the entire data in the left panel and the zoomed-in one on the right. We indeed observe that the decision boundary from moment- of relaxation have roughly equal distance from points to the grey class and to the green class, while SDP relaxation is suboptimal in that regard but still enclosing the entire grey region. PGD, however, converges very poor local minimum that has very small radius enclosing no data and thus would simply classify all data sample to the same class, since all data falls to one side of the decision boundary. As commented in Section 4 data imbalance is to blame, in which case the final converged solution is very sensitive to the choice of initialization and other hyperparameters such as learning rate. This is in stark contrast with solving problems using the interior point method, where after implementing into MOSEK, we are essentially care-free. From this example, we see that empirically sparse moment-sunnof-sann off-suusssssssss relaxation finds linear separator of the best quality, particularly cases where PGD is expected to fail.
hitpps: http::/gggthuubooomoeo /cjinn /ibbvm
httpps///gihuub.cm///hhh//////// hylinea
20

---

Published in Transactions on Machine Learning Research (04/2025)
data
Train
Test
mathod
PGD
Moment
Figure 5: Decision boundary obtained by each method on one fold of train test split on Gaussian dataset
in Figure While SDP and moment overlap, they differ from the PGD solution.
data
400
Test
PGD
SDP
Moment
Figure Decision boundary visualization of the train split from the first fold. The left panel shows all the data and the right panel zooms in to the decision boundary. PGD gets stuck in bad local minima (a tiny circle in the right panel) and thus classily all data samples to one class. While both SDP and moment relaxation give a decision boundary that demarcate one class from another, Moment has roughly equal margin to samples from the grey class and to samples from the green class, which is preferred in large-margin learning.
21

---

Published in Transactions on Machine Learning Research (04/2025)
E.2 Synthetic Gaussian
To generate mixture of Gaussian in hyperbolic space; we first generate them in Fuclidean space, with the center coordinates independently drawn from standard normal distribution. K such centers are drawn for defining K different classes. Then we sample isotropic Gaussian at respective center with scale s. Finally, we lift the generated Gaussian mixtures to hyperbolic spaces using expo- For simplicity, we only present results for the extreme values: K E (2,5), 8 E {0.4, 1}, and C E {0.1,10).
For each method (PGD, SDP, Moment), we compute the train/test accuracy, weighted F1 score, and loss on each of the folds of data for specific (K, s, C) configuration. We then average these metrics across the 5 folds, for all methods and configurations. To illustrate the performance, we plot the improvements of the average metrics of the Moment and SDP methods compared to PGD as bar plots for 15 different seeds. Outliers beyond the interquartile range (Q1 and Q3) are excluded for clarity, and zero horizontal line is marked for reference. Additionally, to compare the Moment and SDP methods, we compute the average optimality gaps similarly, defined in Equation 15). and present them as bar plots. Our analysis begins by examining the train/test accuracy and weighted F1 score of the PGD, SDP, and Moment methods across various synthetic Gaussian configurations, shown in Figures to 10
Across various configurations, observe that both the Moment and SDP methods generally show improve- ments over PGD in terms of train and test accuracy as well as weighted F1 score. Notably, we observe that Moment method often shows more consistent improvements compared to SDP. This consistency is evident across different values of (K, C), suggesting that the Moment method is more robust and provide more generalizable decision boundaries. Moreover, we observe that 1. for larger number of classes (i.e. larger K), the Moment method consistently and significantly outperforms both SDP and PGD, highlighting its capability to manage complex class structures efficiently; and for simpler datasets (with smaller scale s), both Moment and SDP methods generally outperform PGD, where the Moment method particularly shows promising performance advantage over both PGD and SDP.
Next, we move to examine the train/test loss improvements compared to PGD and optimality gaps com- parison across various configurations, shown in Figures 11 to 14 We observe that for K = 5, the Moment method achieves significantly smaller losses compared to both PGD and SDP, which aligns with our previous observations on accuracy and weighted F1 scores. However, for K 2, the losses of the Moment and SDP methods are generally larger than PGD's. Nevertheless, it is important to note that these losses are not direct mcasurements of our optimization methods' quality; rather, they mcasure the quality of the extracted solutions. Therefore, a larger loss does not necessarily imply that our optimization methods are inferior to PGD, as the heuristic extraction methods might significantly impact the loss. Additionally, we observe that the optimality gaps of the Moment method are significantly smaller than those the SDP method, suggesting that Moment provides better solutions. Interestingly, the optimality gaps of the Moment method also exhibit smaller variance compared to SDP, as indicated by the smaller boxes in the box plots, further supporting the consistency and robustness of the Moment method.
Table 5: Average runtime to finish 1 fold of training for each model on synthetic datasct.
runtime SDP
data
PGD
Moment
gaussian 1
0.99s
0.52s
6.60s
gaussian 2
2.83s
0.56s
30.59s
gaussian 3
4.19s
0.76s
51.84s
tree
2.17s
0.95s
39.89s
tree
2.16s
0.92s
51.18s
tree 3
1.67s
0.74s
59.68s
22

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test accuracy and train/test fl improvements compared to gd (for K=2, s=0.4, and C=0.1)
train accuracy improvement
lest: accuracy improverent
train f1 improvement
Lest f1 improvement
0.005
0.005
0.002
0.001
0.003
0.003
0.000
0.000
0.001
0.001
-0.002
00.007
5dp
moment
sdp
moment
50p
mom ent
sdp
moment
Train/test accuracy and train/test f1 improvements compared to gd (for K=2, s=0.4, and C= C=10).)
train accuracy improvement
test accuracy improvement
train f1 Improvement
best Improvement
0.010
0.010
0.002
0.002
0.000
0.008
0.001
0.001
0.000
0.008
0.000
0.004
0.002
-0.001
-0.001
-0.002
-0.002
-0.002
-0.004
-0.004
sdp
moment
sdp
sdp
sdp
Figure 7: Train accuracy and train/test improvements compared to PGD across various C' E (0.1,10) for K = and s = 0.4
23

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test accuracy and train/test fl improvements compared to gd (for K=2, s=1.0, and C=0.1)
train accuracy improvement
lest: accuracy improverentt
train f1 improvement
Lest f1 improvement
0.020
0.020
0.015
0.010
0.004
0.004
0.000
0.000
-0.005
-0.010
-0.002
-0.002
0.004
-0.004
5dp
moment
sdp
moment
50p
moment ent
sdp
moment
Train/test accuracy and train/test f1 improvements compared to gd (for K=2, s=1.0, and C=10.0)
train accuracy improvement
test accuracy improvement
train f1 Improvement
best Improvement
0.004
0.025
0.004
0.025
0.002
0.002
0.000
0.015
0.015
-0,002
-0.002
0.010
-0.0 0.004
0.010
-0.004
0.006
0..0 0000
0.008
0.008
0.000
0.000
-0.010
0.010
-0.005
0.012
sdp
moment
sdp
sdp
sdp
Figure 8: Train/test accuracy and train /test improvements compared to PGD across various C' E (0.1,10) and for K and 1.0
24

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test accuracy and train/test improvements compared gd (for K=5, s=0.4, and C=0.1)
accuracy improvement
accuracy improvement.
improvement
improvement
0.20
0.150
0.175
0.125
0.125
0.15
0.100
0.125
0.100
0.075
0.075
0.050
0.050
0.025
0.025
0.025
0.000
0.00
0.000
-0.025
moment
moment
Train/test accuracy and train/test f1 improvements compared gd (for K=5, 500.4, and C= C=100
accuracy improvement
accuracy improvement
improvement
improvement
0.02
0.02
0.02
0.00
-0.02
0.02
-0.02
-0.04
-0.01
-0.06
-0.02
0.06
0.008
sdp
sdp
Figure 9: Train/test accuracy and train/tees ttest improvements compared PGD across various C E {0.1, 10}
for K = 5 and 0.4
25

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test accuracy and train/test improvements compared gd (for K=5, s=1.0, and C=0.1)
accuracy improvement
accuracy improvement
improvement
improvement
0.06
0.06
0.04
0.06
0.04
0.02
0.00
0.00
-0.02
-0.02
Train/test accuracy and train/test f1 improvements compared gd (for K=5, s=1.0, and C=10.0)
accuracy Improvement
accuracy improvement
improvement
improvement
0.02
0.02
0.02
0.01
0.01
0.00
0.00
0.00
-0.02
-0.02
-0.01
-0.04
0.03
-0.06
-0.04
0.05
-0.06
-0.06
sdp
sdp
Figure 10: Train/tess /test accuracy and train/test improvements compared PGD across various C' E {0.1, 10} for K = 2 and 1.0
26

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test loss improvements compared to gd & optimality gaps (for K=2, s=0.4, and C=0.1)
improvement
improvement
optimality gap
12
12
0.9
10
0.7
0.5
0.3
moment
Train/test loss improvements compared to gd & optimality gaps (for K=2, 5=0.4, and C=10.0)
improvement
improvement
optimality gap
100
100
1.0
80
0.8
60
0.6
40
40-
0.4
20
20
0.2
0.0
momentt
moment
moment
Figure 11: Train/test /tsst loss improvements compared PGD and optimality gaps comparison across various C {0.1, 10) for K 2 and 0.4
27

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test loss improvements compared to gd & optimality gaps (for K=2, s=1.0, and C=0.1)
improvement
improverent
optimality gap
0.35
0.30
0.16-
0.25
0.20
0.14
0.15
0.12
0.10
0.10
0.05
0.05
0.10
0.00
0.00
0.00
Train/test loss improvements compared to gd optimality gaps (for K=2, s=1.0, and C=10.0)
improvement
improvement
optimality gap
10.0
0.095
0.090
0.085
0.080
0.0
0.075
-2.5
-10
-15
0.065
Figure 12: Train/terr /tent loss improvements compared PGD and optimality gaps comparison across various
C {0.1, 10) for K 2 and
28

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test loss improvements compared to gd & optimality gaps (for K=5, 5=0.4, and C=0.1)
improvement
improvement
optimality gap
30-
20
20-
-10
-10
sdp
sdp
sdp
Train/test loss improvements compared to gd optimality gaps (for K=5, s=0.4, and C=10.0)
improvement
improvement
optimality gap
0.50
700
800
0.45
0.40
580
0.35
400
200
200
0.20
100
0.15
0.10
-100
sdp
moment
moment
Figure 13: Train /test loss improvements compared PGD and optimality gaps comparison across various
C (0.1, 10) for K and 0.4
29

---

Published in Transactions on Machine Learning Research (04/2025)
Train/test loss improvements compared to gd & optimality gaps (for K=5, s=1.0, and C=0.1)
improvement
improvement
optimality gap
0.16
0.14
0.12
0.10
0.08
0.06
sdp
moment
irain/test loss improvements compared to gd optimality gaps (for K=5, s=1.0, and C=10.0)
train improvement
improvement
optimality gap
1750
0.25
1250
1500
1000
0.20
1000
750
0.15
250
0.10
sdp
moment
sdp
moment
sdp
moment
Figure 14: Train/teen /test loss improvements compared to PGD and optimality gaps comparison across various
C 10) for K and
Lastly, we compare the computational efficiency these methods, where we compute the average runtime to finish fold of training for each model on synthetic dataset, shown in Table 5 We observe that sparse moment relaxation typically requires least one order of magnitude in runtime compared other methods, which to extent limits the applicability of this method to large scale dataset.
E.3
Real Data
In this section we provide detailed performance breakdown by the choice of regularization C' for both one- vs-one and one-vs-rest scheme in Tables 0 to 11
30

---

Published in Transactions on Machine Learning Research (04/2025)
Table 6: Real dataset performance (C = 0.1), one-vs-rest
data
test ace SDP
test fl [tuiero]
PGD
Moment
PGD
SDP
Moment
SDP
Moment
foothall
40.00%
5.07%
31.30% 1.74%
37.39% 4.43%
0.28 0.05
0.26 0.03
0.3928
0.1145
karate
50.00% = 6.39%
50.00% = 6.39%
50.001% = 6.39%
0.31 = 0.07
0.31 + 0.07
0.31 0.07
0.9155
0.0818
polbooks
83.81% + 2.33%
84.76% = 1.90%
84.76% + 1.90%
0.79 = 0.02
0.80 + 0.03
0.80 0.03
0.6334
0.3908
krumsiek
67.21% 2.64%
82.56% = 2.01%
85.69%
0.85%
0.63 = 0.02
0.80 + 0.08
0.83
0.01
0.6811
0.2025
molgnard
58.13% 2.31%
63.50%
1.90%
63.60%
1.66%
0.52
0.60 0.02
0.60
0.02
0.0435
0.0482
olssonn
54.23% 0.62%
78.90%
1.31%
81.51%
3.32%
0.43 +: 0.01
0.76 + 0.02
0.79
0.04
0.6734
0.3418
paul
32.03% + 1.23%
53.72% + 2.42%
64.53%
2.47%
0.22 + 0.02
0.47 + 0.03
0.60 0.03
0.4477
0.1214
mnpesoidprogeaitoors
50.39%
2.73%
69.65%
4.73%
76.69%
2.31%
0.05
0.02
0.6320
0.3018
Table 7: Real dataset performance (C 1.0), one-vs-rest
lest scc SDP
test f1 (mikroo
data
PGD
Moment
PGD
SDP
Moment
SDP
Moneent
football
40.87% + 4.43%
32.17% + 4.43%
37.39% + 4.43%
0.29 + 0.03
0.23
0.04
0.26 + 0.03
0.3430
0.1196
karate
50.00%% + 6.39%
50.00% + 6.39%
50.00% = 6.39%
0.31 = 0.07
0.34 0.07
0.31 + 0.07
0.9789
0.0816
polhooks
84.78% 1.90%
84.76% + 1.90%
84.76% + 1.00%
0.79 + 0.02
0.80
0.03
0.80 + 0.03
0.3828
0.1685
krumsiek
78.19% = 1. 1.83%
81.53% + 1.13%
86.16% = 0.81%
0.71 = 0.02
0.78 0.02
0.84 + 0.01
0.7520
0.1014
moignard
63.37%
0.70%
63.68% + 1.75%
63.78% 1.57%
0.62 = 0.01
0.60
0.0299
0.0401
olsson
58.31%
+ 0.64%
79.63% + 3.54%
81.20% + 3.68%
0.48 + 0.00
0.77 0.04
0.79 + 0.04
0.5281
0.0976
paul
51.86% = 1.20%
48. 60% + 3.69%
61.61% = 2.37%
0.48 = 0.02
0.11 = 0.05
0.61 = 0.02
0.1053
0.0936
myeloidprogemiitrss
50.94%
0.96%
70.12% + 3.28%
76.84% + 2.04%
0.54 + 0.02
0.67 0.04
0.75 + 0.02
0.6570
0.1074
Table Real dataset performance (C 10.0), one-vs-rest
data
test ace
test ft [micro]
PGD
Moment
PGD
SDP
Moment
SDP
Moment
football
11.74%
6.51%
31.78%
6.15%
37.39%
43%
0.29 = 0.05
+ 0.07
0.26
0.03
0.3130
0.0999
karate
50.00% + 6.39%
50.00% + 6.30%
50.00% + 6.39%
0.34 = 0.07
0.34 + 0.07
0.34
0.07
0.9086
0.0921
polbooks
2.33% 83.81%
84.76%
1.90%
84.76%
1.90%
0.79
0.02
0.80 1 0.03
0.80
0.03
0.1711
0.0991
krumstek
81.78%
2.66%
78.06%
2.12%
86.47%
0.64%
0.79 = 0.03
0.74 + 0.03
0.84
0.00
0.8008
0.0921
maignard
60.40%
1.03%
63.60%
1.80%
63.78%
1.57%
0.58
0.60 +: 0.02
0.60
0.02
0.0338
0.0396
obsson
74.27% = 5.15%
79.63%
+ 3.54%
79.94%
= 4.11%
0.69 : 0.07
0.77 1: 0.04
0.77 : 0.05
0.4118
0.0659
paul
46.61% = 1.95%
17.16%
= 2.20%
61.71%
2.36%
0.36 0.02
0.37 + 0.03
0.61 0.02
0.1034
0.0861
myyeoldprogeenitoss
69.31%
3.81%
65.71% 3.58%
76.69%
2.14%
0.66
: 0.01
0.7076
0.0842
In one-vs-rest scheme, we observe that the Moment method consistently outperforms both PGD and SDP
across almost all datasets and C in terms of accuracy and F1 scores. Notably, the optimality gaps, 77, for Moment are consistently lower than those for SDP, indicating that the Moment method's ''s solution obatin a better gap, which underscore the effectiveness of the Moment method in real datasets.
Table 9: Real dataset performance (C 0.1), one-vs-one
data
test acc SDP
test fl (micro)
?)
PGD
Moment
PGD
SDP
Moment
SDP
Moment
lootbell
39.13%
9.12%
42.61% + 5.07%
41.74%
7.06%
0.31 4 0.06
0.35 # 0.06
0.33 = 0.07
0.8195
0.7177
karate
50.00% + 6.39%
50.00%
6.39%
50.00%
6.39%
0.34 + 0.07
0.34 # 0.07
0.34 = 0.07
0.9155
0.0818
polbooks
81.90%
1.67%
86.67% + 1.90%
2.33% 83.81%
0.79 + 0.05
0.81 = 0.03
0.81 0.03
0.9237
0.6320
krunsick
89.76%
0.50%
90.46%
1.18%
90.38%
1.49%
0.90
0.01
0.90
0.02
0.5843
0.3855
moignard
61.31%
1.13%
62.38%
1.56%
62 63.
1.39%
0.63 + 0.01
0.61 = 0.01
0.61
0.01
0.0852
0.0376
oleson
93.41%
1.84%
94.04%
1.21%
94.36%
+ 0.78%
0.93 + 0.02
0.94 + 0.01
0.94
= 0.01
0.5102
0.4412
peul
64.86%
2.50%
68.85%
+ 2.26%
67.15%
2.26%
0.62 + 0.03
0.66 + 0.02
0.65 = 0.03
0.0974
0.5787
myeloiépragemioons
79.50%
2.50%
60.44%
2.47%
80.44%
1.84%
0.79 0.02
0.80 + 0.02
0.80
0.02
0.6504
0.5340
elfar
98.13%
0.16% 95.04%
98.12%
0.18%
98. 13%
0.18%
0.98 0.00
0.98 # 0.00
0.98 = 0.00
0.1505
0.0902
fushion-mnist
0.21%
95.28%
0.16%
95.12%
0. 18%
0.95 + 0.00
0.95 + 0.00
0.95 + 0.00
0.4262
0.1555
31

---

Published in Transactions on Machine Learning Research (04/2025)
Table 10: Real dataset performance (C = 1.0), one-vs-one
data
test ace SDP
test fl [uuiero)
PGD
Moment
PGD
SDP
Moment
SDP
Moment
foothall
40.00%
6.39%
12.61% 5.07%
41.74% 7.06%
0.35
0.33 0.07
0.7842
0.5012
karate
50.00% = 6.39%
50.00%% = 6.39%
50.00%% = 6.39%
0.31 0.07
0.31 + 0.07
0.31 0.07
0.9789
0.0816
polbooks
82.86% + 3.81%
86.67%
1.90%
83.81% + 2.33%
0.79 = 0.04
0.84 + 0.03
0.81 0.03
0.7263
0.2733
krumsšek
89.05% = 1.56%
90.46%
1.18%
90.22% + 1.66%
0.89 = 0.02
0.90 + 0.01
0.90
0.02
0.8171
0.2330
molgnard
63.22% 0.92%
62.43%
1.11%
62.06%
1.19%
0.62 0.01
0.61 + 0.01
0.61 0.01
0.0402
0.0419
olsson
92.47% 2.35%
94.01%
+: 2.12%
94.36%
0.78%
0.92 + 0.03
0.94 + 0.02
0.94 0.01
0.7517
0.3635
paul
66.98% + 2.80%
68.897 89%
2.28%
67. 17.
+ 2.345
0.64 + 0.03
0.66 + 0.02
0.06 0.03
0.7191
0.4195
mnpesoidrrogeaatooss
80.13%
1.99%
80.28%
2.50%
80.44%
1.84%
0.80
0.02
0.7540
cifar
98.42%%
0.16%
98.42%
0.17%
98.42% + 0.17%
0.98
0.98 + 0.00
0.98
0.00
0.0959
0.0573
fushion-mnis
94.97% 1. 0.22%
95.27%
0.16%
96.20% 1. 0.16%
0.95 0.00
0.96 1. 0.00
0.95 0.00
0.3635
0.0581
Table 11: Real dataset performance (C 10.0), one-vs-one
data
test ace SDP
test fl (mieroo] SDP
PGD
Moment
PGD
Moment
SDP
Moment
football
40.00% # 5.07%
42.61% = 5.07%
41.74% +: 7.06%
0.32 =: 0,06
0.35 +: 0.06
0.33
0.07
0.6689
0,2805
karate
50.00% = 6.39%
50.00% = 6.39%
50.00% + 6.39%
0.31 = 0.07
0.31 + 0.07
0.31 = 0.07
0. 0.9986
0.0921
polbooks
83.81% 3.81%
86.67%
1.90%
83.81%
2.33%
0.84
0.03
0.03
0.3383
krumsłek
89.32% 0.73%
90.16%
1.18%
89.00%
1.68%
0.89
0.90
0.01
0.89 0.02
0.9211
0.1349
moignard
63.50% + 1.35%
02.53%
+ 10%%
62.60%
+ 1.%%%
0.62 + 0.01
0.61 + 0.01
0.61 0.01
0.0312
0.0401
olsson
93-10% + 2.73%
94.03%
+ 2.12%
94.36% + 0.78%
0.93 = 0.03
0.94 + 0.02
0.94
0.01
0.9266
0.2534
paul
65.45%
2.41%
68.85%
2.26%
68.52%
2.30%
0.66
0.02
0.66 0.03
0.7863
myyeliidrrogenitoos
79.81%
2.00%
80.25%
2.50%
80.60%
2.58%
0.80 0,02
0.80 +: 0.02
0.81
0.02
0.8911
0,1960
cifar
98.18% + 0.14%
98.42% + 0.17%
98.42% + 0.17%
0.98 + 0.00
0.98 + 0.00
0.98
0.00
0.0825
0.0550
fushion-mmist
94.42%
1.10%
95.28%
0.16%
95.23%
1 0.15%
0.94 1 0.01
0.95 1 0.00
0.95 0.00
0.3492
0.0054
In one-vs-one scheme however, we observe that the SDP and Moment have comparative performances, both better than PGD. Nevertheless, the optimality gaps of SDP are still significantly larger than the Moment's, for almost all cases.
Similarly, we compare the average runtime to finish 1 fold of training for each model on these real datasets, shown in Table 12 We observe similar trend: the sparse moment relaxation typically requires at least order of magnitude more runtime compared to the other methods.
Table 12: Average runtime to finish fold of training for cach model on real dataset.
onc-vs-rest runtime
onc-vs-onc runtimo
data
PGD
SDP
Moment
PGD
SDP
Moment
football
5.908s
0.581s
20.522s
21.722s
1.119s
17.907s
karate
2.437s
0.501s
1.124s
2.472s
0.525s
1.176s
polbooks
2.205s
0.547s
5.537s
1.748s
0.544s
4.393s
krumsiek
9.639s
3.053s
294.077s
15.728s
1.561s
169.176s
moignard
9. 9.690s
13.000s
368.433s
9.271s
4.826s
293.234s
olsson
7.695s
0.738s
106.584s
10.567s
0.653s
38.487s
paul
34.452s
22.717s
1487.205s
75.878s
3.542s
1313.008s
myeloidprogenitors
6.566s
1.170s
112.341s
10.769s
1.291s
84.402s
cifar
237.019s
2606.295s
9430.7414
fashion-mnist.
285.604s
2840.226s
13128.2200
32

---

Published in Transactions on Machine Learning Research (04/2025)
F Robust Hyperbolic Support Vector Machine
In this section, we propose the robust version of hyperbolic support vector machine without implemention. This is different from the practice of adversarial training that scarches for adversarial samples the fly used in the machine learning communily, such as Weber el. al. (020)). Rather, we predefine an uncertainly structure for data features and attempt to write down the corresponding optimization formulation, which
we call the robust counterpart, as described in Ben-Tal ct al. 22099 Bertsimas & Hertog (2022).
Denole T; as the features observed, or the nominal values, the QCQP can be made robust by introducing an uncertainty set Ue which defines the maximum perturbation around 2; that we think the true data could live in. More prociscly, the formulation is now
(QCQP-robust)
min wER- EER 2
w Gw + +C ECE E1
1=1
s.t. & 0, D. [n]
(28)
(Bi(G))) < V2g. - 1, Vi [nl, Vo Uz.
w Gw > 0
where we add data uncertainty to each classifiability constraint (the second constraint).
However, we could not naively add Euclidean perturbations around क; and postulate that as our uncertainty set, since Euclidean perturbations hyperbolic features highly likely would force it outside of the hyperbolic manifold. Instead, natural generalization to Euclidean noise in the hyperbolic space is to add the noise in the Euclidean tangent space and subsequently 'project' them back onto the hyperbolic space, so that all samples in the uncertainly set stay on the hyperbolic manifold. This is made possible through exponential and logarithmic map.
We demonstrate our robust version of HSVM using a loc example. Define Uz the uncertainty set for data Hd as
U3 (a H x (xog 2), 22), & pp).
(29)
where p >> 0 is the robust parameter, controlling the scale of perturbations are willing to tolerate. In this case, all perturbations are done on the Euclidean tangent space at the origin. Since the geometry of the set is complicated, for small p we may relax the uncertainty set to its first order taylor expansion given by
Üz fo E H = + Jaz, 22 & st, J= = D Dexpo(.)1==
(30)
where Jg is the Jacobian of the exponential map evaluated at x. Suppose E = Irl, where E Rd. To E IR (i.c. partitioned into nogative and positive definite parts), and further suppose e = log, then wo could write down the Jacobian as
7T T sinb(lle la) [
E (d(+))
(coos((fella) sinh([]=](a) |
Ia
||llaa
Then, by adding the uncertainty set to the constraints, we have
(v.(G)))* w < V28, Vo e Un, + ( + +JJ,,2)) & V2g. - 1, 1,1121100 <p
(31)
(bi(Gz;)) (G.,.) < V2g, 1,
(32)
33

---

Published in Transactions on Machine Learning Research (04/2025)
where the last step is rewriting into the robust counterpart (RC). We present the &o norm bounded robust HSVM as follows,
nh w Gw + C E2
min WER
Gw
s.t. G20 [n]
(33)
(wi(Gx:)) (GG::))) (IJ, & V2G. 1, Vi E [n] w² Gw
Note that since Y/ E {-1,1}; we may drop the ys term in the norm and subsoquently write down the SDP relaxation this non-convex QCQP problem and solve it efficiently with
(SDP-Linf)
min WER wER4+1
Tr W) + C Σe &
1=1
CER"
s.t. & 0, Vi E [n]
(34)
(vx)) T w + pll(GJ2,)) " < V26, - 1, 1, [n]
Tr W) >
1 "
W 00
w
For the implementation in MOSEK, linearize the l norm term by introducing extra auxiliary variables, which do not show here. The moment relaxation can be implemented likewise, since this is constraint-wist uncertainty and we preserve the same spansity pattern so that the same sparse moment relaxation applies.
Remark 1. Since take Taylor approrimation to first order, Uz also does not guarantee that all of its elements live striclly on the hyperbolic monvfolld HH. One could seek the second order approcimation to the defining function, which make the robust criterion quadratic form on the uncertainty parameter 2.
Remark 2. Equation
33 arises from loo uncertainty set. We could of course generalize this analysis to other types of uncertainty sets such as l2 uncertainty and ellipsoidal uncertainty, each with different number of auriliary variables introduced in their lineurization.
34


Reviews:
[{"review_id": "LhOdsxIR0m", "reviewer": "Reviewer_dPiK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in this area and have not followed the relevant literature, so my evaluation is somewhat limited.\n\n### Strengths:\n* The paper provides extensive numerical experiments.\n* The paper is generally well-written and is mostly easy to understand.\n* In principle and based on the experiments, for low-dimensional problems, the introduced approach will better handle the non-convexity of the problem and outperform gradient-based approaches.\n\n### Weaknesses:\n* As the authors also mention in the manuscript, a major weakness is that unlike gradient-based algorithms, the relaxations here scale poorly with problem dimension.\n* The relaxations introduced here still lack convergence guarantees similar to gradient-based algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the optimization problem of training a support vector machine on a Lorentz manifold. The authors show that the problem can be formulated as a non-convex quadratically-constrained quadratic programming problem, and apply two known convex relaxations for solving it, namely semi-definite programming (SDP) and moment-sum-of-squares (Moment). Due to the prohibitive complexity of the Moment relaxation, the authors employ the sparsity of the problem and consider a sparse version of the Moment relaxation with smaller complexity. The authors demonstrate via experiments on synthetic and real datasets that these reductions typically perform better than projected gradient descent which was used in prior works.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* I could not follow why we would choose larger $\\kappa$ for the Moment relaxation applied to this problem. Isn't the original polynomial $p(q)$ a second-degree polynomial, for which it would suffice to have $\\kappa = 1$?\n\n* Given that there is some space left in the main text, the authors could add more details in the main text as opposed to the appendix in how the constraints and solutions of the Moment relaxation relate to the constraints and solutions of the original problem, which would help readers who do not have a background in moment optimization.\n\n* The notation in Equations (10) and (11) is a bit misleading. If I understand correctly, $\\langle f_z, A(q)\\rangle$ for some matrix of polynomials $A(q)$ means applying $f_z$ element-wise to $A(q)$, whereas the notation suggests some sort of inner product between $f_z$ and $A(q)$. Perhaps the authors can use a different notation here, while keeping $\\langle f_z, p\\rangle$ between polynomials.\n\n* There are some unreadable characters in the Dataset paragraph of page 7.\n\n* Parentheses are missing for citations that are not part of the sentence such as Mishne et al. (2023) and Weber et al. (2020) in the second paragraph of page 1.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uYNlP1V47W", "reviewer": "Reviewer_dQpE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n•\tThe problem under consideration is interesting and relevant to machine learning over hierarchical datasets.\n\n•\tThe proposed framework is explained in detail.\n\n•\tThe paper includes multiple experiments.\n\n\nCons:\n\n•\tIn the prior work of Chien et al. (2021), the authors do not follow a PGD approach to the best of my understanding. In fact, their main contribution is to provide a reformulation of hyperbolic SVM (albeit in the Poincare ball model of hyperbolic space) into an equivalent convex optimization problem. You may also check [1], a follow up to Chien et al. (2021), for more detailed information. Furthermore, [1] also shows that their proposed approach is highly scalable, and provides much better performance than prior works, some of which may not even converge in many settings considered in [1]. \n\n•\tThere is no performance comparison with Euclidean baselines. Particularly, what is the performance of (a) Euclidean SVM over Euclidean embeddings, (b) Euclidean SVM over hyperbolic embeddings, (c) hyperbolic SVM over Euclidean embeddings. This is important to ascertain what improvements one is getting when applying hyperbolic embedding or/and hyperbolic machine learning. \n\n•\tThere is no discussion on how one can jointly optimize hyperbolic embedding and train a hyperbolic SVM model on the hyperbolic embeddings. I acknowledge that this has been largely ignored in the prior works as well. \n\n•\tThe curvature of hyperbolic space is negative, but not necessarily -1. The framework seems to only apply when curvature is -1.\n\n[1] Pan, Chao, Eli Chien, Puoya Tabaghi, Jianhao Peng, and Olgica Milenkovic. \"Provably accurate and scalable linear classifiers in hyperbolic spaces.\" Knowledge and Information Systems 65, no. 4 (2023): 1817-1850.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper targets the problem of efficient and accurate machine learning in hyperbolic space. In particular, given the embeddings of a dataset in hyperbolic space, the paper targets the problem of machine learning within the hyperbolic space itself, which is in contrast to carrying out machine learning in Euclidean space. The specific ML problem of interest is hyperbolic SVM. Compared to prior works where hyperbolic SVM is addressed using the projected gradient descent (PGD) method, the paper proposes a different optimization approach that seeks to overcome the limitations of PGD in terms of general sensitivity to hyperparameters and initializations. Multiple experiments demonstrate improved performance of the proposed framework over PGD approach for quite a few datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "•\tPlease provide in-depth discussion on the proposed hyperbolic SVM framework in [1]. Specify what the limitations are of [1] and how the current manuscript overcomes those limitations.\n\n•\tProvide thorough experimental comparisons with [1].\n\n•\tGeneralize the paper to when curvature is not -1.\n\n•\tVector notations are not consistent. For example, in Section 3.1, in Hyperbolic Space definition, why italic and non-italic notations are used to represent the same variable? Then, in Tangent Space definition, vectors are represented by non-bold font. Please make all notations consistent. \n\n•\tIn Table 1, in some cases, PGD performs very close to SDP and Moment. In fact, for Gaussian 2, PGD is better than SDP. Furthermore, there are cases where SDP is same as Moment. Please provide intuition behind these results. How can a practitioner ascertain beforehand which method should be used?", "broader_impact_concerns": "The reviewer doesn't have any concern that would require a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FjtQa1qPgH", "reviewer": "Reviewer_ZMJ4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\n- The paper considers a reformulation of hyperbolic soft-margin SVM that can be inputted into standard solvers.\n- The paper is transparently written, discussing various tradeoffs and limitations of the methods.\n- Related work is properly cited.\n\n**Weaknesses**:\n\n- Theoretically not much stronger guarantees than PGD: i) SDP only matches originally formulation when low rank. ii) Sparse-Moment only has guarantees when the flat-extension property is satisfied (which is not the case for the given problem according to the authors)\n- Empirically the advantage over PGD is not clear: i) on one-vs-one the empirical performance is similar (and PGD could be further tuned) ii) The proposed methods are computationally much slower especially for large #datapoints.\n- Empirical evaluation is limited to 2 dimensional examples", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers minimization problems over a hyperbolic space (instead of the usual euclidean space). They specifically consider the soft-margin SVM as in Cho et al. (2019):\n\n- They apply a Taylor expansion to obtain a (non-convex) quadratically-constrained quadratic programming (QCQP). They consider an SDP relaxation (Eq. 8) and a moment-sum-of-squares relaxation (Eq. 13) for which they develop a sparse variant (Eq. 14).\n- They empirically test against projected gradient descent (PGD) on 2-dimensional cases (synthetic Gaussian and tree embeddings, 2d feature embeddings of datasets including CIFAR10/Fashion-MNIST)\n- They observe that Sparse-Moment performs well on one-vs-rest classification split (but is slow due to poor scaling in #datapoints), whereas all methods perform much more similarly (and better) on one-vs-one classification split.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "_Overclaim of empirical contributions_. I suggest either providing a much more extensive comparison, or downtoning the claim in comparison with PGD (specifically the statement \"We observe that they achieve better classification accuracy and F1 score than the existing PGD approach on both simulated and real dataset\" in the discussion):\n\n- All methods performs much more similarly (and better) on the one-vs-one. I suggest focusing on this case and leaving one-vs-rest as an additional experiment, since it is worse for all methods (performancewise for PGD and computationally for SDP and Sparse-Moment).\n- PGD seem to perform better for the largest regularization factor C=10 considered (Table 7). Why not consider a larger factor? It also seem unusual to keep the stepsize fixed regardless of the regularization constant.\n- It is stated that \"Nevertheless, both relaxed models significantly outperform projected gradient descent (PGD) by a wide margin\". Considering that Sparse-Moment is orders of magnitude slower than PGD (Table 11), it seems reasonable to at least tune the stepsize of PGD.\n- All methods perform much better on one-vs-one split. Why not consider one-vs-one for the synthetic examples?\n\nThe reformulations requires more detail in the paper:\n\n- What are the specific relaxations made to obtain the Moment reformulation (eq. 13) and the SDP (eq. 8).\n- Is Eq. 14 an equivalent reformulation of Eq. 13? This seem to be suggest by the statement \"we observe a star-shaped sparsity\".\n- Can Eq. 7 formally be related to the soft-margin in Eq. 6?\n\nVague statements:\n\n- It is unclear what \"Moment\" in the experiments specifically refers to. Does \"sparse moment-sum-of-squares relaxations (Moment)\" in the experiments refers to Eq. 14?\n- \"However, moment-sum-of-squares relaxation does not scale with the data size due to the combinatorial factors\". From the experiments Sparse-Moment do no scale well in datasize either (Table 11). If would be helpful if the authors could compare the computational complexity of Sparse-Moment and moment-sum-of-squares.\n- \"their hyperbolic embeddings obtained through standard hyperbolic embedding procedure\". It would be helpful if the authors elaborate on the procedure to make the paper self-contained.\n- \"Its exponential volume growth with respect to radius motivates representation learning of hierarchical data using the hyperbolic space\". Could the authors elaborate?\n\nTypos:\n\n- datasetsâĂŤfootball, âĂŤto", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes algorithms for solving the SVM problem in hyperbolic space by considering convex relaxations based on semi-definite programming and sum-of-squares. The authors then compare the proposed approach to previously studied approaches, mainly projected gradient descent.

The reviewers appreciated the problem, the proposed algorithms, and the conducted empirical analysis. Therefore, the decision is leaning towards acceptance. Nevertheless, reviewers expressed concerns on the empirical study, particularly regarding the limited comparisons with other baselines and restriction to low-dimensional datasets.

Given that the authors did not update the manuscript during the rebuttal, I ask that the authors address the requested changes in a revised manuscript. The revision should also include both a clear discussion and a rigorous experimental study of when the proposed methods perform better or worse than an appropriately tuned PGD baseline.
Decision: Accept (poster)