SVM classifier convergence I was implementing a SVM Classifier using scikit library on a MNIST dataset available on Kaggle. Everything was going well until one of my friend asked me a question:

What is the number of updates required before the SVM classifier converges? 

I got stuck here. How can I answer this?
 A: This is highly dependant on the algorithm in question. Optimizers such as SMO are basically doing a matrix inversion and may have run time $O(n^3)$ in the worst case. Recent approaches are much faster, and are generally stochastic and often use variance reduction techniques. There are numerous of these: SAGA, SVRG, SPDC, etc.
Generally, in these works, they have several iterations where in each iteration they do a small amount of work (i.e., $O(d)$ where $d$ is the dimension of the problem); and in the end they take some (possibly weighted) average over the individual iterates. The number of iterates is generally $O\left( (n + f(\kappa, n)) \log \frac{1}{\epsilon}\right)$ to reach $\epsilon$ convergence, where $f(\cdot,\cdot)$ depends on the algorithm, for example $\kappa$ or $\sqrt{\kappa n}$.  $\kappa$ is the condition number ($\frac{R^2}{\lambda\gamma}$) where our points lie in an $R^2$ sphere, and our  function to minimize is $(1/\gamma)$-Lischitz smooth and $\lambda$-strongly convex. There is also work around non-strongly convex functions (i.e., $\lambda=0$).
Here are some links:
SPDC
SAGA, SVRG and more
