Learning performance comparable to SVM that doesnt require QP

[hsolo]

1. Is there any learning algorithm/approach that offers, in practice, performance comparable to SVM but that doesnt require QP?

For eg, http://cbcl.mit.edu/cbcl/publications/ps/rlsc.pdf

2. At a high level is it correct to think of regularization as introducing a 'softness' and thus a 'generalization dividend' for regression problems and of SVMs (soft kernels) as introducing a generalization dividend for classification problems, albeit at the cost of QP?