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.

  • 1
    $\begingroup$ Where did you read that? $\endgroup$
    – Firebug
    Jan 31, 2018 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, 2018 at 17:17

1 Answer 1


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.


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.