ABSTRACT
We have seen in Chapter 2 that the model selection procedure (2.9) has some nice statistical properties but suffers from a prohibitive computational cost in many cases. For example, in the coordinate-sparse setting, the algorithmic complexity for computing (2.9) is exponential in p, so it cannot be implemented in moderate or highdimensional settings. To circumvent this issue, a standard trick is to derive from the NP-hard problem (2.9) a convex criterion that can be minimized efficiently. The main point is then to check that the estimator derived from this convex criterion is almost as good as the estimator (2.9), at least for some classes of matrix X. This chapter is devoted to this issue and to some related computational aspects.
