Local Duality for Sparse Support Vector Machines.

Area of Science:

• Machine Learning
• Optimization Theory
• Computational Statistics

Background:

• Sparse Support Vector Machines (SSVMs) are increasingly used due to cardinality minimization in optimization.
• Existing SSVM derivations often lack theoretical justification, particularly when adding ℓ0-norm to convex SVM dual problems.
• Empirical advantages of SSVMs over convex Support Vector Machines (SVMs) necessitate a theoretical framework.

Purpose of the Study:

• To develop a local duality theory for SSVM formulations.
• To establish the theoretical relationship between SSVMs and other SVM variants like hinge-loss SVM (hSVM) and ramp-loss SVM (rSVM).
• To provide theoretical justification for the empirical success of SSVMs.

Main Methods:

• Development of a local duality theory for SSVMs.
• Proof that the derived SSVM is the dual problem of the 0/1-loss SVM.
• Analysis of the relationship between SSVM local solutions and hyperparameters of hSVM and rSVM.

Main Results:

• The linear representer theorem is proven to hold for local solutions of the derived SSVM and 0/1-loss SVM.
• SSVM local solutions offer guidance for selecting hSVM and rSVM hyperparameters.
• Under specific conditions, global solutions of hSVM converge to local solutions of 0/1-loss SVM, and local minimizers of 0/1-loss SVM are also local minimizers of rSVM.

Conclusions:

• The study provides the first theoretical justification for SSVMs derived via ℓ0-norm regularization.
• The established local duality explains the superior performance of SSVMs compared to hSVM and rSVM in empirical studies.
• Numerical tests confirm the potential advantages of SSVMs, especially when utilizing the proposed locally well-behaved solutions.