Regularity properties for sparse regression

Edgar Dobriban Jianqing Fan

Statistics Theory and Methods mathscidoc:1912.43413

Communications in mathematics and statistics, 4, (1), 1-19, 2016.3
Statistical and machine learning theory has developed several conditions ensuring that popular estimators such as the Lasso or the Dantzig selector perform well in high-dimensional sparse regression, including the restricted eigenvalue, compatibility, and q sensitivity properties. However, some of the central aspects of these conditions are not well understood. For instance, it is unknown if these conditions can be checked efficiently on any given dataset. This is problematic, because they are at the core of the theory of sparse regression. Here we provide a rigorous proof that these conditions are NP-hard to check. This shows that the conditions are computationally infeasible to verify, and raises some questions about their practical applications. However, by taking an average-case perspective instead of the worst-case view of NP-hardness, we show that a particular condition, q sensitivity, has certain
No keywords uploaded!
[ Download ] [ 2019-12-21 11:42:54 uploaded by Jianqing_Fan ] [ 108 downloads ] [ 0 comments ]
  title={Regularity properties for sparse regression},
  author={Edgar Dobriban, and Jianqing Fan},
  booktitle={Communications in mathematics and statistics},
Edgar Dobriban, and Jianqing Fan. Regularity properties for sparse regression. 2016. Vol. 4. In Communications in mathematics and statistics. pp.1-19.
Please log in for comment!
Contact us: | Copyright Reserved