[Colloquium] 5/17 Young Researcher Seminar Series: Samuel Hopkins, Cornell

[Mary Marre via Colloquium]

When:     Wednesday, May 17th at 11:00 am

Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526

Who:       Samuel Hopkins, Cornell


Title: Sample-Optimal Inference, the Method of Moments, and Community
Detection.

Abstract: We propose a simple and efficient meta-algorithm for Bayesian
estimation problems (i.e. hidden variable, latent variable, or planted
problems). Our algorithm uses low-degree polynomials together with new and
highly robust tensor decomposition methods. We focus on the question: for a
given estimation problem, precisely how many samples (up to low-order
additive terms) do polynomial-time algorithms require to obtain good
estimates of hidden variables? Our meta-algorithm is broadly applicable,
and achieves statistical or conjectured computational sample-complexity
thresholds for many well-studied problems, including many for which
previous algorithms were highly problem-specific.

As a running example we employ the stochastic block model -- a widely
studied family of random graph models which contain latent community
structure. We recover and unify the proofs of the best-known sample
complexity bounds for the partial recovery problem in this model. We also
give the first provable guarantees for partial recovery of community
structure in constant-degree graphs where nodes may participate in many
communities simultaneously. This model is known to exhibit a sharp sample
complexity threshold -- with fewer than a very specific number of samples,
recovering community structure becomes impossible. While previous
explanations for this phenomenon appeal to sophisticated ideas from
statistical mechanics, we give a new and simple explanation based on
properties of low-degree polynomials.

Joint work with David Steurer


Host: Madhur Tulsiani <madhurt at ttic.edu>

************************************************************
**************************************



The TTIC Young Researcher Seminar Series (http://www.ttic.edu/young-
researcher.php) features talks by Ph.D. students and postdocs whose research is
of broad interest to the computer science community. The series provides an
opportunity for early-career researchers to present recent work to and meet
with students and faculty at TTIC and nearby universities.


The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.

For additional information, please contact Matthew Walter (mwalter at ttic.edu
).






Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170510/ec203605/attachment.html>