2
$\begingroup$

I'm trying to figure out where I'm going wrong with my formulation of a certain problem, as all other instances of it were formulated slightly differently.

The problem (SVR problem, If you're familiar with it) is as follows:given $\{x^{(i)},y_i\}_{i=1}^{m}$, We would like to find a hyperplane, defined by $\langle w,x\rangle +b=0$ which minimizes the $l_2$ norm of $w$ plus the sum (over $i$) of the loss defined by: $$loss(w,b;x^{(i)})=[\left|\langle w,x^{(i)}\rangle +b -y_i\right|-\epsilon ]_+ $$

I would formulate the problem as follows: $$\min_{w,b,\xi_i} \frac{1}{2}\|w\|^2 + \sum_{i=1}^{m}\xi_i$$ $$s.t.\cases{\langle w,x^{(i)}\rangle +b-y_i-\epsilon\leq\xi_i\cr y_i-\langle w,x^{(i)}\rangle -b-\epsilon\leq\xi_i\cr \xi_i\geq 0} i=1,...,m $$ But every formulation I've seen uses separate variables $\xi_i,\xi_i^* \geq 0$ for the first 2 constraints: $$\min_{w,b,\xi_i} \frac{1}{2}\|w\|^2 + \sum_{i=1}^{m}(\xi_i + \xi_i^*)$$ $$s.t. \cases{\langle w,x^{(i)}\rangle +b-y_i-\epsilon\leq\xi_i\cr y_i-\langle w,x^{(i)}\rangle -b-\epsilon\leq\xi_i^*\cr \xi_i,\xi_i^*\geq 0} i=1,...,m $$ What's wrong with my way? I'm thinking it might have something to do with the KKT conditions (since we want to formulate it using the multipliers and get a problem with a global minimum). I have some basic understanding of the KKT conditions, but I don't fully understand all the constraints qualifications (Which I assume might be the problem)

$\endgroup$
10
  • $\begingroup$ Your way looks good. If $z_i=<w,x^i>+b-y_i$ then $loss_i = [|z_i|-\epsilon]_+$ and so $z_i - \epsilon \leq loss_i$ and $-z_i - \epsilon \leq loss_i$, which are captured in your constraints.So your problem seeks to minimize $(1/2)||w||^2 + \sum_i loss_i$. $\endgroup$
    – Michael
    Dec 24, 2014 at 19:24
  • $\begingroup$ I think you would need to add the $<w,x>+b=0$ constraint though. I don't know what the "other formulation" is or if it has some advantages. Your problem indeed looks convex. $\endgroup$
    – Michael
    Dec 24, 2014 at 19:31
  • $\begingroup$ @Michael Well, the question persists then... I'm hoping to find someone who is by chance familiar with SVR and convex optimization in general to explain this... I haven't found a detailed explanation of the formulation, only a description of the problem and then a formal formulation like mine except with the noted changes. We won't need the constraint $\langle w,x\rangle +b=0 $ though, it's just the definition of a hyperplane, we don't have some $x$ for which we demand this. $\endgroup$ Dec 25, 2014 at 19:13
  • $\begingroup$ I see no problem at all with your formulation. In fact, you don't even need $\xi_i\geq 0$. It is implied by the other two. I'll bet that a formulation that uses $\xi_i^*$ is less efficient than yours. But in fact, we can't answer the question fully without seeing the exact form of the alternate formulation. $\endgroup$ Dec 26, 2014 at 2:30
  • 1
    $\begingroup$ Then as written I am certain the extra variables are unnecessary. Either one or the other of $\xi_i$, $\xi_i^*$ will be zero at the optimum. (Or both.) $\endgroup$ Dec 26, 2014 at 14:52

1 Answer 1

2
$\begingroup$

The dual of your new primal problem is almost the same as the standard dual, with one difference. To see this, I am following the work on this link (but modifying it to your new primal): http://alex.smola.org/papers/2003/SmoSch03b.pdf

Under your new problem, the Lagrangian is (with multipliers $\lambda_i, \mu_i, \theta_i$):

\begin{align} &L = \frac{1}{2}||w||^2 + \sum_i \xi_i \\ &+ \sum_i \lambda_i [w^T x^i + b - y_i - \epsilon - \xi_i] \\ &+ \sum_i \mu_i [y_i - w^T x^i - b - \epsilon - \xi_i] \\ &-\sum_i \theta_i \xi_i \end{align}

where $w^T$ is the transpose of vector $w$. You now use duality concepts to compute $\sup_{\lambda \geq 0 , \mu \geq 0, \theta \geq 0} \left[\inf_{w, \xi, b} L\right]$. Since we must have an infimum over $w$ we can take $\partial/\partial w_j$ to get (similar to equation (8) in the paper):

$$ w = \sum_i (\mu_i - \lambda_i)x^i $$

Since we must take an infimum over $b$, the answer is $-\infty$ unless (similar to equation (7) in the paper):

$$ \sum_i (\lambda_i - \mu_i) = 0 $$

and so we must choose the multipliers to satisfy the above to avoid a $-\infty$ infimum. Similarly, since we take an infimum over $\xi_i$ we must have (similar to equation (9)):

$$ 1 = \lambda_i + \mu_i + \theta_i $$

Plugging these back into the Lagrangian $L$, simplifying, and taking the outer maximization gives:

\begin{align} &\mbox{Maximize:} -\frac{1}{2}\sum_i\sum_j (\mu_i-\lambda_i)(\mu_j-\lambda_j)x_i^Tx_j - \epsilon\sum_i(\lambda_i + \mu_i) + \sum_i y^i (\mu_i-\lambda_i) \\ &\mbox{Subject to:} \sum_i (\lambda_i-\mu_i) = 0 \: \: , \: \: \lambda_i \geq 0 \: \: \forall i \: \: , \: \: \mu_i \geq 0 \: \: \forall i \: \: , \: \: \lambda_i + \mu_i \leq 1 \: \: \forall i \end{align}

where the $\lambda_i + \mu_i \leq 1 $ constraint comes from $\lambda_i + \mu_i = 1 - \theta_i$ and $\theta_i\geq 0$. The only difference between this new dual problem and the standard one given in equation (10) of the paper is that, there, we would get separate constraints $\lambda_i \in [0,1]$ and $\mu_i \in [0,1]$ rather than the combined constraint $\lambda_i + \mu_i \leq 1$. I think the separate constraints are a bit easier, and so your formulation has a simpler primal (as Michael Grant also mentioned), but a slightly more complicated dual.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .