When do stepwise algorithms meet subset selection criteria

Recent results in homotopy and solution paths demonstrate that certain well-designed greedy algorithms, with a range of values of the algorithmic parameter, can provide solution paths to a sequence of convex optimization problems. On the other hand, in regression many existing criteria in subset selection (including Cp, AIC, BIC, MDL, RIC, etc.) involve optimizing an objective function that contains a counting measure. The two optimization problems are formulated as (P1) and (P0) in the present paper. The latter is generally combinatoric and has been proven to be NP-hard. We study the conditions under which the two optimization problems have common solutions. Hence, in these situations a stepwise algorithm can be used to solve the seemingly unsolvable problem. Our main result is motivated by recent work in sparse representation, while two others emerge from different angles: a direct analysis of sufficiency and necessity and a condition on the mostly correlated covariates. An extreme example connected with least angle regression is of independent interest.

• Publication year

  2007

• Venue

  Annals of Statistics

• Publication date

  2007-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/009053606000001334arXiv 0708.2149
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the “degrees of freedom” of the lasso

  2007cited by this paper
• Just relax: convex programming methods for identifying sparse signals in noise

  2006influential reference
• Statistical Challenges with High Dimensionality: Feature Selection in Knowledge Discovery

  2006cited by this paper
• Stable recovery of sparse overcomplete representations in the presence of noise

  2006cited by this paper
• Exploring Multivariate Data With the Forward Search

  2006cited by this paper
• The Adaptive Lasso and Its Oracle Properties

  2006cited by this paper
• A simple test to check the optimality of sparse signal approximations

  2005influential reference
• Sparse representations for multiple measurement vectors (MMV) in an over-complete dictionary

  2005cited by this paper
• Homotopy continuation for sparse signal representation

  2005influential reference
• New results in detection, estimation, and model selection

  2005cited by this paper
• [Least Angle Regression]: Discussion

  2004influential reference
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2004cited by this paper
• JUST RELAX: CONVEX PROGRAMMING METHODS FOR SUBSET SELECTION AND SPARSE APPROXIMATION

  2004cited by this paper
• Discussion of "Least Angle Regression" by Efron, Hastie, Johnstone and Tibshirani

  2004cited by this paper
• The Entire Regularization Path for the Support Vector Machine

  2004cited by this paper
• Nonconcave penalized likelihood with a diverging number of parameters

  2004cited by this paper
• On sparse representations in arbitrary redundant bases

  2004cited by this paper
• The Estimation of Prediction Error

  2004cited by this paper
• Greed is good: algorithmic results for sparse approximation

  2004cited by this paper
• Model Uncertainty

  2003cited by this paper
• Sparse representations in unions of bases

  2003cited by this paper
• Discussion of Least Angle Regression

  2003cited by this paper
• Model selection and multimodel inference : a practical information-theoretic approach

  2003cited by this paper
• Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach (2nd ed.)

  2003cited by this paper
• Approximation of functions over redundant dictionaries using coherence

  2003cited by this paper
• Optimally sparse representation in general (nonorthogonal) dictionaries via l minimization.

  2003cited by this paper
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization

  2003cited by this paper
• Adaptive Model Selection

  2002cited by this paper
• A branch and bound algorithm for computing the best subset regression models

  2002cited by this paper
• A generalized uncertainty principle and sparse representation in pairs of bases

  2002cited by this paper
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties

  2001cited by this paper
• Uncertainty principles and ideal atomic decomposition

  2001cited by this paper
• A new approach to variable selection in least squares problems

  2000influential reference
• On the LASSO and its Dual

  2000influential reference
• Some Comments on Cp

  2000influential reference
• On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem

  2000cited by this paper
• Regressions by Leaps and Bounds

  2000cited by this paper
• The Variable Selection Problem

  2000influential reference
• A wavelet tour of signal processing

  1998cited by this paper
• On Measuring and Correcting the Effects of Data Mining and Model Selection

  1998cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• Feature Selection: Evaluation, Application, and Small Sample Performance

  1997cited by this paper
• Wrappers for Feature Subset Selection

  1997cited by this paper
• Some remarks on greedy algorithms

  1996cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996influential reference
• Matrix computations (3rd ed.)

  1996cited by this paper
• The Interpretation of Mallows's CP‐Statistic

  1996influential reference
• Adapting to Unknown Smoothness via Wavelet Shrinkage

  1995cited by this paper
• Consistent Variable Selection in Linear Models

  1995cited by this paper
• Sparse Approximate Solutions to Linear Systems

  1995cited by this paper
• More comments on C p

  1995influential reference
• Basis pursuit

  1994influential reference
• Adaptive time-frequency decompositions

  1994cited by this paper
• The risk inflation criterion for multiple regression

  1994cited by this paper
• Construction of supersaturated designs through partially aliased interactions

  1993cited by this paper
• Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

  1993cited by this paper
• Subset Selection in Regression

  1992cited by this paper
• An Improved Branch and Bound Algorithm for Feature Subset Selection

  1988cited by this paper
• Linear inversion of ban limit reflection seismograms

  1986cited by this paper
• Finite Algorithms in Optimization and Data Analysis

  1986cited by this paper
• Finite Algorithms in Optimization and Data Analysis

  1985influential reference
• Algorithm AS 199: A Branch and Bound Algorithm for Determining the Optimal Feature Subset of Given Size

  1984cited by this paper
• Matrix computations

  1983cited by this paper
• Estimating the Dimension of a Model

  1978cited by this paper
• A Branch and Bound Algorithm for Feature Subset Selection

  1977cited by this paper
• Some comments on C_p

  1973cited by this paper
• Information Theory and an Extension of the Maximum Likelihood Principle

  1973influential reference
• Discussion on

  1908cited by this paper
• © Institute of Mathematical Statistics, 2004 LEAST ANGLE REGRESSION

  year unknowninfluential reference

• Automated subset selection via information criteria optimization in generalized linear models

  2024cites this paper
• A comparative study of augmented inverse propensity weighted estimators using outcome-oriented covariate selection via penalization with outcome-adaptive lasso

  2024cites this paper
• Collection of theses

  2023cites this paper
• Learning From Limited Temporal Data: Dynamically Sparse Historical Functional Linear Models With Applications to Earth Science

  2023cites this paper
• High-dimensional sparse index tracking based on a multi-step convex optimization approach

  2023cites this paper
• Feature selection algorithms in generalized additive models under concurvity

  2022cites this paper
• Variable Selection for the Spatial Autoregressive Model with Autoregressive Disturbances

  2021cites this paper
• Randomized boosting with multivariable base-learners for high-dimensional variable selection and prediction

  2021cites this paper
• A provable two-stage algorithm for penalized hazards regression

  2021cites this paper
• Stable Anatomy Detection in Multimodal Imaging Through Sparse Group Regularization: A Comparative Study of Iron Accumulation in the Aging Brain

  2021cites this paper
• The relational side of intellectual capital: an empirical study on brand value evaluation and financial performance

  2020cites this paper
• High-dimensional variable selection via low-dimensional adaptive learning

  2019cites this paper
• NP-hardness of ℓ0 minimization problems: revision and extension to the non-negative setting

  2019influential citation
• Significant Anatomy Detection Through Sparse Classification: A Comparative Study

  2018cites this paper
• A penalized quasi-maximum likelihood method for variable selection in the spatial autoregressive model

  2018cites this paper
• Hard thresholding regression

  2018cites this paper
• A Fast Reduced-Space Algorithmic Framework for Sparse Optimization

  2018cites this paper
• Achieving the oracle property of OEM with nonconvex penalties

  2017cites this paper
• Entropic uncertainty inequalities on sparse representation

  2016cites this paper
• Near optimal representative subset selection from short sequences generated by a stationary source

  2016cites this paper
• Identification of Cell Type-Specific Differences in Erythropoietin Receptor Signaling in Primary Erythroid and Lung Cancer Cells

  2016cites this paper
• I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.

  2015cites this paper
• Bayesian feature selection for high-dimensional linear regression via the Ising approximation with applications to genomics

  2015cites this paper
• Variable selection in linear models

  2014cites this paper
• On High Dimensional Sparse Regression and Its Inference

  2014cites this paper
• Map estimation for Bayesian mixture models with submodular priors

  2014cites this paper
• Hard Thresholded Regression Via Linear Programming

  2014cites this paper
• New inequalities on sparse representation in pairs of bases

  2013cites this paper
• Forward Selection Procedure for Linear Model Building Using Spearman’s Rank Correlation

  2012influential citation
• Orthogonalizing Penalized Regression

  2011cites this paper
• On best subset regression

  2011cites this paper
• OEM for least squares problems

  2011cites this paper
• Versuchsplanung und Methoden zur Identifikation zeitkontinuierlicher Zustandsraummodelle am Beispiel des Verbrennungsmotors

  2011cites this paper
• A Model Selection Method for Nonlinear System Identification Based fMRI Effective Connectivity Analysis

  2011cites this paper
• Regularization for Sparseness and Smoothness : Applications in System Identification and Signal Processing

  2010cites this paper
• A least angle regression method for fMRI activation detection in phase-encoded experimental designs

  2010cites this paper
• Group Variable Selection Methods and Their Applications in Analysis of Genomic Data

  2010cites this paper
• Graphical model structure learning using L₁-regularization

  2010cites this paper
• Two Conditions for Equivalence of 0-Norm Solution and 1-Norm Solution in Sparse Representation

  2010cites this paper
• Complexity of penalized likelihood estimation

  2010influential citation
• Greedy and Relaxed Approximations to Model Selection : A simulation study

  2008cites this paper
• Theoretical results and applications related to dimension reduction

  2007influential citation
• SOME RECENT RESULTS IN MODEL SELECTION

  2007cites this paper
• Advances in variable selection and visualization methods for analysis of multivariate data

  2007influential citation
• Regressions by Enhanced Leaps-and-Bounds via Additional Optimality Tests (LBOT)

  2006cites this paper
• Hardness on Numerical Realization of Some Penalized Likelihood Estimators

  2006cites this paper
• New results in detection, estimation, and model selection

  2005cites this paper
• A comparative study of augmented inverse propensity weighted estimators using outcome-adaptive lasso and other penalized regression methods

  year unknowncites this paper