[Sds-seminars] [Sds-announce] Thursday at 10:30: Ilias Zadik on "The price of computational efficiency in high-dimensional estimation"

Dan Spielman daniel.spielman at yale.edu
Tue Feb 21 15:32:29 EST 2023


ILIAS ZADIK, MIT
The price of computational efficiency in high-dimensional estimation
Thursday, February 23, 202310:30AM to 11:30AM
Dunham Lab. Room 220 see map
<http://maps.google.com/?q=10+Hillhouse+Avenue%2C+2nd+Floor%2C+New+Haven%2C+%2C+%2C+us>

10 Hillhouse Avenue, 2nd Floor
New Haven
Website <https://iliaszadik.github.io/>
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20230221/53be04dd/attachment.html>
-------------- next part --------------
-- 
Sds-announce mailing list
Sds-announce at mailman.yale.edu
https://mailman.yale.edu/mailman/listinfo/sds-announce


More information about the Sds-seminars mailing list