PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Authors:
Preprint
Abstract
This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are stronger than the information-theoretic optimum) against natural models of computation. A popular such model in the literature is the family of low-degree polynomial tests. While these tests are defined in such a way that make them easy to analyze, the class of algorithms that they rule out is somewhat restricted. An important goal in this context has been to obtain lower bounds against the stronger and more natural class of low-degree Polynomial Threshold Function (PTF) tests, i.e., any test that can be expressed as comparing some low-degree polynomial of the data to a threshold. Proving lower bounds against PTF tests has turned out to be challenging. Indeed, we are not aware of any non-trivial PTF testing lower bounds in the literature. In this paper, we establish the first non-trivial PTF testing lower bounds for a range of statistical tasks. Specifically, we prove a near-optimal PTF testing lower bound for Non-Gaussian Component Analysis (NGCA). Our NGCA lower bound implies similar lower bounds for a number of other statistical problems. Our proof leverages a connection to recent work on pseudorandom generators for PTFs and recent techniques developed in that context. At the technical level, we develop several tools of independent interest, including novel structural results for analyzing the behavior of low-degree polynomials restricted to random directions.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Algorithmic High-Dimensional Robust Statistics2023
- Subexponential-Time Algorithms for Sparse PCAFoundations of Computational Mathematics, 2023
- A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length2014
- The correct exponent for the Gotsman–Linial Conjecturecomputational complexity, 2014
- Average Sensitivity and Noise Sensitivity of Polynomial Threshold FunctionsSIAM Journal on Computing, 2014
- Sparse non Gaussian component analysis by semidefinite programmingMachine Learning, 2013
- A Small PRG for Polynomial Threshold Functions of Gaussians2011
- Bounded Independence Fools Degree-2 Threshold Functions2010
- Approximating the Best Linear Unbiased Estimator of Non-Gaussian Signals with Gaussian NoiseIEICE Transactions on Information and Systems, 2008
- The perceptron: A probabilistic model for information storage and organization in the brain.Psychological Review, 1958