[Sds-seminars] S&DS In-Person Seminar, Ilias Zadik, 2/23, 10:30am-11:30am @ DL220, "The price of computational efficiency in high-dimensional estimation"

[elizavette.torres at yale.edu]

 <https://statistics.yale.edu/>     <https://statistics.yale.edu/>
Department of Statistics and Data Science  


 <https://statistics.yale.edu/seminars/ilias-zadik> Ilias Zadik, MIT


Date: Thursday, February 23, 2023

Time: 10:30AM to 11:30AM

Dunham Lab. Room 220 

10 Hillhouse Avenue, 2nd Floor

New Haven

 <https://iliaszadik.github.io/> Website

 

 

Title: The price of computational efficiency in high-dimensional estimation

 

Information and Abstract: 

In recent years we have experienced a remarkable growth on the number and
size of available datasets. Such growth has led to the intense and
challenging pursuit of estimators which are provably both computationally
efficient and statistically accurate. Notably, the analysis of
polynomial-time estimators has revealed intriguing phenomena in several high
dimensional estimation tasks, such as their apparent failure of such
estimators to reach the optimal statistical guarantees achieved among all
estimators (that is the presence of a non-trivial "computational-statistical
trade-off"). 

In this talk, I will present new such algorithmic results for the
well-studied planted clique model and for the fundamental sparse regression
model. For planted clique, we reveal the surprising severe failure of the
Metropolis process to work in polynomial-time, even when simple degree
heuristics succeed. In particular, our result resolved a well-known 30-years
old open problem on the performance of the Metropolis process for the model,
posed by Jerrum in 1992. For sparse regression, we show the failure of large
families of polynomial-time estimators, such as MCMC and low-degree
polynomial methods, to improve upon the best-known polynomial-time
regression methods. As an outcome, our work offers rigorous evidence that
popular regression methods such as LASSO are optimally balancing their
computational and statistical recourses.

 

 

For more details and upcoming events visit our website at
<http://statistics.yale.edu/> http://statistics.yale.edu/

 

Department of Statistics and Data Science

Yale University
24 Hillhouse Avenue
New Haven, CT 06511

t 203.432.0666
f 203.432.0633

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20230222/17fd5361/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 2925 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20230222/17fd5361/attachment.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.jpg
Type: image/jpeg
Size: 28109 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20230222/17fd5361/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 5211 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20230222/17fd5361/attachment-0002.jpg>