Snacks: a fast large-scale kernel SVM solver

• URL: http://arxiv.org/abs/2304.07983v1
• Date: Mon, 17 Apr 2023 04:19:20 GMT
• Title: Snacks: a fast large-scale kernel SVM solver
• Authors: Sofiane Tanji and Andrea Della Vecchia and Fran\c{c}ois Glineur and Silvia Villa
• Abstract summary: Snacks is a new large-scale solver for Kernel Support Vector Machines. Snacks relies on a Nystr"om approximation of the kernel matrix and an accelerated variant of the subgradient method.
• Score: 0.8602553195689513
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel methods provide a powerful framework for non parametric learning. They are based on kernel functions and allow learning in a rich functional space while applying linear statistical learning tools, such as Ridge Regression or Support Vector Machines. However, standard kernel methods suffer from a quadratic time and memory complexity in the number of data points and thus have limited applications in large-scale learning. In this paper, we propose Snacks, a new large-scale solver for Kernel Support Vector Machines. Specifically, Snacks relies on a Nystr\"om approximation of the kernel matrix and an accelerated variant of the stochastic subgradient method. We demonstrate formally through a detailed empirical evaluation, that it competes with other SVM solvers on a variety of benchmark datasets.

Related papers

• Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives [0.5735035463793009]
  We present a technique based on the non-equispaced fast Fourier transform (NFFT) with rigorous error analysis. We show that this approach is also well suited to allow the approximation of the matrix that arises when the kernel is differentiated. We illustrate the performance of the additive kernel scheme with fast matrix vector products on a number of data sets.
  arXiv  Detail & Related papers  (2024-04-26T11:50:16Z)
• A new trigonometric kernel function for SVM [0.0]
  We introduce a new trigonometric kernel function containing one parameter for the machine learning algorithms. We also conduct an empirical evaluation on the kernel-SVM and kernel-SVR methods and demonstrate its strong performance.
  arXiv  Detail & Related papers  (2022-10-16T17:10:52Z)
• Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication [0.0]
  kernel matrix is typically dense and large-scale. Depending on the dimension of the feature space even the computation of all of its entries in reasonable time becomes a challenging task. We propose the use of an ANOVA kernel, where we construct several kernels based on lower-dimensional feature spaces for which we provide fast algorithms realizing the matrix-vector products. Based on a feature grouping approach, we then show how the fast matrix-vector products can be embedded into a learning method choosing kernel ridge regression and the preconditioned conjugate gradient solver.
  arXiv  Detail & Related papers  (2021-11-19T10:29:39Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  kernel is especially important as other kernels can often be approximated by the kernel via a Taylor series expansion. Recent techniques in sketching reduce the dependence in the running time on the degree oblivious $q$ of the kernel. We give a new sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term.
  arXiv  Detail & Related papers  (2021-08-21T02:14:55Z)
• Kernel Continual Learning [117.79080100313722]
  kernel continual learning is a simple but effective variant of continual learning to tackle catastrophic forgetting. episodic memory unit stores a subset of samples for each task to learn task-specific classifiers based on kernel ridge regression. variational random features to learn a data-driven kernel for each task.
  arXiv  Detail & Related papers  (2021-07-12T22:09:30Z)
• Kernel Identification Through Transformers [54.3795894579111]
  Kernel selection plays a central role in determining the performance of Gaussian Process (GP) models. This work addresses the challenge of constructing custom kernel functions for high-dimensional GP regression models. We introduce a novel approach named KITT: Kernel Identification Through Transformers.
  arXiv  Detail & Related papers  (2021-06-15T14:32:38Z)
• A Semismooth-Newton's-Method-Based Linearization and Approximation Approach for Kernel Support Vector Machines [1.177306187948666]
  Support Vector Machines (SVMs) are among the most popular and the best performing classification algorithms. In this paper, we propose a semismooth Newton's method based linearization approximation approach for kernel SVMs. The advantage of the proposed approach is that it maintains low computational cost and keeps a fast convergence rate.
  arXiv  Detail & Related papers  (2020-07-21T07:44:21Z)
• MKLpy: a python-based framework for Multiple Kernel Learning [4.670305538969914]
  We introduce MKLpy, a python-based framework for Multiple Kernel Learning. The library provides Multiple Kernel Learning algorithms for classification tasks, mechanisms to compute kernel functions for different data types, and evaluation strategies.
  arXiv  Detail & Related papers  (2020-07-20T10:10:13Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• Learning Deep Kernels for Non-Parametric Two-Sample Tests [50.92621794426821]
  We propose a class of kernel-based two-sample tests, which aim to determine whether two sets of samples are drawn from the same distribution. Our tests are constructed from kernels parameterized by deep neural nets, trained to maximize test power.
  arXiv  Detail & Related papers  (2020-02-21T03:54:23Z)
• On Coresets for Support Vector Machines [61.928187390362176]
  A coreset is a small, representative subset of the original data points. We show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings.
  arXiv  Detail & Related papers  (2020-02-15T23:25:12Z)

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.