Abstract
Non-Gaussian component analysis (NGCA) is the following statistical task: Given sample access to a high-dimensional distribution that is non-Gaussian in a hidden direction and a standard multivariate Gaussian in the orthogonal complement, approximate the hidden direction. In a 2017 paper with Kane and Stewart, we established tight Statistical Query (SQ) lower bounds for this problem and derived similar implications for several, seemingly unrelated, statistical tasks. Since then, a number of works have leveraged this framework to obtain tight SQ lower bounds for a range of high-dimensional learning problems. In this work, we will survey these developments and discuss opportunities for future work.