Precise Error Rates for Computationally Efficient Testing

• URL: http://arxiv.org/abs/2311.00289v1
• Date: Wed, 1 Nov 2023 04:41:16 GMT
• Title: Precise Error Rates for Computationally Efficient Testing
• Authors: Ankur Moitra, Alexander S. Wein
• Abstract summary: We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity. An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
• Score: 75.63895690909241
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the classical spiked Wigner model (with a general i.i.d. spike prior) we show that an existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates among all computationally efficient tests, even though there are exponential-time tests that do better. This result is conditional on an appropriate complexity-theoretic conjecture, namely a natural strengthening of the well-established low-degree conjecture. Our result shows that the spectrum is a sufficient statistic for computationally bounded tests (but not for all tests). To our knowledge, our approach gives the first tool for reasoning about the precise asymptotic testing error achievable with efficient computation. The main ingredients required for our hardness result are a sharp bound on the norm of the low-degree likelihood ratio along with (counterintuitively) a positive result on achievability of testing. This strategy appears to be new even in the setting of unbounded computation, in which case it gives an alternate way to analyze the fundamental statistical limits of testing.

Related papers

• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  We provide the first type-I-error and expected-rejection-time guarantees under general non-data generating processes. We show how to apply our results to inference on parameters defined by estimating equations, such as average treatment effects.
  arXiv  Detail & Related papers  (2022-12-29T18:37:08Z)
• Learning to Increase the Power of Conditional Randomization Tests [8.883733362171032]
  The model-X conditional randomization test is a generic framework for conditional independence testing. We introduce novel model-fitting schemes that are designed to explicitly improve the power of model-X tests.
  arXiv  Detail & Related papers  (2022-07-03T12:29:25Z)
• Statistical and Computational Phase Transitions in Group Testing [73.55361918807883]
  We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease. We consider two different simple random procedures for assigning individuals tests.
  arXiv  Detail & Related papers  (2022-06-15T16:38:50Z)
• Sequential Permutation Testing of Random Forest Variable Importance Measures [68.8204255655161]
  It is proposed here to use sequential permutation tests and sequential p-value estimation to reduce the high computational costs associated with conventional permutation tests. The results of simulation studies confirm that the theoretical properties of the sequential tests apply. The numerical stability of the methods is investigated in two additional application studies.
  arXiv  Detail & Related papers  (2022-06-02T20:16:50Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Significance tests of feature relevance for a blackbox learner [6.72450543613463]
  We derive two consistent tests for the feature relevance of a blackbox learner. The first evaluates a loss difference with perturbation on an inference sample. The second splits the inference sample into two but does not require data perturbation.
  arXiv  Detail & Related papers  (2021-03-02T00:59:19Z)
• Cross-validation Confidence Intervals for Test Error [83.67415139421448]
  This work develops central limit theorems for crossvalidation and consistent estimators of its variance under weak stability conditions on the learning algorithm. Results are the first of their kind for the popular choice of leave-one-out cross-validation.
  arXiv  Detail & Related papers  (2020-07-24T17:40:06Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• The Chi-Square Test of Distance Correlation [7.748852202364896]
  chi-square test is non-parametric, extremely fast, and applicable to bias-corrected distance correlation using any strong negative type metric or characteristic kernel. We show that the underlying chi-square distribution well approximates and dominates the limiting null distribution in upper tail, prove the chi-square test can be valid and consistent for testing independence.
  arXiv  Detail & Related papers  (2019-12-27T15:16:40Z)

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.