BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20220313T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20221106T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20240519T102034Z
UID:8d18e9b4-7133-42d3-8b38-147f850cda49
DTSTART;TZID=America/New_York:20220510T160000
DTEND;TZID=America/New_York:20220510T170000
CREATED:20220413T161335
DESCRIPTION:We consider the problem of clustering a mixture of Gaussians in
high dimensions\, one of the most well-studied tasks in clustering and hi
gh dimensional distribution learning. In the most basic setting\, we recei
ve samples from a mixture of k Gaussians in d dimensions\, each with ident
ity covariance\, and with the promise that the means of the Gaussians have
pairwise separation at least Delta. The goal is to efficiently recover a
near-perfect clustering of the samples\, in polynomial time and sample com
plexity. It is folklore that this problem is information-theoretically pos
sible as long as Delta >> sqrt(log k)\, however\, all known algorithmic me
thods for this regime require at least quasi-polynomial runtime and sample
complexity. All of these methods hit the same basic roadblock: it seems t
hat efficient methods for solving this problem need to look at all moments
of degree at least polylogarithmically many moments\; however\, even writ
ing down the moment tensor at that degree requires quasi-polynomial runtim
e.\n\nIn this work\, we circumvent this barrier\, and present the first fu
lly polynomial time algorithm for this problem. Perhaps surprisingly\, our
method still goes via the method of moments\, but we avoid writing down t
he full moment tensor using a recursively constructed implicit representat
ion of the moment tensor. This allows us to have restricted access to the
moment tensor in polynomial time\, which we demonstrate is sufficient to s
olve the full problem. We also demonstrate that our techniques generalize
to the case where the components are all shifts of the same distribution\,
as long as that distribution satisfies the Poincare inequality.\n
LAST-MODIFIED:20220413T161335
LOCATION:32-G449 (Kiva)
SUMMARY:Clustering Mixtures with Almost Optimal Separation in Polynomial Ti
me
URL:https://calendar.csail.mit.edu/events/246170
END:VEVENT
END:VCALENDAR