Approximate Hard-Margin SVM (Support Vector Machines (SVM))
Jump to navigation
Jump to search
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 |