Three topics in variable selection

Many variable selection algorithms in data mining utilize ranking and thresholding predictors as a principle due to its scalability and simplicity. Most ranking methods, however, rely on the assumption of the data independence. It might be misleading if dependence and heteroscedasticity, which are prevalent in real world data, are ignored. Instead of assuming completely (conditionally) independence, we capture the potential data dependency via a block-wise way. Through this view, I propose two approaches, the GEE approach and the Tukey approach, to handle the dependency and heteroscedasticity. In addition, I show that these two approaches are asymptotically equivalent under mild assumptions. I applied this idea to the Netflix data for the KDD cup competition in 2007, in which a time-consistent polynomial distributed lag model was built via the simpler Tukey approach. The model is simple and effective and can be easily generalized to apply to a variety of data. In the past decade, a rich literature has been developed using l1-regularization. We however have found that in problems with real sparsity, the l0 proxy algorithm, stepwise regression, could outperform l1 algorithms. Which one provides better solutions: the approximation to the correct problem, or the exact algorithm for the relaxed problems? I provided an extensive comparison of these algorithms from several perspectives and studied theoretically the minimax risk ratios, showing that while using an l1 penalty never outperforms using an l0 penalty by more than a constant factor, in some cases using an l1 penalty is infinitely worse than using an l0 penalty. Fast algorithms are highly desirable for modeling massive datasets. I propose a fast regression algorithm that can substantially reduce the computational complexity of searching, yet retain good accuracy. It also guarantees to discover correlated features that are collectively predictive, and avoid model over-fitting. Its capability of controlling mFDR (marginal False Discovery Rate) statistically enables the one-pass search of the fast algorithm and guarantees the accuracy of the sparse model chosen by the algorithm without cross validation. Numerical results show that our algorithm is much faster than any other algorithm and is competitively as accurate as the best but slower algorithms