# What algorithm do SVMs use to minimize their objective function?

Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems.

$$\text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2$$

My question is, what linear programming runs on the background for the minimization of the objective function $$J$$. Is it Simplex?

• Its not linear programming. its Quadratic programming, you have here a quadratic function and not a linear one Feb 22, 2021 at 15:18
• A good algorithm to use is the SMO - Sequential Minimal Optimization, which is a technique specifically designed for SVMs Feb 22, 2021 at 15:19
• @nirshahar Thanks a lot. I recommend that you post those comments as an answer so I can accept it! Feb 22, 2021 at 15:24

The SVM problem (and other related problems) can be described as a minimization \ maximization of a quadratic function.

This can be easily solved with the gradient descent algorithm, however I recommend using the SMO algorithm since it is a direct solution (to the dual of the SVM problem), and can be also used for kernelized SVMs

• Addition to the above answer: I just came across this paper (link below) that presents PEGASOS algorithm. It claims that with PEGASOS "the number of iterations required to obtain a solution of accuracy $\epsilon$ is $O(1/\epsilon)$, where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs require $Ω(1/\epsilon^2)$ iterations" courses.edx.org/assets/courseware/v1/… Feb 26, 2021 at 12:49