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

Question

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

• Vapnik, V.N. (1995) ‘Chapter 5. Constructing learning algorithms’, in The Nature of Statistical Learning Theory. New York, NY: Springer New York, pp. 119–156. Available at: https://doi.org/10.1007/978-1-4757-3264-1. PDF from someone's GitHub.
• Smola, A.J. and Schölkopf, B. (2004) ‘A tutorial on support vector regression’, Statistics and Computing, 14(3), pp. 199–222. Available at: https://doi.org/10.1023/B:STCO.0000035301.49549.88. PDF from author.

Answer 1

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.