Sum-of-Squares Lower Bound for Non-Gaussian Component Analysis

Non-Gaussian Component Analysis (NGCA) is a machine learning problem that asks to find a hidden non-Gaussian direction in high-dimensional data. We show that even powerful Sum-of-Squares (SoS) algorithms cannot efficiently solve NGCA with fewer than $n^{(1-o(1))k/2}$ samples, establishing a tight information-computation tradeoff. The proof introduces a representation-theoretic approach to analyse the key random matrices arising in SoS lower bound studies, which may have broader applications.