PTF Testing Lower Bounds for Non-Gaussian Component Analysis

• URL: http://arxiv.org/abs/2511.19398v1
• Date: Mon, 24 Nov 2025 18:35:29 GMT
• Title: PTF Testing Lower Bounds for Non-Gaussian Component Analysis
• Authors: Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas,
• Abstract summary: This work studies information-computation gaps for statistical problems.<n>We prove a near-trivial PTF testing lower bound for Non-Gaussian Component Analysis (NGCA)<n>Our NGCA lower bound implies similar lower bounds for a number of other statistical problems.
• Score: 45.24757440014651
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials [57.377943721487966]
  This is a survey on the use of low-degrees to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems.
  arXiv  Detail & Related papers  (2025-06-12T14:35:26Z)
• Low degree conjecture implies sharp computational thresholds in stochastic block model [3.7873597471903935]
  We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23] in the context of the symmetric block model)<n>We establish that no-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold.<n>Our results provide evidence of a computational-to-statistical gap in learning the parameters of block models.
  arXiv  Detail & Related papers  (2025-02-20T20:21:03Z)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  Federated learning has attracted significant recent attention due to its applicability across a wide range of settings where data is collected and analyzed across disparate locations. We study federated nonparametric goodness-of-fit testing in the white-noise-with-drift model under distributed differential privacy (DP) constraints.
  arXiv  Detail & Related papers  (2024-06-10T19:25:19Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity.<n>An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  We study two of the most popular restricted computational models, the statistical query framework and low-degree corollas, in the context of high-dimensional hypothesis testing. Under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. Asries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.
  arXiv  Detail & Related papers  (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.