# Using SVM when kernel is simple and sample size is large

Consider SVM classification: $y_i \in \{+1,-1\}$ are labels, $\mathbf{x}_i$ are covariates ($i=1\ldots N$).

Let $K(\cdot,\cdot)$ be the kernel function, whose corresponding feature mapping is $h(\mathbf{x})$ with dimension $p$.

SVM would provide solution as $\hat{f}(\mathbf{x})= \sum_{i=1}^N{\alpha_i K(\mathbf{x}_i,\mathbf{x})}+b$. With $\mathbf{\alpha} \ \mbox{and}\ b$, there are in total $N+1$ parameter to be optimized.

Now consider the case where $N$ is very big, but the kernel is simple (eg. low order polynomial) leading to comparatively small $p$. Would it be simpler if we just forget about the kernel and optimize:

$$\min_{\beta,b} \sum_{i=1}^N{ \big( 1-y_i(h(\mathbf{x}_i)^T\beta+b) \big) _+ } +\lambda||\beta ||^2$$

• Note that the constant $b$ can be computed when the $\alpha_i$ are known, so there are $N$ parameters.
– user83346
Aug 19, 2015 at 14:26

It sounds like you're asking why we always solve the dual SVM problem instead of the primal. The answer is regularization. Without the regularization term, the primal QP would have $k + 1$ variables and $N$ inequality constraints, where as the dual QP would have $N$ variables, $N$ inequality constraints and $1$ equality constraint. So you're correct that it should be faster to solve the primal QP, assuming $k < N$.
However, once you add the regularization term, this is no longer true. With the regularization term, the primal QP has $N + k + 1$ variables and $2N$ inequality constraints but the dual QP has $N$ variables, 1 equality constraint and $2N$ inequality constraints. Moreover, those $2N$ inequality constraints are actually box constraints on the variables, so only half can ever be active at the solution.