Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM

FROM: Bichromatic Hamming Close Pair TO: Approximate Hard-Margin SVM

Implications

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.

Year

2017

Reference

Backurs, A., Indyk, P., & Schmidt, L. (2017). On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. Advances in Neural Information Processing Systems, 30.

https://proceedings.neurips.cc/paper/2017/file/635440afdfc39fe37995fed127d7df4f-Paper.pdf