Search Mailing List Archives
[theory-seminar] [theory-lunch] Jacob Steinhardt on Certifying 2->q Norm
Hongyang Zhang
hongyang at cs.stanford.edu
Thu Oct 12 10:16:21 PDT 2017
Reminder this is today at noon.
-h
On Tue, 10 Oct 2017 at 3:22 PM Hongyang Zhang <hongyang at cs.stanford.edu>
wrote:
> Hi Everyone
>
> This *thursday 12:00pm to 1:00pm, at Gates 463A*, Jacob Steinhardt will
> tell us about "Certifying 2-q Norms with Sum-of-Squares". See below for the
> abstract.
>
> As usual, the talk starts at 12:30pm. See you all!
>
> -hongyang
>
> ------------------------------------------------------------
>
> Title: Certifying 2->q Norm with Sum-of-Squares
>
> Abstract: Approximating the 2->q norm is a natural geometric problem which
> is closely related to the unique games conjecture. BBHKSZ12 show that the
> sum-of-squares (SOS) hierarchy is able to approximate the 2->q norm well on
> points sampled from product distributions on the hypercube, but the general
> performance of SOS on 2->q norm is not well-understood. I will show that
> for distributions satisfying the *Poincare inequality*, m rounds of
> sum-of-squares are sufficient to approximate the 2->m norm for all even m
> >= 2. This substantially extends the result of BBHKSZ12. As applications we
> present improved algorithms for clustering and robust mean estimation. The
> proof exploits recent advances in geometric probability by Adamczak and
> Wolff.
>
> This is joint work with Pravesh Kothari.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20171012/d155faa2/attachment.html>
More information about the theory-seminar
mailing list