Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs

Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar
Proceedings of The 28th Conference on Learning Theory, PMLR 40:1752-1755, 2015.

Abstract

The restricted eigenvalue (RE) condition characterizes the sample complexity of accurate recovery in the context of high-dimensional estimators such as Lasso and Dantzig selector (Bickel et al., 2009). Recent work has shown that random design matrices drawn from any thin-tailed (sub-Gaussian) distributions satisfy the RE condition with high probability, when the number of samples scale as the square of the Gaussian width of the restricted set (Banerjee et al., 2014; Tropp, 2015). We pose the equivalent question for heavy-tailed distributions: Given a random design matrix drawn from a heavy-tailed distribution satisfying the smallball property (Mendelson, 2015), does the design matrix satisfy the RE condition with the same order of sample complexity as sub-Gaussian distributions? An answer to the question will guide the design of highdimensional estimators for heavy tailed problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Banerjee15, title = {Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs}, author = {Banerjee, Arindam and Chen, Sheng and Sivakumar, Vidyashankar}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1752--1755}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Banerjee15.pdf}, url = {https://proceedings.mlr.press/v40/Banerjee15.html}, abstract = {The restricted eigenvalue (RE) condition characterizes the sample complexity of accurate recovery in the context of high-dimensional estimators such as Lasso and Dantzig selector (Bickel et al., 2009). Recent work has shown that random design matrices drawn from any thin-tailed (sub-Gaussian) distributions satisfy the RE condition with high probability, when the number of samples scale as the square of the Gaussian width of the restricted set (Banerjee et al., 2014; Tropp, 2015). We pose the equivalent question for heavy-tailed distributions: Given a random design matrix drawn from a heavy-tailed distribution satisfying the smallball property (Mendelson, 2015), does the design matrix satisfy the RE condition with the same order of sample complexity as sub-Gaussian distributions? An answer to the question will guide the design of highdimensional estimators for heavy tailed problems.} }
Endnote
%0 Conference Paper %T Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs %A Arindam Banerjee %A Sheng Chen %A Vidyashankar Sivakumar %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Banerjee15 %I PMLR %P 1752--1755 %U https://proceedings.mlr.press/v40/Banerjee15.html %V 40 %X The restricted eigenvalue (RE) condition characterizes the sample complexity of accurate recovery in the context of high-dimensional estimators such as Lasso and Dantzig selector (Bickel et al., 2009). Recent work has shown that random design matrices drawn from any thin-tailed (sub-Gaussian) distributions satisfy the RE condition with high probability, when the number of samples scale as the square of the Gaussian width of the restricted set (Banerjee et al., 2014; Tropp, 2015). We pose the equivalent question for heavy-tailed distributions: Given a random design matrix drawn from a heavy-tailed distribution satisfying the smallball property (Mendelson, 2015), does the design matrix satisfy the RE condition with the same order of sample complexity as sub-Gaussian distributions? An answer to the question will guide the design of highdimensional estimators for heavy tailed problems.
RIS
TY - CPAPER TI - Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs AU - Arindam Banerjee AU - Sheng Chen AU - Vidyashankar Sivakumar BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Banerjee15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 1752 EP - 1755 L1 - http://proceedings.mlr.press/v40/Banerjee15.pdf UR - https://proceedings.mlr.press/v40/Banerjee15.html AB - The restricted eigenvalue (RE) condition characterizes the sample complexity of accurate recovery in the context of high-dimensional estimators such as Lasso and Dantzig selector (Bickel et al., 2009). Recent work has shown that random design matrices drawn from any thin-tailed (sub-Gaussian) distributions satisfy the RE condition with high probability, when the number of samples scale as the square of the Gaussian width of the restricted set (Banerjee et al., 2014; Tropp, 2015). We pose the equivalent question for heavy-tailed distributions: Given a random design matrix drawn from a heavy-tailed distribution satisfying the smallball property (Mendelson, 2015), does the design matrix satisfy the RE condition with the same order of sample complexity as sub-Gaussian distributions? An answer to the question will guide the design of highdimensional estimators for heavy tailed problems. ER -
APA
Banerjee, A., Chen, S. & Sivakumar, V.. (2015). Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:1752-1755 Available from https://proceedings.mlr.press/v40/Banerjee15.html.

Related Material