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?