Universal hypothesis testing

In statistics, universal hypothesis testing is a generalization of binary simple hypothesis testing. The universal problem is to distinguish between a simple null hypothesis H0:Q=P, and the most general composite alternative H1:Q≠P, using independent and identically distributed samples from Q. The problem was first described in Wassily Hoeffding's work on optimal tests for multinomial distributions, which focused on the asymptotics of the problem.

The setting is sometimes referred to as goodness of fit testing or one-sample testing. It is similar in principle to the identity testing problem, in which we are promised that an unknown distribution is either exactly P or ε-far from P in some statistical distance. In certain circumstances "universal hypothesis testing" is used to refer to composite hypothesis testing problems using universal inference estimators, which are statistics that work without regularity assumptions.

Formulation

A simple binary hypothesis testing problem involves distinguishing between H0:Q=P0 and H1:Q=P1, using samples X1,…,Xn∼i.i.d.Q. In the traditional setting of hypothesis testing P0,P1 are known apriori. A composite version of this problem involves sets of probability distributions Ω0,Ω1, and requires distinguishing between H0:Q∈Ω0 and H1:Q∈Ω1. Universal hypothesis testing corresponds to the special case of composite hypothesis testing where the null hypothesis is simple, Ω0=P and the alternative hypothesis is the set of all distributions other than P, Ω1={F:F≠P}.

Given a fixed number of samples, these two hypothesis can be indistinguishable, as it is possible for the distribution under the alternative hypothesis to be arbitrarily close to the null hypothesis. To avoid this issue, the problem is often considered in the Neyman-Pearson setting, where the goal is to build a test that achieves a fixed type I error probability under the null hypothesis and then minimize the probability of type II error. Mathematical formulations of universal hypothesis testing generally assume that under the alternative hypothesis the distribution is fixed but unknown, to highlight the fact that universal tests do not require knowledge of the alternative to function.

Subsequent work on universal hypothesis testing includes second-order asymptotic analysis, universal outlier hypothesis testing, and universal quickest change detection. Universal hypothesis testing has been studied in regimes where the support of the underlying distributions grows as a proportion to the number of samples drawn from the distribution, in what is called the 'learning limited regime'. Applications for universal hypothesis testing include universal coding. While Hoeffding's initial results were restricted to distributions with finite supports, later results developed solutions for continuous distributions using extensions of the Kullback-Leibler Divergence, or kernel methods.

Two-sample universal hypothesis testing

Another version of the universal hypothesis testing problem is the two-sample problem, in which the nominal distribution P is also unknown, and all inference is made using samples from both P and Q.

Gutman setting

The Gutman hypothesis testing problem inolves three unknown distributions, P1,P2,Q, where samples are provided from each distribution. In this setting, the hypothesis is H0:Q=P1H1:Q=P2. The samples from P1,P2 are referred to as the training samples, and the samples from Q are known as the test samples. This has a natural connection to the binary classification problem in statistical learning theory.

Examples

As an example, we might want to know if a particular coin was fair, i.e. ℙ[X=H]=12=ℙ[X=T] or not, i.e. ℙ[X=H]≠ℙ[X=T], where H,T denote the coin coming up heads or tails.

See also

References

  1. ↑ Hoeffding, Wassily (April 1965). "Asymptotically Optimal Tests for Multinomial Distributions". The Annals of Mathematical Statistics. 36 (2): 369–401. doi:10.1214/aoms/1177700150. ISSN 0003-4851.
  2. ↑ Diakonikolas, Ilias; Gouleakis, Themis; Peebles, John; Price, Eric (2018). "Sample-Optimal Identity Testing with High Probability". LIPIcs, Volume 107, ICALP 2018. 107: 41:1–41:14. arXiv:1708.02728. doi:10.4230/LIPIcs.ICALP.2018.41.
  3. ↑ Moniri, Behrad. "Universal Inference" (PDF). engineering.upenn.edu. University of Pennsylvania. Archived from the original (PDF) on 27 September 2026. Retrieved 27 September 2026.
  4. ↑ Levitan, E.; Merhav, N. (August 2002). "A competitive Neyman-Pearson approach to universal hypothesis testing with applications". IEEE Transactions on Information Theory. 48 (8): 2215–2229. Bibcode:2002ITIT...48.2215L. doi:10.1109/TIT.2002.800478. ISSN 0018-9448.
  5. ↑ Zeitouni, O.; Gutman, M. (March 1991). "On universal hypotheses testing via large deviations". IEEE Transactions on Information Theory. 37 (2): 285–290. Bibcode:1991ITIT...37..285Z. doi:10.1109/18.75244.
  6. 1 2 Kelly, Benjamin G.; Tularak, Thitidej; Wagner, Aaron B.; Viswanath, Pramod (2010). "Universal hypothesis testing in the learning-limited regime". IEEE International Symposium on Information Theory, ISIT 2010, June 13–18, 2010, Austin, Texas, USA, Proceedings. IEEE. pp. 1478–1482. doi:10.1109/ISIT.2010.5513583.
  7. ↑ Harsha, K. V.; Ravi, Jithin; Koch, Tobias (1 November 2022). "Second-Order Asymptotics of Hoeffding-Like Hypothesis Tests". 2022 IEEE Information Theory Workshop (ITW): 654–659. arXiv:2205.05631. Bibcode:2022itw..conf...35H. doi:10.1109/ITW54588.2022.9965931. ISBN 978-1-6654-8341-4.{{cite journal}}: CS1 maint: periodical has ISBN (link)
  8. ↑ Harsha, K. V.; Ravi, Jithin; Koch, Tobias (October 2025). "On the Second-Order Asymptotics of the Hoeffding Test and Other Divergence Tests". IEEE Transactions on Information Theory. 71 (10): 7459–7483. arXiv:2403.03537. Bibcode:2025ITIT...71.7459H. doi:10.1109/TIT.2025.3588194.
  9. ↑ Li, Yun; Nitinawarat, Sirin; Veeravalli, Venugopal V. (July 2014). "Universal Outlier Hypothesis Testing". IEEE Transactions on Information Theory. 60 (7): 4066–4082. arXiv:1302.4776. Bibcode:2014ITIT...60.4066L. doi:10.1109/TIT.2014.2317691.
  10. ↑ Lau, Tze Siong; Tay, Wee Peng; Veeravalli, Venugopal V. (March 2017). "Quickest change detection with unknown post-change distribution". 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 3924–3928. doi:10.1109/ICASSP.2017.7952892. ISBN 978-1-5090-4117-6.
  11. ↑ Liang, Yuchen; Veeravalli, Venugopal V. (November 2024). "Quickest Change Detection With Post-Change Density Estimation". IEEE Transactions on Information Theory. 70 (11): 8072–8086. arXiv:2311.15128. Bibcode:2024ITIT...70.8072L. doi:10.1109/TIT.2024.3418379.
  12. ↑ Huang, Dayu; Meyn, Sean (December 2013). "Generalized Error Exponents for Small Sample Universal Hypothesis Testing". IEEE Transactions on Information Theory. 59 (12): 8157–8181. arXiv:1204.1563. Bibcode:2013ITIT...59.8157H. doi:10.1109/TIT.2013.2283266.
  13. ↑ Huang, Dayu (2012). Hypothesis Testing And Learning With Small Samples (Doctor of Philosophy thesis). University of Illinois at Urbana-Champaign. Retrieved Nov 1, 2026.
  14. ↑ Feder, M.; Merhav, N. (June 2002). "Universal composite hypothesis testing: a competitive minimax approach". IEEE Transactions on Information Theory. 48 (6): 1504–1517. Bibcode:2002ITIT...48.1504F. doi:10.1109/TIT.2002.1003837.
  15. ↑ Yang, Pengfei; Chen, Biao (April 2019). "Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions". IEEE Transactions on Information Theory. 65 (4): 2360–2373. arXiv:1711.04238. Bibcode:2019ITIT...65.2360Y. doi:10.1109/TIT.2018.2879057. ISSN 0018-9448.
  16. 1 2 Zhu, Shengyu; Chen, Biao; Chen, Zhitang; Yang, Pengfei (April 2021). "Asymptotically Optimal One- and Two-Sample Testing With Kernels". IEEE Transactions on Information Theory. 67 (4): 2074–2092. arXiv:1908.10037. Bibcode:2021ITIT...67.2074Z. doi:10.1109/TIT.2021.3059267. ISSN 0018-9448.
  17. ↑ Zhu, Shengyu; Chen, Biao; Yang, Pengfei; Chen, Zhitang (2019-04-11). "Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit". Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. PMLR: 1544–1553. arXiv:1802.07581.
  18. ↑ Grootveld, Arick; Chen, Biao; Gandikota, Venkata (June 2026). "Asymptotically Optimal Tests for One- and Two-Sample Problems". 2026 IEEE International Symposium on Information Theory (ISIT). pp. 1–6. arXiv:2601.11727. doi:10.1109/ISIT62367.2026.11654166. ISBN 979-8-3315-8004-9.
  19. ↑ Gutman, M. (March 1989). "Asymptotically optimal classification for multiple tests with empirically observed statistics". IEEE Transactions on Information Theory. 35 (2): 401–408. Bibcode:1989ITIT...35..401G. doi:10.1109/18.32134.
  20. ↑ Li, Yun; Veeravalli, Venugopal V. (2016). "Outlying sequence detection in large datasets: Comparison of universal hypothesis testing and clustering". 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, Shanghai, China, March 20–25, 2016. IEEE. pp. 6180–6184. doi:10.1109/ICASSP.2016.7472865.