Introduction to High-Dimensional Statistics, 2nd Edition

Chapter 5

Convex Criteria

DOI: 10.1201/9781003158745-5

We have seen in Chapter 2 that the model selection procedure (2.9), page 35, 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 high-dimensional 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 ...