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

Question

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.

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.