A Case of Exponential Convergence Rates for SVM

• URL: http://arxiv.org/abs/2205.10055v2
• Date: Mon, 22 May 2023 23:57:23 GMT
• Title: A Case of Exponential Convergence Rates for SVM
• Abstract summary: Generalization guarantees of classification have historically been offered by Vapnik-Chervonenkis theory. We show that SVM can exhibit exponential convergence rates even without assuming the hard Tsybakov margin condition.
• Score: 1.52292571922932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classification is often the first problem described in introductory machine learning classes. Generalization guarantees of classification have historically been offered by Vapnik-Chervonenkis theory. Yet those guarantees are based on intractable algorithms, which has led to the theory of surrogate methods in classification. Guarantees offered by surrogate methods are based on calibration inequalities, which have been shown to be highly sub-optimal under some margin conditions, failing short to capture exponential convergence phenomena. Those "super" fast rates are becoming to be well understood for smooth surrogates, but the picture remains blurry for non-smooth losses such as the hinge loss, associated with the renowned support vector machines. In this paper, we present a simple mechanism to obtain fast convergence rates and we investigate its usage for SVM. In particular, we show that SVM can exhibit exponential convergence rates even without assuming the hard Tsybakov margin condition.

Related papers

• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness [50.78508362183774]
  Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance.<n>Most require the Lipschitz condition, which is often not met in common machine learning schemes.
  arXiv  Detail & Related papers  (2025-07-11T15:36:48Z)
• Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models [59.47572583027685]
  We provide the first finite-time error bounds and convergence rate analysis for discrete diffusion models using absorbing rate matrices.<n>We establish the first convergence guarantees for both the $tau$-leaping and uniformization samplers under absorbing rate matrices.<n>Under suitable assumptions, we provide convergence guarantees without early stopping.
  arXiv  Detail & Related papers  (2025-06-02T23:14:35Z)
• Kernel Support Vector Machine Classifiers with the $\ell_0$-Norm Hinge Loss [3.007949058551534]
  Support Vector Machine (SVM) has been one of the most successful machine learning techniques for binary classification problems. This paper is concentrated on vectors with hinge loss (referred as $ell$-KSVM), which is a composite function of hinge loss and $ell_$norm. Experiments on the synthetic and real datasets are illuminated to show that $ell_$-KSVM can achieve comparable accuracy compared with the standard KSVM.
  arXiv  Detail & Related papers  (2023-06-24T14:52:44Z)
• Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums [7.778461949427662]
  Byzantine resilience emerged as a prominent topic within the distributed machine learning community. We present emphRESAM (RESilient Averaging of Momentums), a unified framework that makes it simple to establish optimal Byzantine resilience.
  arXiv  Detail & Related papers  (2022-05-24T16:14:50Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• Multiclass learning with margin: exponential rates with no bias-variance trade-off [16.438523317718694]
  We study the behavior of error bounds for multiclass classification under suitable margin conditions. Different convergence rates can be obtained in correspondence of different margin assumptions.
  arXiv  Detail & Related papers  (2022-02-03T18:57:27Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Conditional Bures Metric for Domain Adaptation [14.528711361447712]
  Unsupervised domain adaptation (UDA) has attracted widespread attention in recent years. Previous UDA methods assume the marginal distributions of different domains are shifted while ignoring the discriminant information in the label distributions. In this work, we focus on the conditional distribution shift problem which is of great concern to current conditional invariant models.
  arXiv  Detail & Related papers  (2021-07-31T18:06:31Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Constrained Classification and Policy Learning [0.0]
  We study consistency of surrogate loss procedures under a constrained set of classifiers. We show that hinge losses are the only surrogate losses that preserve consistency in second-best scenarios.
  arXiv  Detail & Related papers  (2021-06-24T10:43:00Z)
• Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization [120.31448970413298]
  We extend the theory of Tikhonov regularization to generalized self concordant loss functions. We show that fast and optimal rates can be achieved for GSC by using the iterated Tikhonov regularization scheme.
  arXiv  Detail & Related papers  (2021-06-16T15:25:41Z)
• Distribution-free uncertainty quantification for classification under label shift [105.27463615756733]
  We focus on uncertainty quantification (UQ) for classification problems via two avenues. We first argue that label shift hurts UQ, by showing degradation in coverage and calibration. We examine these techniques theoretically in a distribution-free framework and demonstrate their excellent practical performance.
  arXiv  Detail & Related papers  (2021-03-04T20:51:03Z)
• Super fast rates in structured prediction [88.99819200562784]
  We show how we can leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in $n-1/4$ to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem.
  arXiv  Detail & Related papers  (2021-02-01T10:50:04Z)

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.