Near-Tight Margin-Based Generalization Bounds for Support Vector Machines

• URL: http://arxiv.org/abs/2006.02175v1
• Date: Wed, 3 Jun 2020 11:22:37 GMT
• Title: Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
• Authors: Allan Gr{\o}nlund, Lior Kamma, Kasper Green Larsen
• Abstract summary: 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.
• Score: 15.447966950703952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of data using the largest possible margin to the data. The focus on maximizing the margin has been well motivated through numerous generalization bounds. In this paper, we revisit and improve the classic generalization bounds in terms of margins. Furthermore, we complement our new generalization bound by a nearly matching lower bound, thus almost settling the generalization performance of SVMs in terms of margins.

Related papers

• New Equivalences Between Interpolation and SVMs: Kernels and Structured Features [22.231455330003328]
  We present a new and flexible analysis framework for proving SVP in an arbitrary kernel reproducing Hilbert space with a flexible class of generative models for the labels. We show that SVP occurs in many interesting settings not covered by prior work, and we leverage these results to prove novel generalization results for kernel SVM classification.
  arXiv  Detail & Related papers  (2023-05-03T17:52:40Z)
• Margin Optimal Classification Trees [0.0]
  We present a novel mixed-integer formulation for the Optimal Classification Tree ( OCT) problem. Our model, denoted as Margin Optimal Classification Tree (MARGOT), exploits the generalization capabilities of Support Vector Machines for binary classification. To enhance the interpretability of our approach, we analyse two alternative versions of MARGOT, which include feature selection constraints inducing local sparsity of the hyperplanes.
  arXiv  Detail & Related papers  (2022-10-19T14:08:56Z)
• Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence [55.26547500184405]
  Existing tools rely on em uniform convergence em (UC), which guarantees that the test loss will be close to the training loss, uniformly over a class of candidate models. Nagarajan and Kolter show that in certain simple linear and neural-network settings, any uniform convergence bound will be vacuous, leaving open the question of how to prove generalization in settings where UC fails. We prove a new type of margin bound showing that above a certain signal-to-noise threshold, any near-max-margin will achieve almost no test loss in these two settings.
  arXiv  Detail & Related papers  (2022-06-16T02:46:26Z)
• 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)
• Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion [3.157455635899373]
  We significantly improve the generalization bounds for VC classes by using two main ideas. First, we consider the hypergeometric inversion tail to obtain a very tight non-uniform distribution-independent risk upper bound for VC classes. Second, we optimize the ghost sample trick to obtain a further non-negligible gain.
  arXiv  Detail & Related papers  (2021-10-29T19:50:34Z)
• Measuring Generalization with Optimal Transport [111.29415509046886]
  We develop margin-based generalization bounds, where the margins are normalized with optimal transport costs. Our bounds robustly predict the generalization error, given training data and network parameters, on large scale datasets.
  arXiv  Detail & Related papers  (2021-06-07T03:04:59Z)
• Semi-Supervised Domain Generalization with Stochastic StyleMatch [90.98288822165482]
  In real-world applications, we might have only a few labels available from each source domain due to high annotation cost. In this work, we investigate semi-supervised domain generalization, a more realistic and practical setting. Our proposed approach, StyleMatch, is inspired by FixMatch, a state-of-the-art semi-supervised learning method based on pseudo-labeling.
  arXiv  Detail & Related papers  (2021-06-01T16:00:08Z)
• Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
  Variational autoencoders (VAE) are a powerful and widely-used class of generative models. We introduce a new constrained objective based on the Cauchy-Schwarz divergence, which can be computed analytically for GMMs. Our objective improves upon variational auto-encoding models in density estimation, unsupervised clustering, semi-supervised learning, and face analysis.
  arXiv  Detail & Related papers  (2021-01-06T17:36:26Z)
• On the proliferation of support vectors in high dimensions [24.63581896788434]
  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.
  arXiv  Detail & Related papers  (2020-09-22T16:45:06Z)
• 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.