Open problem: Restricted eigenvalue condition for heavy tailed designs

Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar

Research output: Contribution to journalConference articlepeer-review


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 small-ball 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 high-dimensional estimators for heavy tailed problems.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Issue number2015
StatePublished - 2015
Externally publishedYes
Event28th Conference on Learning Theory, COLT 2015 - Paris, France
Duration: Jul 2 2015Jul 6 2015

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Open problem: Restricted eigenvalue condition for heavy tailed designs'. Together they form a unique fingerprint.

Cite this