# Carousel Greedy Algorithms for Feature Selection in Linear Regression
## 4 Generalized Feature Selection  
In this section, we will discuss two generalized versions of feature selection. Recall the feature selection problem that we discussed is  
\[\min_{\theta}\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{i}) ^{2},\] (13) subject to \[\sum_{j=1}^{p}I_{\theta_{j}\
eq 0}\leq k. \tag{14}\]  
This can be reformulated (big-M formulation) as the following MIP (for large enough \(M>0\)):  
\[\min_{\theta,z}\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{ i})^{2},\] (15) subject to \[-Mz_{i}\leq\theta_{i}\leq Mz_{i},\quad\forall i\in[p], \tag{16}\] \[\sum_{i\in[p]}z_{i}\leq k,\] (17) \[z_{i}\in\{0,1\},\quad\forall i\in[p]. \tag{18}\]  
Here, \(z_{i}\) is the indicator variable for \(\theta_{i}\), where \(z_{i}=1\) if \(\theta_{i}\) is nonzero and \(z_{i}=0\) otherwise. \begin{table}
\begin{tabular}{l l l l l} \hline \hline  & \multicolumn{2}{c}{\(k=20\)} & \multicolumn{2}{c}{\(k=25\)} \\  & RSS & Time (s) & RSS & Time (s) \\ \hline Stepwise regression & 911,080 & 25.99 & 829,608 & 38.45 \\ CG with stepwise initialization & **870,346** & 214.43 & **791,960** & 440.14 \\ Iterated BI-MIPs by Gurobi with stepwise initialization & **870,346** & 303.65 & 792,731 & 566.38 \\ \hline  & \multicolumn{2}{c}{\(k=30\)} & \multicolumn{2}{c}{\(k=35\)} \\  & RSS & Time (s) & RSS & Time (s) \\ \hline Stepwise regression & 767,448 & 52.70 & 723,472 & 68.81 \\ CG with stepwise initialization & **741,317** & 437.13 & 700,462 & 566.73 \\ Iterated BI-MIPs by Gurobi with stepwise initialization & 751,680 & 406.33 & **699,196** & 457.45 \\ \hline  & \multicolumn{2}{c}{\(k=40\)} & \multicolumn{2}{c}{\(k=45\)} \\  & RSS & Time (s) & RSS & Time (s) \\ \hline Stepwise regression & 685,136 & 85.31 & 651,250 & 107.74 \\ CG with stepwise initialization & **666,991** & 453.45 & **638,087** & 493.93 \\ Iterated BI-MIPs by [PERSON] with stepwise initialization & **666,991** & 416.42 & 643,517 & 353.18 \\ \hline  & \multicolumn{2}{c}{\(k=50\)} & \multicolumn{2}{c}{} \\  & RSS & Time (s) & & \\ \hline Stepwise regression & 623,118 & 132.24 & & \\ CG with stepwise initialization & 609,722 & 1409.88 & & \\ Iterated BI-MIPs by [PERSON] with stepwise initialization & **609,478** & 768.68 & & \\ \hline \hline \end{tabular}
\end{table} 
Table 4: _Cont._The problem can be generalized by adding some constraints. **Case A**: Suppose we have sets of variables that are highly correlated. For example, if variables \(i\), \(j\), and \(k\) are in one of these sets, then we can add the following constraint:  
\[z_{i}+z_{j}+z_{k}\leq 1. \tag{19}\]  
If \(l\) and \(m\) are in another set, we can add  
\[z_{l}+z_{m}\leq 1. \tag{20}\]  
**Case B**: Suppose some of the coefficients must be bounded if the associated variables are selected. Then we can add the following constraints:  
\[l_{i}z_{i}\leq\theta_{i}\leq u_{i}z_{i},\quad\forall i\in[p]. \tag{21}\]  
In (21), we allow \(l_{i}=-\infty\) or \(u_{i}=\infty\) for some \(i\) to include the case where the coefficients are unbounded from below or above. CG can also be applied to Cases A and B. Let us restate CG and show how small modifications to CG can solve Cases A and B. Recall that, in each carousel step of feature selection, we delete one variable and add one. Assume \(S_{d}\) is the set of variables _after_ deleting one variable in a step. Then, the problem of adding one becomes: Solve unconstrained linear regression problems on the set \(S_{d}\cup\{l\}\) for each \(l\
otin S_{d}\) and return the \(l\) with the smallest RSS. Expressed formally, this is  
\[\operatorname*{argmin}_{l\
otin S_{d}}f(l,S_{d}). \tag{22}\]  
Here \(f(l,S_{d})\) indicates the RSS we obtain by adding \(l\) to \(S_{d}\). It can be found from the following problem:  
\[f(l,S_{d})=\min_{\theta}\sum_{i=1}^{n}(\sum_{j\in S_{d}\cup\{l\}}X_{ij}\theta_ {j}-y_{i})^{2}. \tag{23}\]  
In (23), only a submatrix of \(X\) with size \(n\times(|S_{d}|+1)\) is involved. That is, we solve a sequence of smaller size unconstrained linear regression problems for each \(l\
otin S_{d}\) and compare the results.