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.


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.