<div dir="ltr"><div dir="ltr">Hi all — please join us on <b>Wednesday at 12:30pm</b> for another theory lunch! Details below:<div><br></div><div>*****</div><div><b>Date: </b>April 10, 2024</div><div><b>Time: </b>12:30pm</div><div><b>Location: </b>JCL 390</div><div><b><br></b></div><div><b>Title: </b>Sum of Squares Lower Bounds for Non-Gaussian Component Analysis</div><div><b><br></b></div><div><b>Speaker: </b>Aaron Potechin</div><div><b><br></b></div><div><b>Abstract: </b>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.</div><br>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):<br><br>Random distribution: Take m samples from N(0,Id).<br>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.<br><br>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.<br><br>This is joint work with Ilias Diakonikolas, Sushrut Karmalkar, and Shuo Pang.</div></div>