 <p>For completeness, <a href="http://scikit-learn.org/stable/modules/svm.html#nusvc" rel="nofollow">from the documentation</a>: Nu-SVM is a constrained formulation of SVM (equivalent with the original up to reparametrization) which poses a hard bound on the allowed misclassification. If this bound cannot by satisfied, then the associated convex optimization problem becomes infeasible.</p> <p>From this standpoint the first thing you have to investigate is how much training error you really can expect, and maybe revise your assumptions. Search over a grid of <code>C</code> values for a standard SVM to check that.</p> <p>NuSVC should work with some values strictly less than 1, though. According to your description, you have tried 0.9 -- start adding 9s, ie .99, .999. If it doesn't work at some point, then there has to be another problem somewhere.</p>