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!

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}$
