A Safe Screening Rule with Bi-level Optimization of $\nu$ Support Vector Machine

• URL: http://arxiv.org/abs/2403.01769v1
• Date: Mon, 4 Mar 2024 06:55:57 GMT
• Title: A Safe Screening Rule with Bi-level Optimization of $\nu$ Support Vector Machine
• Authors: Zhiji Yang, Wanyi Chen, Huan Zhang, Yitian Xu, Lei Shi, Jianhua Zhao
• Abstract summary: We propose a safe screening rule with bi-level optimization for $nu$-SVM. Our SRBO-$nu$-SVM is strictly deduced by integrating the Karush-Kuhn-Tucker conditions. We also develop an efficient dual coordinate descent method (DCDM) to further improve computational speed.
• Score: 15.096652880354199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Support vector machine (SVM) has achieved many successes in machine learning, especially for a small sample problem. As a famous extension of the traditional SVM, the $\nu$ support vector machine ($\nu$-SVM) has shown outstanding performance due to its great model interpretability. However, it still faces challenges in training overhead for large-scale problems. To address this issue, we propose a safe screening rule with bi-level optimization for $\nu$-SVM (SRBO-$\nu$-SVM) which can screen out inactive samples before training and reduce the computational cost without sacrificing the prediction accuracy. Our SRBO-$\nu$-SVM is strictly deduced by integrating the Karush-Kuhn-Tucker (KKT) conditions, the variational inequalities of convex problems and the $\nu$-property. Furthermore, we develop an efficient dual coordinate descent method (DCDM) to further improve computational speed. Finally, a unified framework for SRBO is proposed to accelerate many SVM-type models, and it is successfully applied to one-class SVM. Experimental results on 6 artificial data sets and 30 benchmark data sets have verified the effectiveness and safety of our proposed methods in supervised and unsupervised tasks.

Related papers

• $p$SVM: Soft-margin SVMs with $p$-norm Hinge Loss [0.0]
  Support Vector Machines (SVMs) based on hinge loss have been extensively discussed and applied to various binary classification tasks. In this paper, we explore the properties, performance, and training algorithms of $p$SVMs.
  arXiv  Detail & Related papers  (2024-08-19T11:30:00Z)
• Sparse Learning and Class Probability Estimation with Weighted Support Vector Machines [1.3597551064547502]
  weighted Support Vector Machines (wSVMs) have shown great values in robustly predicting the class probability and classification for various problems with high accuracy. We propose novel wSVMs frameworks that incorporate automatic variable selection with accurate probability estimation for sparse learning problems. The proposed wSVMs-based sparse learning methods have wide applications and can be further extended to $K$-class problems through ensemble learning.
  arXiv  Detail & Related papers  (2023-12-17T06:12:33Z)
• Optimization meets Machine Learning: An Exact Algorithm for Semi-Supervised Support Vector Machines [0.9831489366502302]
  Support vector machines (SVMs) are well-studied supervised learning models for binary classification. We present a new branch approach for S3VMs using semidefinite programming (SDP) relaxations. SDP relaxation provides bounds significantly stronger than the ones available in the literature.
  arXiv  Detail & Related papers  (2023-12-15T13:44:54Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Majorization-Minimization for sparse SVMs [46.99165837639182]
  Support Vector Machines (SVMs) were introduced for performing binary classification tasks, under a supervised framework, several decades ago. They often outperform other supervised methods and remain one of the most popular approaches in the machine learning arena. In this work, we investigate the training of SVMs through a smooth sparse-promoting-regularized squared hinge loss minimization.
  arXiv  Detail & Related papers  (2023-08-31T17:03:16Z)
• Evaluating robustness of support vector machines with the Lagrangian dual approach [6.868150350359336]
  We propose a method to improve the verification performance for vector machines (SVMs) with nonlinear kernels. We evaluate the adversarial robustness of SVMs with linear and nonlinear kernels on the MNIST and Fashion-MNIST datasets. The experimental results show that the percentage of provable robustness obtained by our method on the test set is better than that of the state-of-the-art.
  arXiv  Detail & Related papers  (2023-06-05T07:15:54Z)
• High-Dimensional Penalized Bernstein Support Vector Machines [0.0]
  Non-differentiability of the SVM hinge loss function can lead to computational difficulties in high dimensional settings. We propose two efficient algorithms for computing the solution of the penalized BernSVM. Our bound holds with high probability and achieves a rate of order $sqrtslog(p)/n$, where $s$ is the number of active features.
  arXiv  Detail & Related papers  (2023-03-16T03:48:29Z)
• 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)
• 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)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• 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.