Timezone: »

 
Poster
Beyond Sub-Gaussian Measurements: High-Dimensional Structured Estimation with Sub-Exponential Designs
Vidyashankar Sivakumar · Arindam Banerjee · Pradeep Ravikumar

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #99
in Poster Session »
We consider the problem of high-dimensional structured estimation with norm-regularized estimators, such as Lasso, when the design matrix and noise are drawn from sub-exponential distributions.Existing results only consider sub-Gaussian designs and noise, and both the sample complexity and non-asymptotic estimation error have been shown to depend on the Gaussian width of suitable sets. In contrast, for the sub-exponential setting, we show that the sample complexity and the estimation error will depend on the exponential width of the corresponding sets, and the analysis holds for any norm. Further, using generic chaining, we show that the exponential width for any set will be at most $\sqrt{\log p}$ times the Gaussian width of the set, yielding Gaussian width based results even for the sub-exponential case. Further, for certain popular estimators, viz Lasso and Group Lasso, using a VC-dimension based analysis, we show that the sample complexity will in fact be the same order as Gaussian designs. Our general analysis and results are the first in the sub-exponential setting, and are readily applicable to special sub-exponential families such as log-concave and extreme-value distributions.
[ PDF] 

Author Information

Vidyashankar Sivakumar (UNIVERSITY OF MINNESOTA, TC)
Arindam Banerjee (University of Minnesota)

Arindam Banerjee is a Professor at the Department of Computer & Engineering and a Resident Fellow at the Institute on the Environment at the University of Minnesota, Twin Cities. His research interests are in machine learning, data mining, and applications in complex real-world problems in different areas including climate science, ecology, recommendation systems, text analysis, and finance. He has won several awards, including the NSF CAREER award (2010), the IBM Faculty Award (2013), and six best paper awards in top-tier conferences.

Pradeep Ravikumar (University of Texas at Austin)

More from the Same Authors