The role of Support Vectors in optimization

Question

I believe that I have somewhat an understanding of the objective and loss functions associated with Support Vector Machines (SVM), however, one point is still confusing me: The fact that the margins of the SVM can be characterized only by the Support Vectors is often named as a reason for their efficient optimization.

What I do not understand is this: To know what the Support Vectors will be, doesn't the algorithm have to consider all the datapoints in the beginning? I.e. is this sparse representation not only possible after training?

Edit: Here is an example:

In other words, if all data points other than the support vectors were removed, the algorithm would find the same solution. This property, known as sparseness, has many consequences, both in the implementation and in the analysis of the algorithm

From this paper: Cristianini, N. and Scholkopf, B. (2002). Support Vector Machines and Kernel Methods: The New Generation of Learning Machines, page 39.

So, I understand how the (hinge) loss function looks like, how we come to this function at all, and how derivation can lead to a solution - but I guess I don't understand how this is algorithmically implemented such that only the support vectors are needed (from when on are only these needed, how exactly does this affect the SVM optimization?)

Answer 1

Let's focus on the case of kernel-SVMs and analyze its computational complexity, differentiating between the learning stage and the prediction stage (even though I think in your question you only consider the former).

Let $m$ denote the number of training examples, $S<m$ denote the number of support vectors, and assume the complexity of implementing the kernel $K$ is $O(n)$ (which is the common case for most kernels).

Prediction: $O(n\cdot S)$. This follows from the fact that the Representer theorem tells us that the optimal solution of the quadratic program solved by SVM implementations (the dual problem formulation) - i.e, the final predictor - is of the form $\mathbf{w}=\sum_{i=1}^{m}\alpha_{i}\psi(\mathbf{x}_{i})$, where the coefficients $\alpha_i$ are non-zero only for those examples which are support vectors.

Learning. You are correct in your intuition, and the fact that we don't know which examples are the support vectors ahead of time is indeed what makes the analysis of the computational complexity trickier. This doesn't mean that the result is that it's not dependent on $S$, only that the argument is more complicated. Indeed, a more careful analysis (please see Section 4.2 of 1 for a full treatment) shows that the complexity is in the order of both $S^3$ and $m\cdot S$ (where the choice of the regularization parameter $C$ determines which of the two terms is the dominant one). Anyway, this demonstrates the point that the final number of support vectors is the critical component of the computational cost of solving the dual problem, despite it being somewhat counter-intuitive since we don't know them a-priori.

As a final comment, it's worth noting that in reality (and perhaps in practice), you will see the computational complexity of soft-SVM quoted as being either $m^2$ (for a small value of $C$) or $m^3$ (for a large value of $C$). This does follow from the above analysis, because in the limit the number of support vectors grows linearly with the number of examples.

1 [Bottou, Léon, and Chih-Jen Lin. "Support vector machine solvers." Large scale kernel machines (2007): 301-320.]