Approximate Hard-Margin SVM (Support Vector Machines (SVM))
Revision as of 10:30, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate Hard-Margin SVM (Support Vector Machines (SVM))}} == Description == A (primal) hard-margin SVM is an optimization problem of the following form: $\min\limits_{\alpha_1,\ldots,\alpha_n\geq 0} \frac{1}{2} \sum \limits_{i,j = 1}^n \alpha_i \alpha_j y_i y_j k(x_i, x_j)$ subject to $y_i f(x_i) \geq 1, i = 1, \ldots, n$ where $f(x) := \sum_{i=1}^n \alpha_i y_i k(x_i, x)$ == Parameters == No parameters found. == Table of Algorithms == Curre...")
Description
A (primal) hard-margin SVM is an optimization problem of the following form:
$\min\limits_{\alpha_1,\ldots,\alpha_n\geq 0} \frac{1}{2} \sum \limits_{i,j = 1}^n \alpha_i \alpha_j y_i y_j k(x_i, x_j)$
subject to $y_i f(x_i) \geq 1, i = 1, \ldots, n$ where $f(x) := \sum_{i=1}^n \alpha_i y_i k(x_i, x)$
Parameters
No parameters found.
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Bichromatic Hamming Close Pair | assume: SETH then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. |
2017 | https://proceedings.neurips.cc/paper/2017/file/635440afdfc39fe37995fed127d7df4f-Paper.pdf | link |