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

Wed May 17 10:24:40 CDT 2017

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 Tue, May 16, 2017 at 2:29 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>*
>
> 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/20170517/92cf7f16/attachment-0001.html>