2026-10-29 CVXOPT Scribe
$\newcommand{\R}{\mathbb{R}}$ $\newcommand{\qq}{\quad\quad}$ $\newcommand{\lag}{\mathcal{L}}$
Last class we saw the geometry problems such as projection onto a set. Refer the book for more examples. A particularly interesting is projection onto a convex polyhedron. We will look into Support Vector Machines in this class
Support Vector Machines
Though regarded as an ancient relic by some, SVMs are still very important. They were THE main linear classification tool used in the 90s before the advent of deep learning. They still very useful today if you have small problems or if the dataset is too small for deep learning to work. They are also very useful on resource constrained devices.
Classification Problem
Suppose you have some dataset $(X, y) = (x_i, y_i)_i \in \R^n \times \{-1, +1\}$. We want to fit a line through this. This has the following form $$ w^Tx_i - b = \begin{cases}
0, y_i = 1\ < 0, y_i = -1 \end{cases} $$
The reason we use $\{-1, +1\}$ is that we can combine the cases into one as
$$ y_i(w^Tx_i - b) \ge 0 $$We can already form an optimization problem as
$$ \begin{align} \text{minimize}\qq & 1\\ \text{subject to}\qq & y_i(w^Tx_i - b) \ge 0, i = 1, \ldots, N& \end{align} $$Though it seems weird to minimize 1, this does indeed work. All we’re asking here is that is there a feasible solution?
In the case a feasible solution exists, it probably won’t be unique.
In that case how do we pick a good solution? How do you define good?
One way to define good is by the width of the margin. We want the widest gap between the classes. This in turn causes the classifier to be in the most middle between the classes.
Classifiers having this property are called Maximum Margin Linear Classifiers. How do we express this quality as an optimization problem?
$$ \begin{align} \text{minimize}\qq& -t\\ \text{subject to}\qq& y_i (w^Tx_i - b) \ge t \end{align} $$There is a problem in this formulation. We can scale $w, b$ by arbitrary amounts and minimize $-t$. We have to add a constraint to stop this.
$$ \begin{align} \text{minimize}\qq& -t\\ \text{subject to}\qq& y_i (w^Tx_i - b) \ge t\\ & \|w\|_2 \le 1 \end{align} $$As mentioned above the solver wants to maximize $w$ hence the inequality will always be tight. But we cannot have this as our constraint. $\|w\|_2 = 1$ gives us a hypersphere which is not convex. So even if we know that the solution will be on the sphere we have to have the entire ball as our constraint.
Lagrangian
$$ \begin{gather} \lag(t, w, b, \mu, \lambda) = -t + \sum_i \mu_i(y_i(w^Tx_i - b) - t) + \lambda (\|w\|_2 - 1) \end{gather} $$Differentiating w.r.t $b$ and $t$ gives us the following
$$ \sum \mu_i = 1\\ \sum \mu_i y_i = 0 $$Let us mull over what this means. Summing of all the $\mu$-s is equal to 1. These look like convex coefficients. As $y\in\{-1, +1\}$ we can split the sum over $\mu_iy_i$ as
$$ \sum_i^{N^+} \mu_i^+ - \sum_i^{N^-}\mu^-_i = 0 $$Substituting this into $\sum \mu_i$ we get
$$ \sum_i^{N^+} \mu_i^+ = \sum_i^{N^-}\mu^-_i = \frac{1}{2} $$Differentiating a norm seems like a pain in the ass so we will leave it as is for now. Then Lagrange dual function looks like
$$ \begin{align} g(\mu, \lambda) &= \inf_{w} \left(w^T\sum_{i = 1}^N \mu_i y_i x_i + \lambda \|w\|_2 - \lambda \right)\\ &= \begin{cases} -\lambda,\qq \|\sum_i \mu_i y_i x_i\|_2 \le \lambda \\ -\infty,\qq \text{o.w } \end{cases} \end{align} $$We form the dual problem as
$$ \begin{align} \text{minimize}\qq & -\|\sum_{i = 1}^N \mu_i y_i x_i\|_2\\ \text{subject to}\qq & \mu \succeq 0\\ & \sum_i \mu_i^+ = \sum \mu_i^- = \frac{1}{2} \end{align} $$Splitting the $\mu$-s we can write the objective function as $\|\sum \mu_i^+ x_i^+ - \sum \mu_i^- x_i^-\|$. This looks like minimizing the distance between two convex combinations.
As this satisfies Slater’s constraint qualification, the primal value is equal to the dual value.
All of this is just the maximum margin linear classifier. SVM add a relaxation on this to allow misclassifications. Obviously we don’t want misclassifications to happen but when they do we want to penalize them based on how wrong they are rather penalty based on the hardness of classification. For a point very close to the margin we will penalize less as it is indeed a tricky point to classify but we will heavily penalize the point that are clearly far away from the margin and yet are misclassified.