[Colloquium] REMINDER: 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>*

On Wed, May 10, 2017 at 5:06 PM, Mary Marre <mmarre at ttic.edu> wrote:

> 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 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%20357-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/20170516/b7b2c2a9/attachment-0001.html>