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


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


Experiments
4.1 Synthetic Dataset
4.2 Real Dataset


Discussions, Acknowledgements, and References Related Works Related Works Related Works Convex Relaxation Techniques for Hyperbolic SVMs
3.1 Preliminaries
3.2 Original Formulation of the HSVM
3.3 Semidefinite Formulation
3.4 Moment-Sum-of-Squares Relaxation Convex Relaxation Techniques for Hyperbolic SVMs 3.1 Preliminaries 3.1 Preliminaries 3.2 Original Formulation of the HSVM 3.2 Original Formulation of the HSVM 3.3 Semidefinite Formulation 3.3 Semidefinite Formulation 3.4 Moment-Sum-of-Squares Relaxation 3.4 Moment-Sum-of-Squares Relaxation Experiments
4.1 Synthetic Dataset
4.2 Real Dataset Experiments Experiments 4.1 Synthetic Dataset 4.1 Synthetic Dataset 4.2 Real Dataset 4.2 Real Dataset Discussions, Acknowledgements, and References Discussions, Acknowledgements, and References Discussions, Acknowledgements, and References A. Proofs A. Proofs B. Solution Extraction in Relaxed Formulation B. Solution Extraction in Relaxed Formulation C. On Moment Sum-of-Squares Relaxation Hierarchy C. On Moment Sum-of-Squares Relaxation Hierarchy D. Platt Scaling [31] D. Platt Scaling [31] E. Detailed Experimental Results E. Detailed Experimental Results F. Robust Hyperbolic Support Vector Machine F. Robust Hyperbolic Support Vector Machine C On Moment Sum-of-Squares Relaxation Hierarchy In this section, we provide necessary background on moment-sum-of-squares hierarchy. We start by considering a general Polynomial Optimization Problem (POP) and introduce the sparse version. This section borrows substantially from the course note [4]. C.1 Polynomial Optimization and Dual Cones Polynomial optimization problem (POP) in the most generic form can be presented as where 𝑝(𝑥) is our polynomial objective and ℎ𝑖(𝑥), 𝑔𝑖(𝑥) are our polynomial equality and inequality constraints respectively. However, in general, solving such POP to global optimality is NP-hard [9, 29]. To address this challenge, we leverage methods from algebraic geometry [9, 21], 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 of some other polynomials, and we define Σ[𝑥] to be the collection of SOS polynomials. More formally, we have sum-of-squares (SOS) polynomials where R[𝑥] denotes the polynomial ring over R. Next, we recall the definitions of quadratic module and its dual. Given a set of polynomials g = [𝑔1, 𝑔2, ..., 𝑔𝑙], the quadratic module generated by g is defined as quadratic module g and its degree 2𝑑-truncation is defined as, Similarly, given a set of polynomials h = [ℎ1, ℎ2, ..., ℎ𝑚], the ideal generated by h is defined as, and its degree 2𝑑-truncation is defined as, where 𝜆𝑖 ’s are also called polynomial multipliers. Interestingly, it is shown that we can perfectly characterize the dual of the sum of ideal and quadratic module, (Ideal[h]2𝑑 + Qmodule[g]2𝑑) ∗ = 𝒵[ℎ]2𝑑 ∩ ℳ[𝑔]2𝑑 , With these notions setup, we can reformulate the POP above into the following SOS program for arbitrary 𝜅 ∈ N as the relaxataion order, C.2 Sparse Polynomial Optimization Definition 1. Correlated Sparsity for an objective 𝑝 ∈ R[𝑥] and associated set of constraints means Definition 1. Correlated Sparsity Correlated Sparsity for an objective and associated set of constraints means With correlated sparsity and data regularity (Putinar’s Positivestellentz outlined in Nie [9]), we 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 is our case for HSVM, the sparse POP for our problem reads as and we could derive its dual accordingly and present the SDP form for implementation in Equation (14). Authors:
(1) Sheng Yang, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (shengyang@g.harvard.edu);
(2) Peihan Liu, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (peihanliu@fas.harvard.edu);
(3) Cengiz Pehlevan, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, Center for Brain Science, Harvard University, Cambridge, MA, and Kempner Institute for the Study of Natural and Artificial Intelligence, Harvard University, Cambridge, MA (cpehlevan@seas.harvard.edu). Authors: Authors: (1) Sheng Yang, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (shengyang@g.harvard.edu); (2) Peihan Liu, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA (peihanliu@fas.harvard.edu); (3) Cengiz Pehlevan, John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, Center for Brain Science, Harvard University, Cambridge, MA, and Kempner Institute for the Study of Natural and Artificial Intelligence, Harvard University, Cambridge, MA (cpehlevan@seas.harvard.edu). This paper is available on arxiv under CC by-SA 4.0 Deed (Attribution-Sharealike 4.0 International) license. This paper is available on arxiv under CC by-SA 4.0 Deed (Attribution-Sharealike 4.0 International) license. available on arxiv available on arxiv [4] Chapter 5 Moment Relaxation: https://hankyang.seas.harvard.edu/Semidefinite/Moment.html

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

Moment

Dual Cones & Quadratic Modules: The Geometry of Global Optimality

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

Hyperbolic SVM vs. Euclidean SVM: Comparing Optimization Challenges

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

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

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

10 Ways AI Has Changed Our Lives

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

Hyperbolic SVM vs. Euclidean SVM: Comparing Optimization Challenges

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

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

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

10 Ways AI Has Changed Our Lives

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps