2013/10/22 by Piotr Pokarowski, Pokarowski, Piotr, Jan Mielniczuk +1 · 1 citation
Computer Science · Engineering · Mathematics · #Bayesian Methods and Mixture Models #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical Methods and Bayesian Inference #Statistical Methods and Inference #stat.ML
paper · pdf · doi:10.48550/arxiv.1310.6062
arxiv created 2013/10/22 · openalex publication_date 2013/10/22 · arxiv updated 2013/10/24 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
We introduce a computationally effective algorithm for a linear model selection consisting of three steps: screening--ordering--selection (SOS). Screening of predictors is based on the thresholded Lasso that is l1 penalized least squares. The screened predictors are then fitted using least squares (LS) and ordered with respect to their t statistics. Finally, a model is selected using greedy generalized information criterion (GIC) that is l0 penalized LS in a nested family induced by the ordering. We give non-asymptotic upper bounds on error probability of each step of the SOS algorithm in terms of both penalties. Then we obtain selection consistency for different (n, p) scenarios under conditions which are needed for screening consistency of the Lasso. For the traditional setting (n >p) we give Sanov-type bounds on the error probabilities of the ordering--selection algorithm. Its surprising consequence is that the selection error of greedy GIC is asymptotically not larger than of exhaustive GIC. We also obtain new bounds on prediction and estimation errors for the Lasso which are proved in parallel for the algorithm used in practice and its formal version.