0
$\begingroup$

I recently came across a statement that the unconstrained primal L2-regularized SVM formulation $$ \min_\mathbf{w} \lambda \|\mathbf{w}\|^2_2 + \sum_i \max (0, \; 1 - y_i \mathbf{w}^T\mathbf{x}_i) $$ is equivalent to a primal constrained formulation \begin{align} \min_\mathbf{w} \sum_i \max (0, \; 1 - y_i \mathbf{w}^T\mathbf{x}_i) \\ \text{s.t.} \qquad \|\mathbf{w}\|_2 \le \frac{1}{\sqrt{\lambda}} \end{align}

I found no traces of it in the internet, and I can't see what's the intuition behind and the proof of it. Any ideas? Thx.

$\endgroup$
2
  • 1
    $\begingroup$ Where did you read that? $\endgroup$ – Firebug Jan 31 '18 at 17:11
  • $\begingroup$ @Firebug This was a slide from my fellow's optimization course, which is under a restricted URL-access, unfortunately I can't provide it here, sorry! $\endgroup$ – agronskiy Jan 31 '18 at 17:17
1
$\begingroup$

Generally speaking, assuming you had a more standard expression of $\frac{\lambda}{2}||w||^2_2 + \frac{1}{n}\sum_i \max(0, 1 - y_i w^T x_i)$ would give a bound on the solution size of $\frac{1}{\sqrt \lambda}$. Your form would actually have $\sqrt{\frac{2n}{\lambda}}$.

This statement is almost assuredly false. Let $w^*$ be the solution to the standard way of representing the SVM problem.

If we knew that the $||w^*||_2 = S$, for some $S$, then one could bound $||w|||_2 \leq S$ of course and it would be equivalent.

One can show that $||w^*||_2 = o\left(\frac{1}{\sqrt{\lambda}}\right)$. Thus, the space covered by $||w||_2 \leq ||w^*||_2$ becomes infinitely small when compared to $||w||_2 \leq \frac{1}{\sqrt{\lambda}}$; this makes it almost certain that for many problems there is some solution in the space $||w^*||_2 < ||w||_2 \leq \frac{1}{\sqrt{\lambda}}$ which performs better than $w^*$ for the primal-constrained version.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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