Mathematics – Statistics Theory
Scientific paper
2007-08-16
Annals of Statistics 2007, Vol. 35, No. 2, 870-887
Mathematics
Statistics Theory
Published at http://dx.doi.org/10.1214/009053606000001334 in the Annals of Statistics (http://www.imstat.org/aos/) by the Inst
Scientific paper
10.1214/009053606000001334
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 $C_p$, 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.
Huo Xiaoming
Ni
Xuelei
No associations
LandOfFree
When do stepwise algorithms meet subset selection criteria? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with When do stepwise algorithms meet subset selection criteria?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When do stepwise algorithms meet subset selection criteria? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-331583