Support Vector Machines are a family of data analysis algorithms, based on convex Quadratic Programming. We focus on their use for classification that case the SVM algorithms work by maximizing the margin of a classifying hyperplane in a feature space. The feature space is handled by means of kernels f the problems are formulated in dual form. Random Sampling techniques successfully used for similar problems are studied here. The main contribute on is a random zed algorithm for training SVMs for which we can formally prove an upper bound on the expected running time that is quasilinear on the number of data points. To our knowledge, this is the first algorithm for training SVMs in dual formulation and with kernels for which such a quasi-linear time bound has been formally proved.