4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Generally speaking, as far as I know, constrained optimization is much harder than simple regularization... $\endgroup$ Aug 30, 2020 at 13:41
  • $\begingroup$ Note that this applies not only to $L1$ regularization, but also to $L2$ etc. $\endgroup$ Aug 30, 2020 at 13:41
  • $\begingroup$ @ItamarMushkin Fair enough, but the constrained optimization is sometimes chosen, is it not? I have only actually seen it in textbooks. I generally expected that the regularized case would be the default, but there must be some benefit to the constrained case. $\endgroup$
    – user291435
    Aug 30, 2020 at 13:43
  • $\begingroup$ The regularization term approach, and the constraint approach are inversely equivalent $\endgroup$
    – develarist
    Aug 30, 2020 at 15:46
  • $\begingroup$ @develarist Can you clarify the term inversely equivalent? Moreover, even if for properly chosen $\lambda $ and $M$ the two problems are equivalent, that does not mean they are equally good when implemented. For instance, $Ax=b$ can be solved by $x=A^{-1}b$ directly (where $A^{-1}$ exists), but there are situations where it is better to use, say, an iterative approach -- despite there being only one answer that both should achieve in theory. Then there's the matter of actually converting between $\lambda $ and $M$... am I making sense? $\endgroup$
    – user291435
    Aug 30, 2020 at 16:13

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I appreciate all of the background, that will be helpful. But regarding the main question, is the answer basically that you would use the first form to avoid an inactive constraint, whereas you might use the constrained form when returning a global minimum is acceptable/desirable? $\endgroup$
    – user291435
    Aug 30, 2020 at 16:34
  • 1
    $\begingroup$ @user37344 In most practical cases the global minimum probably won’t be feasible so the difference won’t matter, but yeah for me personally I’d always use the first form because I want to actually get shrinkage. For any application I’ve worked on I don’t actually care about the $L_1$ norm as such, but rather I want to get the sparsity that comes from the constraint being active $\endgroup$
    – jld
    Aug 30, 2020 at 16:37
  • $\begingroup$ @jid Gotcha, and on top of that my understanding is that constrained optimizations tend to be numerically harder anyway, so I guess you wouldn't expect to see the 2nd form being very popular. $\endgroup$
    – user291435
    Aug 30, 2020 at 16:43
  • $\begingroup$ @user37344 if the provided value of $M$ makes the global optimum infeasible then solving the first problem is what we do to solve the second problem (since it’s the Lagrangian), so it’s not that one is harder than the other but rather that the constrained problem’s solution may not have shrinkage if the unconstrained solution just happens to be feasible and if I’m doing this, at least, I want the shrinkage $\endgroup$
    – jld
    Aug 30, 2020 at 16:48
1
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ That's interesting. Just to clarify, in the stacked regressions case the problem is actually solved as a constrained optimization problem? And, generally speaking, is that just because the constraints are so specific that there isn't really a good way to convert the problem to one that uses regularization? $\endgroup$
    – user291435
    Aug 30, 2020 at 16:24
  • $\begingroup$ Also, I'm nit picking a bit, but I don't think your stacked regressions example is in the form I gave in my question. It's still interesting, but I don't think it counts as an example here. $\endgroup$
    – user291435
    Aug 30, 2020 at 16:41
  • $\begingroup$ It is of the same general formulation, just not $l1$ minimization. There is a discussion on the paper I linked on why constraint optimization works better than $l2$ regularization in that case, but conclusions are partial for that regard. $\endgroup$ Aug 30, 2020 at 17:59
  • $\begingroup$ +1 interesting example $\endgroup$
    – jld
    Sep 1, 2020 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.