# Carousel Greedy Algorithms for Feature Selection in Linear Regression
## 2 Linear Regression and Feature Selection  
The rigorous mathematical definition of the problem is:  
\[\min_{\theta}RSS=\sum_{i=1}^{n}(\sum_{j=1}^{p}X_{ij}\theta_{j}-y_{i})^{2}, \tag{1}\]  
\[\text{subject to}\ \sum_{j=1}^{p}I_{\theta_{j}\
eq 0}\leq k, \tag{2}\]  
where the following notation applies:  
\(RSS\): the residual sum of squares,  
\(X\in\mathbb{R}^{n\times p}\): the independent variables,  
\(X_{ij}\): the \(i^{th}\) row and \(j^{th}\) column of \(X\),  
\(y\in\mathbb{R}^{n}\): the dependent variable,  
\(y_{i}\): the \(i^{th}\) element of \(y\), \begin{table}
\begin{tabular}{l c c} \hline \hline
**Year** & **Problem** & **Authors** \\ \hline
2023 & Knapsack Problem with Forfeits & [PERSON] et al. [2] \\ \hline
2022 & Knapsack Problem with Forfeits & [PERSON] et al. [3] \\ \hline
2022 & Maximum Network Lifetime Problem with Time Slots and Coverage Constraints & [PERSON] et al. [4] \\ \hline
2021 & Grocery Distribution Plans in Urban Networks with Street Crossing Penalties & [PERSON] et al. [5] \\ \hline
2021 & Finding Minimum Positive Influence Dominating Sets in Social Networks & [PERSON] et al. [6] \\ \hline
2020 & Knapsack Problem with Forfeits & [PERSON] et al. [7] \\ \hline
2020 & Remote Sensing with Unmanned Aerial Vehicles (UAVs) & [PERSON] et al. [8] \\ \hline
2020 & Close-Enough Traveling Salesman Problem & [PERSON] et al. [9] \\ \hline
2019 & Community Detection in Complex Networks & [PERSON] et al. [10] \\ \hline
2019 & Strong Generalized Minimum Labeling Spanning Tree Problem & [PERSON] et al. [11] \\ \hline
2019 & Sentiment Analysis & [PERSON] et al. [12] \\ \hline
2018 & A Distribution Problem & [PERSON] et al. [13] \\ \hline
2017 & Maximum Network Lifetime Problem with Interference Constraints & [PERSON] et al. [14] \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Recent applications of CG. \(\theta\in\mathbb{R}^{p}\): the coefficient vector of explanatory variables, \(\theta_{j}\): the \(j^{th}\) element of \(\theta\), \(n\): the number of observations, \(p\): the total number of explanatory variables (features), \(k\): the number of explanatory variables we want in the model, and \(I_{\theta_{j},\
eq 0}\): equals 1 if \(\theta_{j}\
eq 0\) is true and 0 otherwise. While we use RSS (i.e., OLS or ordinary least squares) as the objective function, other criteria, such as AIC (15), \(C_{p}\)(16), BIC (17), and RIC (18), are possible. We point out that our goal in this paper is quite focused. We do not consider the other criteria mentioned above. In addition, we do not separate the data into training, test, and validation sets as is commonly the case in machine learning models. Rather, we concentrate on minimizing RSS over the training set. This is fully compatible with the objective in linear regression and best subset selection. There are three general approaches to solving the problem in (1) and (2). We summarize them below. 1. Best subset selection. This direct approach typically uses mixed integer optimization (MIO). It has been championed in articles by [PERSON] and his colleagues (19; 20). Although MIO solvers have become very powerful in the last few decades and they can solve problems much faster than in the past, running times can still become too large for many real-world datasets. [PERSON] et al. (2018) has recently proposed a polynomial time algorithm, but it requires some mild conditions on the dataset and it works with high probability, but not always. 2. Regularization. This approach was initially used to address overfitting in unconstrained regression so that the resulting model would behave in a _regular_ way. In this approach, the constraints are moved into the objective function with a penalty term. Regularization is a widely used method because of its speed and high performance in making predictions on test data.