3
$\begingroup$

I understand using gradient descent methods with SVM is intractable if you've used the kernel trick. In that case, best to use libsvm as your solver.

But in the case that you are not using a kernel and simply treating it as a linear separation problem, when does it make sense to use gradient descent as your solver?

As I see it, liblinear is $O(N)$ time and doesn't require hyperparameter tuning.

In some past tests, liblinear has converged to a lower error rate at much faster rate than gradient-based methods.

Yet, Sklearn's own tests show it can be faster in many cases.

When is it optimal to use gradient-based methods with the SVM? Is it with a certain sized dataset or data that is highly linear and convex? What heuristics or explanations are available?

$\endgroup$
2
  • $\begingroup$ liblinear uses coordinate descent for optimization as against gradient descent. Is the question about which is a better optimization technique ? $\endgroup$ – Ankita Talwar Aug 25 '20 at 20:06
  • $\begingroup$ Yes, just, when does it make sense to use SGD over CD.. $\endgroup$ – Learning stats by example Aug 25 '20 at 20:13
1
$\begingroup$

As mentioned in the comment, if the question is when does it make sense to use coordinate descent over stochastic gradient descent, then, one advantage with coordinate descent is that, it updates only one parameter at a time. Thus, when the data has a very very large number of features, it might make sense to use Coordinate Descent over stochastic gradient descent as SGD will try to update all model parameters at the same time. Also, for huge amounts of data CD might have lower computational complexity as against SGD. Also, it makes sense to use Coordinate descent for optimization when the function is not differentiable. Although, there are ways to convert non-differentiable functions to differentiable ones, still Coordinate descent might be one of the ways to move forward.For example, coordinate descent is a good technique to optimize a loss with L1 penalty. It is considered state of the art for Lasso regression as well as for linear SVMs.

$\endgroup$
3
  • 1
    $\begingroup$ It is odd to me that SGD is taught with SVMs so much when CD is clearly so viable. $\endgroup$ – Learning stats by example Sep 6 '20 at 2:28
  • $\begingroup$ As far as I understand , interest in coordinate descent is much recent. SGD gets the job done, and can be generalized to many more problems. $\endgroup$ – Ankita Talwar Sep 6 '20 at 3:18
  • $\begingroup$ To some extent I agree. But SGD is still being taught today, overwhelmingly so. And yes of course SGD can be generalized but so can CD as you note.. and I'm not sure how relevant that is in the sense that what should be taught are the ideal methods. SGD is quite complicated if it's not really necesary. $\endgroup$ – Learning stats by example Sep 6 '20 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.