On the proliferation of support vectors in high dimensions

• URL: http://arxiv.org/abs/2009.10670v2
• Date: Tue, 14 Jun 2022 00:07:47 GMT
• Title: On the proliferation of support vectors in high dimensions
• Authors: Daniel Hsu, Vidya Muthukumar, Ji Xu
• Abstract summary: The support vector machine (SVM) is a well-established classification method whose name refers to the particular training examples, called support vectors. Recent research has shown that in sufficiently high-dimensional linear classification problems, the SVM can generalize well despite a proliferation of support vectors.
• Score: 24.63581896788434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The support vector machine (SVM) is a well-established classification method whose name refers to the particular training examples, called support vectors, that determine the maximum margin separating hyperplane. The SVM classifier is known to enjoy good generalization properties when the number of support vectors is small compared to the number of training examples. However, recent research has shown that in sufficiently high-dimensional linear classification problems, the SVM can generalize well despite a proliferation of support vectors where all training examples are support vectors. In this paper, we identify new deterministic equivalences for this phenomenon of support vector proliferation, and use them to (1) substantially broaden the conditions under which the phenomenon occurs in high-dimensional settings, and (2) prove a nearly matching converse result.

Related papers

• Tverberg's theorem and multi-class support vector machines [0.0]
  We show how we can design new models of multi-class support vector machines (SVMs) These protocols require fewer conditions to classify sets of points, and can be computed using existing binary SVM algorithms in higher-dimensional spaces. We give a new simple proof of a geometric characterization of support vectors for largest margin SVMs by Veelaert.
  arXiv  Detail & Related papers  (2024-04-25T16:37:58Z)
• HyperVQ: MLR-based Vector Quantization in Hyperbolic Space [56.4245885674567]
  We study the use of hyperbolic spaces for vector quantization (HyperVQ) We show that hyperVQ performs comparably in reconstruction and generative tasks while outperforming VQ in discriminative tasks and learning a highly disentangled latent space.
  arXiv  Detail & Related papers  (2024-03-18T03:17:08Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• Handling Imbalanced Classification Problems With Support Vector Machines via Evolutionary Bilevel Optimization [73.17488635491262]
  Support vector machines (SVMs) are popular learning algorithms to deal with binary classification problems. This article introduces EBCS-SVM: evolutionary bilevel cost-sensitive SVMs.
  arXiv  Detail & Related papers  (2022-04-21T16:08:44Z)
• Max-Margin Contrastive Learning [120.32963353348674]
  We present max-margin contrastive learning (MMCL) for unsupervised representation learning. Our approach selects negatives as the sparse support vectors obtained via a quadratic optimization problem. We validate our approach on standard vision benchmark datasets, demonstrating better performance in unsupervised representation learning.
  arXiv  Detail & Related papers  (2021-12-21T18:56:54Z)
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements [48.556633593447465]
  Recovery of support of a sparse vector from simple measurements is a widely studied problem. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers. We provide algorithms that use a number of measurements in $k, log n$ and quasi-polynomial in $ell$ to recover the support of all the unknown vectors in the mixture.
  arXiv  Detail & Related papers  (2021-06-10T17:48:13Z)
• Support vector machines and linear regression coincide with very high-dimensional features [5.878391874426428]
  We show a phenomenon where every training example used to fit an SVM becomes a support vector. First, we prove a super-linear lower bound on the dimension (in terms of sample size) required for support vector proliferation in independent feature models. We also identify a sharp phase transition in Gaussian feature models, bound the width of this transition, and give experimental support for its universality.
  arXiv  Detail & Related papers  (2021-05-28T20:06:21Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)
• Support vector machines and Radon's theorem [0.5027571997864707]
  A support vector machine (SVM) is an algorithm that finds a hyperplane which optimally separates labeled data points in $mathbbRn$ into positive and negative classes. We connect the possible configurations of support vectors to Radon's theorem, which provides guarantees for when a set of points can be divided into two classes.
  arXiv  Detail & Related papers  (2020-11-01T19:57:46Z)
• Near-Tight Margin-Based Generalization Bounds for Support Vector Machines [15.447966950703952]
  Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In this paper, we revisit and improve the classic generalization bounds in terms of margins. We complement our new generalization bound by a nearly matching lower bound, thus almost settling the generalization performance of SVMs in terms of margins.
  arXiv  Detail & Related papers  (2020-06-03T11:22:37Z)
• A Unified Framework for Multiclass and Multilabel Support Vector Machines [6.425654442936364]
  We propose a straightforward extension to the SVM to cope with multiclass and multilabel classification problems. Our framework deviates from the conventional soft margin SVM framework with its direct oppositional structure. Results demonstrate a competitive classifier for both multiclass and multilabel classification problems.
  arXiv  Detail & Related papers  (2020-03-25T03:08:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.