2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ This is a generalization of the [usual linearization of the minimization of a sum of absolute values][1]. 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. [1]: or.stackexchange.com/questions/8831/… $\endgroup$
    – RobPratt
    Jul 11, 2023 at 16:57
  • $\begingroup$ @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... $\endgroup$
    – ForceBru
    Jul 12, 2023 at 19:34

1 Answer 1

4
$\begingroup$

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|$.) enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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