Data-Efficient Hypothesis Testing
Abstract
Pearson s chi-squared test is perhaps the most widely used statistical test, across many data-driven decision making settings. However, the chi-squared test does not make optimal use of its data. By contrast, we propose to study a new---principled and flexible---framework for the same setting as the chi-squared test, designed to yield more statistically significant results than chi-squared onthe same data, and to require less data than chi-squared to reach the same level of statistical significance. When Pearson proposedthe chi-squared test in 1900, computation was perhaps a billion times slower than it is today, and thus the chi-squared test embraces a tradeoff between computation time versus accuracy that is miscalibrated by a factor of a billion for modern use; thus we propose to develop a new testing framework that involves modern algorithmic tools (that were both unfeasible and unknown in Pearson s time) to achieve a more "data-efficient" tester in this classic setting. Technically, the new estimation framework of this proposal centers around a nonlinear optimization setup, optimizing over the choice of estimator from a certain rather general class of estimatorscalled "semilinear estimators", that generalizes the chi-squared test, and most of its commonly considered variants. Our optimization setup views the testing problem as essentially a two-player game, between the "test designer" who chooses the tester, and "nature" who chooses the setting under which our tester will be run. Our optimization setup has 4 nested layers: taking the best tester, over the worst case input, minimized over both Type-I and Type-II errors, and where performance of a given algorithm in a given setting is characterized by the best Chernoff bound possible for this setting. This nonlinear optimization setup is natural, yet daunting.The surprise is that---in preliminary work---we have shown the framework is 1) computationally efficient; 2) theoretically tractable; and 3) provides not just an upper bound but also a lower bound, showing that this class of algorithms is theoretically optimal, in the appropriate limit. Unlike the chi-squared test which is "one size fits all", our approach is flexible and customizable. This proposal puts forward a principled, general, and flexible framework to develop new statistical testers/estimators that leverage modern computational tools to yield unprecedented data efficiency. Across many other statistical contexts also, the process of making operations decisions is often based on statistical tests developed 50-100 years ago. These tests are computationally simple; there is an opportunity across a wide range of settings, for more sophisticated tests, which yield either improved accuracy, or allow the same accuracy but using less data. We therefore anticipate the results of this project to have influence on the development of modern computationally sophisticated statistical tests, leading to better use of statistical data acrossa wide range of areas. Approved forpublic release.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412695
Entities
People
- Paul Valiant
Organizations
- Office of Naval Research
- Purdue University
- United States Navy