Universal hypothesis testing in the learning-limited regime

Benjamin G. Kelly, Thitidej Tularak, Aaron B. Wagner, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


Given training sequences generated by two distinct, but unknown distributions sharing a common alphabet, we seek a classifier that can correctly decide whether a third test sequence is generated by the first or second distribution using only the training data. To model 'limited learning' we allow the alphabet size to grow and therefore probability distributions to change with the blocklength. We prove that a natural choice, namely a generalized likelihood ratio test, is universally consistent (has a probability of error tending to zero with the blocklength for all underlying distributions) when the alphabet size is sub-linear in the blocklength, but inconsistent for linear alphabet growth. For up-to quadratic alphabet growth, in a regime where all probabilities are of the same order, we prove the universally consistency of a new test and show there are no such tests when the alphabet grows quadratically or faster.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Number of pages5
StatePublished - 2010
Externally publishedYes
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8103


Other2010 IEEE International Symposium on Information Theory, ISIT 2010
Country/TerritoryUnited States
CityAustin, TX

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Universal hypothesis testing in the learning-limited regime'. Together they form a unique fingerprint.

Cite this