1
$\begingroup$

If I have an optimization problem w.r.t two vectors, with the following regression problem as an example: $$ \arg\min_{\beta_1, \beta_2}||y_1-X_1\beta_1||_2^2+||y_2-X_2\beta_2||_2^2 + \lambda_1||\beta_1||_1 + \lambda_2||\beta_2||_1 $$ and $\beta_1$ and $\beta_2$ have the same dimension.

Now, here are two constraints that I'm interested in:

1) constraining the two vectors to be the same: $$ ||\beta_1 - \beta_2||_1 < t $$ where $t$ is some constant. Or

2) constraining the two vectors to have the same support: $$ card(supp (\beta_1)\, \cap\, supp(\beta_2)) > t' $$ where $supp$ stands for support, $card$ stands for cardinality, and $t'$ is another constant.

Question: I wonder if solving with the first constraint is a good approximation to the second constraint?

Intuitively, I think so. Further, I think the second constraint is equivalent to: $$ ||\beta_1 - \beta_2||_0 < t'' $$ then the success of Lasso seems to indicate that we can use the first constraint to replace the second one.

I hope someone could correct/confirm my hand-waving thinkings, and if it sounds right, hopefully, can also help to make it proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.