L1 Regularization vs Constraint

Question

It is my understanding that the these: \begin{equation} min_{x}f(x)+\lambda\vert\vert x\vert\vert _{L_{1}} \end{equation}

\begin{equation} min_{x}f(x) \text{,}\hspace{5pt}\vert\vert x\vert\vert _{L_{1}}\leq M \end{equation} problem formulations are both modifications of \begin{equation} min_{x}f(x) \end{equation} which promote sparsity (where $f$ is some loss function, and $x$ are model parameters). Comparing them, I'm guessing that the latter should be used when you either have some idea of the "actual" model's complexity or when computational constraints put a hard bound of the complexity of the model that you can use (I'm using the word complexity here just to mean the opposite of sparseness), whereas the former would be used in other cases. Am I on the right track, and, if not, when should each be used?

Edit: I should clarify this question a little bit. I am aware that, under the right conditions (I think they are fixed $f$, well chosen $\lambda $ and $M$, probably something to do with smoothness) the two problem formulations are mathematically equivalent. But, unless there is a way to convert between $\lambda $ and $M$, you still have to choose one or the other. Moreover, the two set ups would require different approaches numerically, so that one or the other may be better even if you can convert between them. So, I'm more curious about cases where you would use one or the other in practice.

Answer 1

We have the problem $$ \min_x f(x) \\ \text{subject to} \;\|x\|_1 - M \leq 0 $$ where the constraint $x\mapsto \|x\|_1 - M$ is convex and I'll assume $f$ is too (e.g. this could be least squares). If $M > 0$ then Slater's condition holds which means we have strong duality (this is so the regularity conditions of the KKT conditions are met).

The key idea is this: we have our Lagrangian $$ \mathcal L(x,\lambda) = f(x) + \lambda(\|x\|_1 - M) $$ and the KKT conditions tell us that at an optimal point we'll have a condition called complementary slackness which is that $$ \hat \lambda (\|\hat x\|_1 - M) = 0. $$ If it turns out that the global minimum of $f$ (unconstrained) is strictly feasible then we'll have $\|\hat x\|_1 - M < 0$ which forces $\hat\lambda = 0$, and our optimal value is just the unconstrained minimum. But if $\hat\lambda > 0$ then it must be that the constraint is active and our solution is pulled away from the global unconstrained argminimum (unless by chance the global solution happens to exactly have an $L_1$ norm of $M$, but that's an edge case).

When we do this in practice, we typically don't care about the unregularized solution and it would probably be an undesirable feature to sometimes return that if we happened to pick too large of a $L_1$-ball to constrain ourselves to. So when we minimize $\mathcal L$ over $x$ with a provided $\lambda > 0$, as we do when we plug it in as a tuning parameter, we are effectively forcing the constraint to be active and this guarantees us shrinkage.

So conceptually these are quite similar, the only difference is that by directly minimizing the penalized form we aren't taking the chance of having an inactive constraint.

Answer 2

Depending on the problem at hand, both formulations might be equivalent ( for example in the case of Ridge Regression).

An example of preferring constrained optimization would be the case of Stacked Regressions. Here you have a set of predictions $v$ from different models and apply constrained least squares in order to find a weighted average that minimizes prediction error. It can be formulated as: $min \sum_n(y_{i}-\sum_ka_kv_{kn})^2, s.t. a_k\geq0, \sum a_k=1$

This is a little bit different, but in some applications, such as optimal control or design, we might want to find the least-norm solution of a set of linear equations. The problem here is: $min ||x||, s.t. Ax=b$