{"id":164,"date":"2014-12-06T11:35:01","date_gmt":"2014-12-06T11:35:01","guid":{"rendered":"http:\/\/meyn.coron.us\/?page_id=164"},"modified":"2026-04-14T09:54:19","modified_gmt":"2026-04-14T14:54:19","slug":"generalized-error-exponents-for-small-sample-universal-hypothesis-testing","status":"publish","type":"page","link":"https:\/\/faculty.eng.ufl.edu\/meyn\/publications\/generalized-error-exponents-for-small-sample-universal-hypothesis-testing\/","title":{"rendered":"Generalized Error Exponents For Small Sample Universal Hypothesis Testing"},"content":{"rendered":"

Generalized Error Exponents For Small Sample Universal Hypothesis Testing\u00a0<\/a><\/h3>\n
Dayu Huang and Sean Meyn<\/div>\n
IEEE Transactions on Information Theory, 2013<\/div>\n
<\/div>\n
See also the Illinois archive [Link]<\/a><\/div>\n
<\/div>\n
<\/div>\n
\n\n\n\n\n
\n
The small sample<\/em> universal hypothesis testing problem is investigated: \u00a0 This means that the number of samples n<\/strong><\/em> is smaller than the number of possible outcomes m<\/em><\/strong>. \u00a0The goal of this work is to find an appropriate criterion to analyze statistical tests in this setting.<\/div>\n
<\/div>\n
A suitable model for analysis is the high-dimensional model in which both\u00a0n\u00a0<\/strong><\/em>and\u00a0m<\/em><\/strong>\u00a0increase to infinity, and \u00a0n\u00a0<\/strong><\/em>= o(m<\/em><\/strong>).<\/div>\n
<\/div>\n
A new performance criterion based on large deviations analysis is proposed and it generalizes the classical error exponent applicable for large sample problems (in which\u00a0n\u00a0<\/strong><\/em>= O(m<\/em><\/strong>)). This generalized error exponent criterion provides insights that are not available from asymptotic consistency or central limit theorem analysis. The following results are established for the uniform null distribution:<\/div>\n
<\/div>\n
    \n
  • \u00a0The best achievable probability of error decays exponentially in the ration n<\/strong><\/em>^2\/m<\/em><\/strong>.\u00a0 The optimal error exponent is also identified.<\/li>\n<\/ul>\n
      \n
    • A class of tests based on separable statistics, including the coincidence-based test, attains the optimal error exponent.<\/li>\n<\/ul>\n
        \n
      • \u00a0Pearson’s chi-square test has a zero error exponent<\/li>\n<\/ul>\n<\/td>\n
\"Probability<\/a><\/td>\n<\/tr>\n
<\/td>\n\n

This and related references (bibtex)<\/h3>\n
\n
\n
@article{huamey13,<\/div>\n
\n
Title = {Generalized Error Exponents For Small Sample Universal Hypothesis Testing},<\/div>\n<\/div>\n
Author = {Huang, D. and Meyn, S.},<\/div>\n
Journal = {TIT},<\/div>\n
Year = {2013}}<\/div>\n
<\/div>\n<\/div>\n<\/div>\n
@inproceedings{huamey12e,<\/div>\n
Title = {Classification with high-dimensional sparse samples},<\/div>\n
Abstract = {The task of the binary classification problem is to determine which of two distributions has generated a length-n test sequence. The two distributions are unknown; two training sequences of length N, one from each distribution, are observed. The distributions share an alphabet of size m, which is significantly larger than n and N. How does N,n,m affect the probability of classification error? We characterize the achievable error rate in a high-dimensional setting in which N,n,m all tend to infinity, under the assumption that probability of any symbol is O(m-1). The results are: 1) There exists an asymptotically consistent classifier if and only if m = o(min{N2, Nn}). This extends the previous consistency result in [1] to the case N \u2260 n. 2) For the sparse sample case where max{n, N} = o(m), finer results are obtained: The best achievable probability of error decays as – log(Pe) = J min {N2, Nn}(1 +o(1))\/m with J >; 0. 3) A weighted coincidence-based classifier has non-zero generalized error exponent J. 4) The l2-norm based classifier has J = 0.},<\/div>\n
Author = {Huang, Dayu and Meyn, S.},<\/div>\n
Booktitle = {Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on},<\/div>\n
Doi = {10.1109\/ISIT.2012.6283985},<\/div>\n
Issn = {2157-8095},<\/div>\n
Keywords = {error statistics;signal classification;signal sampling; l2-norm based classifier;asymptotically consistent classifier;binary classification;classification error;error decays;generalized error exponent;high dimensional sparse samples;length-n test sequence;training sequences;Approximation methods;Information theory;Random variables;Testing;Training;Vectors;Vocabulary;classification;generalized error exponent;high-dimensional model;large deviations;sparse sample},<\/div>\n
Pages = {2586-2590},<\/div>\n
Year = {2012},<\/div>\n
Bdsk-Url-1 = {http:\/\/dx.doi.org\/10.1109\/ISIT.2012.6283985<\/a>}}<\/div>\n
<\/div>\n
@inproceedings{huamey12d,<\/div>\n
Title = {Optimality of coincidence-based goodness of fit test for sparse sample problems},<\/div>\n
Abstract = {We consider the sparse sample goodness of fit problem, where the number of samples n is smaller than the size of the alphabet m. The generalized error exponent based on large deviation analysis was proposed to characterize the performance of tests, using the high-dimensional model in which both n and m tend to infinity and n = o(m). In previous work, the best achievable probability of error is shown to decay -log(Pe) = (n2\/m)(1 + o(1))J with upper and lower bounds on J. However, there is a significant gap between the two bounds. In this paper, we close the gap by proving a tight upper-bound, which matches the lower-bound over the entire region of generalized error exponents of false alarm and missed detection, achieved by the coincidence-based test. This implies that the coincidence-based test is asymptotically optimal.},<\/div>\n
Author = {Huang, Dayu and Meyn, S.},<\/div>\n
Booktitle = {Information Theory and Applications Workshop (ITA), 2012},<\/div>\n
Doi = {10.1109\/ITA.2012.6181779},<\/div>\n
Keywords = {error statistics;sparse matrices;statistical testing;asymptotically optimal;best achievable error probability;coincidence-based goodness;coincidence-based test;false alarm;fit test;generalized error exponents;high-dimensional model;large deviation analysis;missed detection;optimality;sparse sample goodness;sparse sample problems;test performance;tight upper-bound;Analytical models;Biological system modeling;Convergence;Indexes;Materials;Probability;Speech processing;chi-square test;goodness of fit;high-dimensional model;large deviations;optimal test},<\/div>\n
Pages = {344-346},<\/div>\n
Year = {2012},<\/div>\n
Bdsk-Url-1 = {http:\/\/dx.doi.org\/10.1109\/ITA.2012.6181779<\/a>}}<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Generalized Error Exponents For Small Sample Universal Hypothesis Testing\u00a0 Dayu Huang and Sean Meyn IEEE Transactions on Information Theory, 2013 See also the Illinois archive [Link] The small sample universal hypothesis testing problem is investigated: \u00a0 This means that the number of samples n is smaller than the number of possible outcomes m. \u00a0The goal […]<\/p>\n","protected":false},"author":1347,"featured_media":0,"parent":27,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"page-templates\/page-section-nav.php","meta":{"_acf_changed":false,"inline_featured_image":false,"featured_post":"","footnotes":"","_links_to":"","_links_to_target":""},"class_list":["post-164","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/164","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/users\/1347"}],"replies":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/comments?post=164"}],"version-history":[{"count":1,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/164\/revisions"}],"predecessor-version":[{"id":2909,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/164\/revisions\/2909"}],"up":[{"embeddable":true,"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/pages\/27"}],"wp:attachment":[{"href":"https:\/\/faculty.eng.ufl.edu\/meyn\/wp-json\/wp\/v2\/media?parent=164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}