Time complexity of training SVM and C I always though that a big (high) C will lead to a lower svm training complexity due to lower number of support vectors.
I was very surprised to read a paper that states the opposite - aka, big Cs actually cause higher training time.
I then checked out in other few places, they all state the same (big C - high training time).
Can anyone explain why is this true? Thank you!
 A: It is a long time since I last implemented an SVM, but this is my vague recollection of my intuition at the time of the problem [I think that is sufficient equivocation ;o) ]
For sequential minimal optimisation, the updates at each step must observe the linear constraint
$y_i\alpha_i + y_j\alpha_j = k$.
So to raise $\alpha_i = 0$ to $C$ in one go, you need to find an $\alpha_j = 0$ with $y_j$ of the opposite sign to $y_i$.  In practice, they tend not to get raised all the way to $C$ in one go, as this would end up with a discriminant that didn't minimise the quadratic objective function very well (it would be making a large change to the discriminant).  So you end up with the $\alpha$s taking on intermediate values, which limits the magnitude of the change that can be made at each step while still observing the box and linear equality constraints.
Hopefully an optimisation expert will be along who knows the actual reason!  I'd certainly be interested to see a better answer than mine.
BTW this is one of the reasons I prefer Least-Squares Support Vector Machines for small to medium sized problems (up to a few thousand examples) as their training time doesn't strongly depend on the $C$ hyper-parameter and they can be faster, especially if you are doing a grid-search over the hyper-parameters.
A: Generally speaking this ties closely in to the concept of strong-convexity. Of interest here is the so-called condition number which is defined as $\kappa = \frac{L}{\mu}$ for an $L$-smooth, and $\mu$-strongly convex function. Of relevance here is the lower bound in this paper on the number of Oracle calls, which has a dependence on $\sqrt{\kappa}$. For SVM (or similar formulations with smoothed loss functions which converge to the hinge loss), $\mu=\frac{1}{C}$ (always), so one can indeed see that the lower bound increases at $\sqrt{C}$
