$\lambda \Vert k \Vert_0$ or $\Vert k \Vert_0 \leqslant n$

Question

Say $Y \in \Bbb R^n$ is a response, $X = (x_1, x_2, \cdots, x_m)^T \in \Bbb R^{n \times m}$ are predictors. In a linear regression problem, we want to add an $l_0$ regularization for feature selection.

The first cost function is

$$\text{argmin}_{k \in \Bbb R^{m}} (\Vert Y - Xk \Vert_2^2 + \lambda \Vert k \Vert_0)$$ where $\Vert k \Vert_0$ is $\# \{j: k_j \neq 0\}$

The second cost function is $$\text{minimize}_{k \in \Bbb R^{m}} \Vert Y - Xk \Vert_2^2 \text{ subject to }\Vert k \Vert_0 \leqslant n$$

Say we solve the two problems by using brute force, which means we evaluate the cost for all possible combinations of features.

In the second problem, the RMSE of descriptors (composed of selected features) of different dimensions can be compared directly. However, in the first problem, we must take into account the hyperparameter $\lambda$ that has to be determined by CV.

In practice, what is the objective function that we solve? I think the two results that we get can be totally different. Moverover, will the descriptor with more features always win?

Answer 1

Let's say you have some value $p \leq m$, and only want to use $p$ features to fit your model. I'm also going to assume the problem is 'high-dimensional,' meaning that $m$ is 'big.' In your first objective function, as $\lambda \to \infty$, the number of features that are kept goes to $0$. Furthermore, there is a specific interval between which a fixed number of features are dropped and the rest remain. More concretely, there is some minimum value $\lambda_{0}$, where $\lambda < \lambda_{0}$ means that no features are dropped. There is also a set $\lambda_{1}< \lambda_{2}< \dots < \lambda_{m-1}$ which set thresholds for the number of features in your resulting model, such that for $\lambda_{0} < \lambda < \lambda_{1}$, one feature is dropped, $\lambda_{1} < \lambda < \lambda_{2}$ two features are dropped, etc. Thus, for $p < m$, you can find some $\lambda_{j} < \lambda_{m-1}$ such that $\lambda_{j -1} < \lambda < \lambda_{j}$ results in exactly $p$ features being kept in your model.

Now, which specific set of $p$ features that you keep in your model is not determined by the $\lambda$ value you use. In fact, if you were to perform a simple rotation on your original set of features, used the same value for $\lambda$, and refit your model, you would still get $p$ features, but a possibly different set of $p$ features. This has to do with the fact that the $l_{0}$ norm is not rotationally invariant - the same thing occurs in LASSO regularization using an $l_{1}$ regularization term, but does not occur in Ridge regression where an $l_{2}$ regularization term is used, as the $l_{2}$ norm is rotationally invariant. This also means that your RMSE won't change if you're only performing a rotation of some kind. The degree to which this occurs will depend on the degree of collinearity between any of the features.

The second objective function only determines an upper bound on the number of features, and I assume this means you can try all such subsets of features so long as the cardinality of the subset does not exceed $p$. Of course, as you already mentioned, including more features will allow you to more closely approximate your response vector $Y$, so it will come down to just comparing all the possible subsets of size $p$ and finding the one that minimizes the $l_{2}$ part of the cost. Now you should arrive at the same answer as the first objective function, meaning you end up with the same specific set of $p$ features that minimizes the RMSE. This will also be subject to whatever changes rotations might induce based on the degree of collinearity between any of the features. Thus, the two cost functions are really performing the same process, but depending on the implementation, the second might be slower if it wastes time checking any subsets having fewer than $p$ features.