# Carousel Greedy Algorithms for Feature Selection in Linear Regression
## 3 Algorithm Description and Preliminary Experiments
### Gurobi Implementation of Best Interchange to Find an FSI(1) Minimum  
An alternative approach to Algorithm 3 is the notion of an FSI(1) minimum. This is a local minimum as described in Section 3.2. The original method for finding an FSI(1) minimum in [24] was to formulate the best interchange as the following best interchange MIP (BI-MIP) and apply it iteratively as in Algorithm 4. We will show that CG obtains results comparable to those from FSI(1), but without requiring the use of sophisticated integer programming software. BI-MIP: \[\min\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{i})^{2},\] (5) subject to \[-Mz_{i}\leq\theta_{i}\leq Mz_{i},\quad\forall i\in[p],\] (6) \[z_{i}\leq w_{i},\quad\forall i\in S,\] (7) \[\sum_{i\in S^{c}}z_{i}\leq 1,\] (8) \[\sum_{i\in S}w_{i}\leq|S|-1,\] (9) \[\theta_{i}\in\mathbb{R},\quad\forall i\in[p],\] (10) \[z_{i}\in\{0,1\},\quad\forall i\in[p],\] (11) \[w_{i}\in\{0,1\},\quad\forall i\in S.\] (12)  
Here, we start from an initial set \(S\) and try to find a best interchange between a variable inside \(S\) and a variable outside \(S\). The decision variables are \(\theta,w\), and \(z\). \(z_{i}\)s indicate the nonzeros in \(\theta\), i.e., if \(z_{i}=0\), then \(\theta_{i}=0\). \(w_{i}\)'s indicate whether we remove variable \(i\) from \begin{table}
\begin{tabular}{l l l l l} \hline \hline  & \multicolumn{1}{c}{\(k=7\)} & \multicolumn{3}{c}{\(k=15\)} \\  & RSS & Time (s) & RSS & Time (s) \\ \hline Stepwise regression & 1,653,208 & 5.55 & 1,029,899 & 16.08 \\ CG with stepwise initialization & 1,471,932 & 28.45 & 973,695 & 97.82 \\ CG with random initialization (average over 10 experiments) & 1,471,932 & 13.52 & 972,886 & 100.44 \\ (min RSS over 10 experiments) & 1,471,932 & 970,712 & \\ CG with random initialization (average over 5 experiments) & 1,471,932 & 16.88 & 972,674 & 96.32 \\ (min RSS over 5 experiments) & 1,471,932 & & 970,712 & \\ \hline  & \multicolumn{1}{c}{\(k=25\)} & \multicolumn{3}{c}{\(k=50\)} \\  & RSS & Time (s) & RSS & Time (s) \\ \hline Stepwise regression & 829,608 & 38.45 & 623,118 & 132.24 \\ CG with stepwise initialization & 791,960 & 440.14 & 609,722 & 1409.88 \\ CG with random initialization (average over 10 experiments) & 791,581 & 300.25 & 612,304 & 1057.20 \\ (min RSS over 10 experiments) & 788,836 & & 606,865 & \\ CG with random initialization (average over 5 experiments) & 791,380 & 273.90 & 612,404 & 1120.17 \\ (min RSS over 5 experiments) & 788,836 & & 606,865 & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: CG with stepwise initialization and random initialization for the CT slice dataset. Figure 6: Improvements from carousel greedy with random initialization for the Insurance dataset. \(S\), i.e., if \(w_{i}=0\), then variable \(i\) is removed from \(S\). \([p]\) is defined to be the set \(\{1,2,\ldots,p\}\). In (5), we seek to minimize RSS. In (6), for every \(i\in[p]\), \(z_{i}=1\) if \(\theta_{i}\) is nonzero and \(M\) is a sufficiently large constant. From (7), we see that if variable \(i\) is removed, then \(\theta_{i}\) must be zero. Inequality (8) means that the number of selected variables outside \(S\) is at most 1, i.e., we add at most 1 variable to \(S\). From (9), we see that we remove at least 1 variable from \(S\) (the optimal solution removes exactly 1 variable). In Algorithm 4 for finding an FSI(1) minimum, we solve BI-MIP iteratively until an iteration does not yield any improvement. The pseudo-code is as follows:  
```
1:Initialize \(|S|=k\) by forward stepwise regression with coefficients \(\theta\)
2:while TRUE do
3:\(S^{\prime}\leftarrow\) Apply BI-MIP to \(S\)
4:if RSS of \(S^{\prime}\geq\) RSS of \(S\)then
5: Break
6:endif
7:\(S=S^{\prime}\)
8:endwhile
9:return \(S\)
```  
**Algorithm 4** Pseudo-code of finding an FSI(1) local minimum by Gurobi. Recall that our default version of CG also returns an FSI(1) local minima. The solutions of the two methods are expected to return equally good solutions on average. We begin with a comparison on the CT slice dataset.