This work proposes a new algorithm for training a re-weighted L2 SupportVector Machine (SVM), inspired on the re-weighted Lasso algorithm of Cand\`eset al. and on the equivalence between Lasso and SVM shown recently by Jaggi. Inparticular, the margin required for each training vector is set independently,defining a new weighted SVM model. These weights are selected to be binary, andthey are automatically adapted during the training of the model, resulting in avariation of the Frank-Wolfe optimization algorithm with essentially the samecomputational complexity as the original algorithm. As shown experimentally,this algorithm is computationally cheaper to apply since it requires lessiterations to converge, and it produces models with a sparser representation interms of support vectors and which are more stable with respect to theselection of the regularization hyper-parameter.