{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/14758"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/14758","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Mismatched divergence and universal hypothesis testing","abstract":"Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Huang_Dayu.pdf.txt: 77576 bytes, checksum: 24d221d5653b56f115a407da421bec70 (MD5) Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","abstract_html":"Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Huang_Dayu.pdf.txt: 77576 bytes, checksum: 24d221d5653b56f115a407da421bec70 (MD5) Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","abstract_has_math":false,"creators":["Huang, Dayu"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Meyn, Sean P."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-01-06T17:50:05Z","date_published":"2010-01-06T17:50:05Z","updated_at":"2026-07-22T22:25:08Z","subjects":["Kullback-Leibler divergence","Hoeffding test","Pinsker's inequality","universal hypothesis testing","robust test","mismatched universal test","mismatched divergence","detection","learning","variance","variational representation"],"languages":["en"],"rights":["Copyright 2009 Dayu Huang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/14758","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Meyn, Sean P."]},{"key":"dc:creator","label":"Author","values":["Huang, Dayu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-01-06T17:50:05Z","2012-01-07T11:00:14Z","2009-12"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Kullback-Leibler divergence","Hoeffding test","Pinsker's inequality","universal hypothesis testing","robust test","mismatched universal test","mismatched divergence","detection","learning","variance","variational representation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2009 Dayu Huang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/14758"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Huang_Dayu.pdf.txt: 77576 bytes, checksum: 24d221d5653b56f115a407da421bec70 (MD5) Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z","An important challenge in detection theory is that the size of the state space may be very large. In the context of universal hypothesis testing, two important problems pertaining to the large state space that have not been addressed before are: (1) What is the impact of a large state space on the performance of tests? (2) How does one design an effective test when the state space is large? This thesis addresses these two problems by developing a generalization of Kullback-Leibler (KL) mismatched divergence, called mismatched divergence. 1. We describe a drawback of the Hoeffding test: The asymptotic bias and variance of the Hoeffding test are approximately proportional to the size of the state space; thus, it performs poorly when the number of test samples is comparable to the size of state space. 2. We develop a generalization of the Hoeffding test based on the mismatched divergence, called the mismatched universal test. We show that this test has asymptotic bias and variance proportional to the dimension of the function class used to define the mismatched divergence. The dimension of the function class can be chosen to be much smaller than the size of the state space, and thus our proposed test has a better finite-sample performance in terms of bias and variance. 3. We demonstrate that the mismatched universal test also has an advantage when the distribution of the null hypothesis is learned from data. 4. We develop some algebraic properties and geometric interpretations of the mismatched divergence. We also show its connection to a robust test. 5. We develop a generalization of Pinsker’s inequality, which gives a lower bound of the mismatched divergence.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2009-12-03T18:58:48Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5)","Made available in DSpace on 2010-01-06T17:50:05Z (GMT). No. of bitstreams: 2 Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2010-01-06T17:50:31Z Item is restricted until 2012-01-06T17:50:31Z"]},{"key":"dc:title","label":"Title","values":["Mismatched divergence and universal hypothesis testing"]}]}],"canonical_facts":{"dc:contributor":["Meyn, Sean P."],"dc:creator":["Huang, Dayu"],"dc:date":["2010-01-06T17:50:05Z","2012-01-07T11:00:14Z","2009-12"],"dc:description":["Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Huang_Dayu.pdf.txt: 77576 bytes, checksum: 24d221d5653b56f115a407da421bec70 (MD5) Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-01-07T11:00:14Z","An important challenge in detection theory is that the size of the state space may be very large. In the context of universal hypothesis testing, two important problems pertaining to the large state space that have not been addressed before are: (1) What is the impact of a large state space on the performance of tests? (2) How does one design an effective test when the state space is large? This thesis addresses these two problems by developing a generalization of Kullback-Leibler (KL) mismatched divergence, called mismatched divergence. 1. We describe a drawback of the Hoeffding test: The asymptotic bias and variance of the Hoeffding test are approximately proportional to the size of the state space; thus, it performs poorly when the number of test samples is comparable to the size of state space. 2. We develop a generalization of the Hoeffding test based on the mismatched divergence, called the mismatched universal test. We show that this test has asymptotic bias and variance proportional to the dimension of the function class used to define the mismatched divergence. The dimension of the function class can be chosen to be much smaller than the size of the state space, and thus our proposed test has a better finite-sample performance in terms of bias and variance. 3. We demonstrate that the mismatched universal test also has an advantage when the distribution of the null hypothesis is learned from data. 4. We develop some algebraic properties and geometric interpretations of the mismatched divergence. We also show its connection to a robust test. 5. We develop a generalization of Pinsker’s inequality, which gives a lower bound of the mismatched divergence.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2009-12-03T18:58:48Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5)","Made available in DSpace on 2010-01-06T17:50:05Z (GMT). No. of bitstreams: 2 Huang_Dayu.pdf: 327190 bytes, checksum: 1e89146aa9ef1157d97e1b29645c8502 (MD5) license.txt: 4059 bytes, checksum: f3553b40cd35e763a5b88a902ed8d0a3 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2010-01-06T17:50:31Z Item is restricted until 2012-01-06T17:50:31Z"],"dc:identifier":["http://hdl.handle.net/2142/14758"],"dc:language":["en"],"dc:rights":["Copyright 2009 Dayu Huang"],"dc:subject":["Kullback-Leibler divergence","Hoeffding test","Pinsker's inequality","universal hypothesis testing","robust test","mismatched universal test","mismatched divergence","detection","learning","variance","variational representation"],"dc:title":["Mismatched divergence and universal hypothesis testing"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:08Z"}