# Carousel Greedy Algorithms for Feature Selection in Linear Regression
## 2 Linear Regression and Feature Selection
The most famous regularized model, lasso (22), uses the \(L^{1}\)-penalty as shown below: \[\min_{\theta}\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{i})^{2}+\lambda \sum_{j=1}^{p}|\theta_{j}|.\] (3) As \(\lambda\) becomes larger, it will prevent \(\theta\) from having a large \(L^{1}\)-norm. At the same time, the number of nonzero \(\theta_{i}\) values will also become smaller. For any \(k\), there exists a \(\lambda\) such that the number of nonzero \(\theta_{i}\) values is roughly \(k\), but the number can sometimes jump sharply. This continuous optimization model is very fast, but there are some disadvantages. Some follow-up papers using ideas such as adaptive lasso (23), L0 Learn (24), trimmed lasso (25), elastic net (26), and MC+ (27) appear to improve the model by modifying the penalty term. Specifically, L0 Learn (24) uses the \(L^{0}\)-penalty as shown below: \[\min_{\theta}\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{i})^{2}+\lambda \sum_{j=1}^{p}I_{\theta_{j}\
eq 0}.\] (4) For sparse high-dimensional regression, some authors (28; 29) use \(L^{2}\) regularization without removing the cardinality constraint. 3. Heuristics. Since the subset selection problem is hard to solve optimally, a compromise would be to find a very good solution quickly using a heuristic approach. Stepwise regression is a widely used heuristic for this problem. An alternating method that can achieve a so-called partial minimum is presented in (30). SparseNet (31) provides a coordinate-wise optimization algorithm. CG is another heuristic approach. One idea is to apply CG from a random selection of predictor variables. An alternative is to apply CG to the result of stepwise regression in order to improve the solution. We might expect the latter to outperform MIO in terms of running time, but not in termsof solution quality. In our computational experiments, we will compare approaches with respect to RSS on training data only. There are different variants of the problem specified in (1) and (2). We can restrict the number of variables to be at most \(k\), as in (1) and (2). Alternatively, we can restrict the number of variables to be exactly \(k\). Finally, we can solve an unrestricted version of the problem. We point out that when we minimize \(RSS\) over training data only, it always helps to add another variable. Therefore, when the model specifies there will be at most \(k\) variables, the solution will involve exactly \(k\) variables. In response to the exciting recent work in [19; 20] on the application of highly sophisticated MIO solvers (e.g., Gurobi) to solve the best subset regression problem posed in (1) and (2), [PERSON] et al. [32] have published an extensive computational comparison in which best subset selection, forward stepwise selection, and lasso are evaluated on synthetic data. The authors used both a training set and a test set in their experiments. They implemented the mixed integer quadratic program from [20] and made the resulting R code available in [32]. They found that best subset selection and lasso work well, but neither dominates the other. Furthermore, a relaxed version of lasso created by [PERSON] [33] is the overall winner. Our goal in this paper is to propose a smart heuristic to solve the regression problem where \(k\) is fixed in advance. The heuristic should be easy to understand, code, and use. It should have a reasonably fast running time, although it will require more time than stepwise regression. We expect that for large \(k\), it will be faster than best subset selection. In this paper, we will test our ideas on the three real-world datasets from the UCI ML Repository (see [[https://archive.ics.uci.edu/](https://archive.ics.uci.edu/)]([https://archive.ics.uci.edu/](https://archive.ics.uci.edu/)), accessed on 11 April 2023) listed below:  
1. CT (Computerized Tomography) Slice Dataset: \(n\) = 10,001, \(p=384\);  
2. Building Dataset: \(n=372\), \(p=107\); and  
3. Insurance Dataset: \(n=9822\), \(p=85\).