BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//MIT Statistics and Data Science Center - ECPv4.6//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:MIT Statistics and Data Science Center
X-ORIGINAL-URL:https://stat.mit.edu
X-WR-CALDESC:Events for MIT Statistics and Data Science Center
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20181207T110000
DTEND;TZID=America/New_York:20181207T120000
DTSTAMP:20181212T234227
CREATED:20180620T214409Z
LAST-MODIFIED:20181130T173612Z
UID:2699-1544180400-1544184000@stat.mit.edu
SUMMARY:Reducibility and Computational Lower Bounds for Some High-dimensional Statistics Problems
DESCRIPTION: Abstract: The prototypical high-dimensional statistics problem entails finding a structured signal in noise. Many of these problems exhibit an intriguing phenomenon: the amount of data needed by all known computationally efficient algorithms far exceeds what is needed for inefficient algorithms that search over all possible structures. A line of work initiated by Berthet and Rigollet in 2013 has aimed to explain these gaps by reducing from conjecturally hard problems in computer science. However\, the delicate nature of average-case reductions has limited the applicability of this approach. In this work we introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture. These include tight lower bounds for Planted Independent Set\, Planted Dense Subgraph\, Biclustering\, Sparse Spiked Wigner\, Sparse PCA\, as well as for new models we introduce. Joint work with Matthew Brennan and Wasim Huleihel. \n Bio: Guy Bresler is an assistant professor in the Department of Electrical Engineering and Computer Science at MIT\, and a member of LIDS and IDSS.\nPreviously\, he was a postdoc at MIT and before that received his PhD from the Department of EECS at UC Berkeley.\nHe seeks to obtain engineering insight into practically relevant problems by formulating and solving mathematical models. Concretely\, he wants to understand the relationship between combinatorial structure and computational tractability of high-dimensional inference in the context of graphical models and other statistical models\, recommendation systems\, and biology. \n
URL:https://stat.mit.edu/calendar/guy-bresler/
LOCATION:50 Ames Street\, Cambridge\, MA\, 02139
GEO:42.3620185;-71.0878444
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=50 Ames Street Cambridge MA 02139;X-APPLE-RADIUS=500;X-TITLE=50 Ames Street:geo:-71.0878444,42.3620185
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
END:VCALENDAR