# How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?

This question is about an optimization problem that arises in support vector regression (SVR). Suppose you have $$N$$ pairs $$(\vec{x}_n, y_n)$$ as data and would like to find a vector of weights $$\vec w \in\mathbb R^k$$ and a bias $$b \in \mathbb R$$ such that function $$\vec{w}^T \vec{x}_n + b \approx y_n \,\forall n$$.

(Vapnik, 1995, sec. 5.9.2) introduces SVR as an empirical risk minimization problem:

\begin{aligned} \min_{\mathbf w, b} \quad\frac12 w^T w + C \sum_{n=1}^N l(x_n,y_n; \mathbf w,b)\\ l(x_n,y_n; \mathbf w,b) = \max\left( 0, |y_n - (w^T x_n + b)| - \varepsilon \right) \end{aligned}

The $$l(x_n,y_n; \mathbf w,b)$$ function is known as the $$\varepsilon$$-insensitive loss function.

He then claims that this problem "is equivalent to the problem of finding the pair $$\mathbf w, b$$ that minimizes the quantity defined by slack variables $$(\xi_n,\xi_n^*)_{n=1}^N$$":

\begin{aligned} \min_{\mathbf w, \mathbf\xi, \mathbf\xi^*} &\quad\frac12 w^T w + C \sum_{n=1}^N (\xi_n + \xi_n^*)\\ \text{s.t.} &\quad \begin{cases} y_n - (w^T x_n + b) &\le \varepsilon + \xi_n^*\\ -(y_n - (w^T x_n + b)) &\le \varepsilon + \xi_n\\ \xi_n, \xi_n^* &\ge 0 \end{cases} \forall n\in \{1,\dots,N\} \end{aligned}

My question is: how to get from the $$\varepsilon$$-insensitive loss to the quadratic optimization problem above? Where do the slack variables $$\xi_n,\xi_n^*$$ come from?

Here's what I found:

• (Smola, 2004) cites (Vapnik, 1995) and says that the above optimization problem "corresponds to dealing with a so called $$\varepsilon$$-insensitive loss function", but doesn't explain how to get from the $$\varepsilon$$-insensitive loss to the QP.

• Slides from this CrossValidated answer go from the $$\varepsilon$$-insensitive loss to the QP with no explanation as well.

• These slides (slide 11) derive the QP from the $$\varepsilon$$-insensitive loss step-by-step, but they don't explicitly explain why I can just introduce these random $$\xi_n$$ slack variables.

In particular, why is the minimization problem with the $$\varepsilon$$-insensitive loss equivalent to this? \begin{aligned} \min_{b,w,\xi}&\quad \frac12 w^T w + C\sum_{n=1}^N \xi_n\\ \text{s.t.}&\quad \begin{aligned} &\left| y_n - (w^T x_n + b) \right| - \varepsilon \le \xi_n\\ &\xi_n \ge 0 \end{aligned}\quad\forall n \end{aligned}

Looks like they're trying to find the smallest $$\xi_n$$ such that $$\max\left( 0, \left| y_n - (w^T x_n + b) \right| - \varepsilon \right) \le\xi_n$$, but why is this equivalent to the original problem? How did they think of such a transformation? In what cases can it be applied?

# References

• This is a generalization of the [usual linearization of the minimization of a sum of absolute values]. Because $\xi^*_n$ and $\xi_n$ have the same objective coefficient and will not both be positive at optimality, you can get by with omitting $\xi^*_n$ and just using $\xi_n$ in both constraints. : or.stackexchange.com/questions/8831/… Jul 11 at 16:57
• @RobPratt, "you can get by with omitting $\xi_n^*$" - will this result in an equivalent optimization problem? All derivations I could find, including the widely used LIBSVM library (sec. 2.4 here) and scikit-learn, use both $\xi_n^*$ and $\xi_n$. Now I kind of see where $\xi_n$ come from in the last optimization problem, but why are the $\xi_n^*$ there? I feel like they're redundant, but they appear in all derivations anyway... Jul 12 at 19:34

Consider a simpler problem where you are given a constant $$k\ge 0$$ and want to find $$x\in \mathbb{R}$$ to minimize the (convex piecewise-linear) loss function $$\max(x-k,-k-x,0)=\begin{cases} x-k &\text{if x> k} \\ -k-x &\text{if x< -k} \\ 0 &\text{if -k \le x\le k}\end{cases}$$ (Note that the special case $$k=0$$ corresponds to $$|x|$$.) One way to linearize this minimax objective is to introduce a decision variable $$z$$ and minimize $$z$$ subject to \begin{align} z &\ge x - k \\ z &\ge -k - x \\ z &\ge 0 \end{align}
Another way to linearize this minimax objective is to introduce two decision variables $$z^+$$ and $$z^-$$ and minimize $$z^++z^-$$ subject to \begin{align} -k \le x - z^+ + z^- &\le k \\ z^+ &\ge 0 \\ z^- &\ge 0 \end{align} At optimality, $$z^+ = \max(x-k,0)$$ and $$z^- = \max(-k-x,0)$$, and at most one of these can be positive, so the objective value is $$z^+ + z^- = \max(x-k,-k-x,0)$$, as desired.