[Theory] [Theory Lunch] Aaron Potechin, Wednesday, 4/10 12:30-1:30pm, JCL 390

[Gabe Schoenbach]

Hi all — please join us on *Wednesday at 12:30pm* for another theory lunch!
Details below:

*****
*Date: *April 10, 2024
*Time: *12:30pm
*Location: *JCL 390

*Title: *Sum of Squares Lower Bounds for Non-Gaussian Component Analysis

*Speaker: *Aaron Potechin

*Abstract: *Non-Gaussian Component Analysis (NGCA) is the task of finding a
non-Gaussian direction in a high-dimensional dataset. NGCA has been
extensively studied and hardness for NGCA implies hardness for many other
learning problems including learning mixture models, robust mean/covariance
estimation, robust linear regression, and learning simple neural networks
and generative models. Prior work has shown statistical query and
low-degree polynomial lower bounds for NGCA but not sum of squares (SoS)
lower bounds.

In this work, we show a superconstant degree SoS lower bound for
distinguishing between the following two distributions (which is a
distinguishing variant of NGCA):

Random distribution: Take m samples from N(0,Id).
Planted distribution: First choose a hidden direction v. Then take m
samples which have some non-Gaussian distribution A in the hidden direction
v and have distribution N(0,1) in directions which are orthogonal to v.

In this talk, I will describe the low-degree polynomial framework for
distinguishing problems (as this is easier to analyze than the sum of
squares hierarchy). I will then describe one method for showing the
low-degree polynomial lower bound for NGCA.

This is joint work with Ilias Diakonikolas, Sushrut Karmalkar, and Shuo
Pang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240408/00ab5b5f/attachment.html>