# Primal constrained (not on $\xi_i$, but on $\mathbf{w}$!) formulation of L2 SVM

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.

• Where did you read that? Jan 31, 2018 at 17:11
• @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! Jan 31, 2018 at 17:17

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.