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

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?

• It seems to me that the constraint in the second formulation should be $\Vert k \Vert_0 \leqslant p$, where $p$ is a hyperparameter to be determined by CV. Then the two formulations are essentially equivalent. – Mark L. Stone Sep 2 '18 at 1:49
• @Mark L. Stone thank you! I didn't realize that. But even if this $p$ is a hyperparameter, it still does not come into the cost function, say I want to choose less then $k$ features, should this $k$ still be a fixed value? – meTchaikovsky Sep 2 '18 at 1:53
• $k$ is your vector of linear coefficients... do you mean $p$? – Sycorax says Reinstate Monica Sep 2 '18 at 2:03
• @ Sycorax yes, sorry about the typo :) – meTchaikovsky Sep 2 '18 at 2:05

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.
• I don't understand 'Now you should arrive at the same answer as the first objective function' in the last paragraph, even when I tune the $\lambda$ just right as you pointed out in the first paragraph, the results will be different since there is an extra term in the first cost function besides RMSE. – meTchaikovsky Sep 2 '18 at 3:21
• Sorry if I wasn't too clear, I may have left out some details. So, the $l_{0}$ regularization term forces you to have $p$ features if it's tuned appropriately, as you stated. The particular $p$ features actually used will be the ones that minimize the RMSE, since all subsets of size $p$ will have the same $l_{0}$ regularization cost. The same thing occurs in the second version of the problem, where you are finding the subset of $p$ features that minimizes the RMSE. – Don Walpola Sep 2 '18 at 3:32
• @ Don Walpola thank you, that makes sense to me now. But how can we determine such a $\lambda$? By doing grid search? Moreover, for the first objective, do we decide this $\lambda$ by the validation error rather than the number of features to choose from? – meTchaikovsky Sep 2 '18 at 3:56
• @me_Tchaikovsky Yes, the description I gave is more to explain the theory of what's going on. The particular $\lambda$ value you settle on is determined by whatever the overall goal of the regularization is. Parsimony should be an important consideration here. Balancing that with validation error and avoiding any leaking of information resulting in overfitting is a sound approach, I think. – Don Walpola Sep 2 '18 at 4:06