Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets

Chunsong Sun; Lin Zhou

doi:10.1109/ISIT54713.2023.10206995

Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets

Chunsong Sun^*
, Lin Zhou

^*Corresponding author for this work

School of Cyber Science and Technology

Beihang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.

Original language	English
Title of host publication	2023 IEEE International Symposium on Information Theory, ISIT 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1580-1585
Number of pages	6
ISBN (Electronic)	9781665475549
DOIs	https://doi.org/10.1109/ISIT54713.2023.10206995
State	Published - 2023
Event	2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China Duration: 25 Jun 2023 → 30 Jun 2023

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2023-June
ISSN (Print)	2157-8095

Conference

Conference	2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/Territory	Taiwan, Province of China
City	Taipei
Period	25/06/23 → 30/06/23

Keywords

Noisy adaptive search
adaptivity gain
finite blocklength analysis
multiple targets
second-order asymptotics

Access to Document

10.1109/ISIT54713.2023.10206995

Cite this

Sun, C., & Zhou, L. (2023). Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets. In 2023 IEEE International Symposium on Information Theory, ISIT 2023 (pp. 1580-1585). (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT54713.2023.10206995

@inproceedings{9fb1c8d9782243f2a8d286788cbf5ca7,

title = "Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets",

abstract = "We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.",

keywords = "Noisy adaptive search, adaptivity gain, finite blocklength analysis, multiple targets, second-order asymptotics",

author = "Chunsong Sun and Lin Zhou",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE International Symposium on Information Theory, ISIT 2023 ; Conference date: 25-06-2023 Through 30-06-2023",

year = "2023",

doi = "10.1109/ISIT54713.2023.10206995",

language = "英语",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1580--1585",

booktitle = "2023 IEEE International Symposium on Information Theory, ISIT 2023",

address = "美国",

}

Sun, C & Zhou, L 2023, Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets. in 2023 IEEE International Symposium on Information Theory, ISIT 2023. IEEE International Symposium on Information Theory - Proceedings, vol. 2023-June, Institute of Electrical and Electronics Engineers Inc., pp. 1580-1585, 2023 IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, Province of China, 25/06/23. https://doi.org/10.1109/ISIT54713.2023.10206995

Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets. / Sun, Chunsong; Zhou, Lin.
2023 IEEE International Symposium on Information Theory, ISIT 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 1580-1585 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets

AU - Sun, Chunsong

AU - Zhou, Lin

PY - 2023

Y1 - 2023

N2 - We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.

AB - We study the problem of adaptive search for multiple targets using the framework of 20 questions estimation under the query-dependent noise channel. Specifically, we propose an adaptive query strategy that combines the ideas of non-adaptive search for multiple targets using random coding by Zhou, Bai and Hero (TIT, 2022) and adaptive search for one target using variable-length coding with feedback by Zhou and Hero (ISIT, 2021). Our main contribution is the derivation of the non-asymptotic and second-order asymptotic performance of our adaptive query procedure. Furthermore, we discuss the benefit of adaptivity, analytically and numerically, by comparing our results with the non-adaptive counterparts.

KW - Noisy adaptive search

KW - adaptivity gain

KW - finite blocklength analysis

KW - multiple targets

KW - second-order asymptotics

UR - https://www.scopus.com/pages/publications/85171426170

U2 - 10.1109/ISIT54713.2023.10206995

DO - 10.1109/ISIT54713.2023.10206995

M3 - 会议稿件

AN - SCOPUS:85171426170

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1580

EP - 1585

BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023

Y2 - 25 June 2023 through 30 June 2023

ER -

Achievable Resolution Limits of Noisy Adaptive 20 Questions Estimation for Multiple Targets

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this