BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Lecture / Talk / Workshop
DESCRIPTION:Tselil Schramm\, Stanford University\n\nAbstract: One fundament
al goal of high-dimensional statistics is to detect and recover structure f
rom noisy data. But even for simple settings (e.g. a planted low-rank matri
x perturbed by noise)\, the computational complexity of estimation is somet
imes poorly understood. A growing body of work studies low-degree polynomia
ls as a proxy for computational complexity: it has been demonstrated in var
ious settings that low-degree polynomials of the data can match the statist
ical performance of the best known polynomial-time algorithms for detection
. But prior work has failed to address settings in which there is a "detect
ion-recovery gap" and detection is qualitatively easier than recovery. In t
his talk\, I'll describe a recent result in which we extend the method of l
ow-degree polynomials to address recovery problems. As applications\, we re
solve (in the low-degree framework) open problems about the computational c
omplexity of recovery for the planted submatrix and planted dense subgraph
problems. Based on joint work with Alex Wein.
DTEND:20210423T233000Z
DTSTAMP:20210728T172604Z
DTSTART:20210423T223000Z
LOCATION:
SEQUENCE:0
SUMMARY:Probability and Statistics Seminar: Computational Barriers to Estim
ation from Low-Degree Polynomials
UID:tag:localist.com\,2008:EventInstance_36468286226379
URL:https://calendar.usc.edu/event/probability_and_statistics_seminar_compu
tational_barriers_to_estimation_from_low-degree_polynomials
END:VEVENT
END:VCALENDAR