PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 39 of its 75 references that are in the map. First posted on arXiv 24 Nov 2025.
Builds on
39 of 75 references.
References · 39
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
- 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
- 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
- 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
- 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
- 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
- 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
- 2017Learning Geometric Concepts with Nasty Noisecited by 46
- 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
- 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
- 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
- 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
27 more
- 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
- 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
- 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
- 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
- 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
- 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
- 2025Computational Complexity of Statistics: New Insights from Low-Degree Polynomialscited by 19
- 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
- 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
- 2022Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexitycited by 12
- 2022Learning (Very) Simple Generative Models Is Hardcited by 9
- 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
- 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
- 2018Non-Gaussian Component Analysis using Entropy Methodscited by 8
- 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
- 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
- 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
- 2025Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Modelscited by 5
- 2018Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)cited by 4
- 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
- 2024Computational-Statistical Gaps for Improper Learning in Sparse Linear Regressioncited by 4
- 2024Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gapscited by 4
- 2016Non-Gaussian Component Analysis with Log-Density Gradient Estimationcited by 3
- 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
- 2024Cryptographic Hardness of Score Estimationcited by 3
- 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
- 2013Efficient deterministic approximate counting for low-degree polynomial threshold functionscited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.