New Equivalences Between Interpolation and SVMs: Kernels and Structured Features

• URL: http://arxiv.org/abs/2305.02304v1
• Date: Wed, 3 May 2023 17:52:40 GMT
• Title: New Equivalences Between Interpolation and SVMs: Kernels and Structured Features
• Authors: Chiraag Kaushik, Andrew D. McRae, Mark A. Davenport, Vidya Muthukumar
• Abstract summary: 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.
• Score: 22.231455330003328
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The support vector machine (SVM) is a supervised learning algorithm that finds a maximum-margin linear classifier, often after mapping the data to a high-dimensional feature space via the kernel trick. Recent work has demonstrated that in certain sufficiently overparameterized settings, the SVM decision function coincides exactly with the minimum-norm label interpolant. This phenomenon of support vector proliferation (SVP) is especially interesting because it allows us to understand SVM performance by leveraging recent analyses of harmless interpolation in linear and kernel models. However, previous work on SVP has made restrictive assumptions on the data/feature distribution and spectrum. In this paper, we present a new and flexible analysis framework for proving SVP in an arbitrary reproducing kernel Hilbert space with a flexible class of generative models for the labels. We present conditions for SVP for features in the families of general bounded orthonormal systems (e.g. Fourier features) and independent sub-Gaussian features. In both cases, 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.

Related papers

• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• 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)
• Temporal support vectors for spiking neuronal networks [0.0]
  We introduce a novel extension of the static Support Vector Machine (T-SVM) We show that T-SVM and its kernel extensions generate robust synaptic weight vectors in spiking neurons. We propose T-SVM with nonlinear kernels as a new model of the computational role of the nonlinearities and extensive morphologies of neuronal dendritic trees.
  arXiv  Detail & Related papers  (2022-05-28T23:47:15Z)
• Hybrid Random Features [60.116392415715275]
  We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) HRFs automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest.
  arXiv  Detail & Related papers  (2021-10-08T20:22:59Z)
• Computing on Functions Using Randomized Vector Representations [4.066849397181077]
  We call this new function encoding and computing framework Vector Function Architecture (VFA) Our analyses and results suggest that VFAs constitute a powerful new framework for representing and manipulating functions in distributed neural systems.
  arXiv  Detail & Related papers  (2021-09-08T04:39:48Z)
• 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)
• Kernel learning approaches for summarising and combining posterior similarity matrices [68.8204255655161]
  We build upon the notion of the posterior similarity matrix (PSM) in order to suggest new approaches for summarising the output of MCMC algorithms for Bayesian clustering models. A key contribution of our work is the observation that PSMs are positive semi-definite, and hence can be used to define probabilistically-motivated kernel matrices.
  arXiv  Detail & Related papers  (2020-09-27T14:16:14Z)
• Behavioral analysis of support vector machine classifier with Gaussian kernel and imbalanced data [6.028247638616058]
  The behavior of the SVM classification model is analyzed when these parameters take different values with balanced and imbalanced data. From this analysis, we proposed a novel search algorithm. In our algorithm, we search for the optimal SVM parameters into two one-dimensional spaces instead of searching into one two-dimensional space.
  arXiv  Detail & Related papers  (2020-07-09T19:28:25Z)
• A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time [0.2855485723554975]
  We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning. Based on the classical SVM-perf algorithm of Joachims, our algorithm has a running time which scales linearly in the number of training examples.
  arXiv  Detail & Related papers  (2020-06-18T06:25:45Z)
• Bayesian Sparse Factor Analysis with Kernelized Observations [67.60224656603823]
  Multi-view problems can be faced with latent variable models. High-dimensionality and non-linear issues are traditionally handled by kernel methods. We propose merging both approaches into single model.
  arXiv  Detail & Related papers  (2020-06-01T14:25:38Z)
• An End-to-End Graph Convolutional Kernel Support Vector Machine [0.0]
  A kernel-based support vector machine (SVM) for graph classification is proposed. The proposed model is trained in a supervised end-to-end manner. Experimental results demonstrate that the proposed model outperforms existing deep learning baseline models on a number of datasets.
  arXiv  Detail & Related papers  (2020-02-29T09:57:42Z)

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.