Technical Program

Paper Detail

Paper IDS.6.2
Paper Title Resolution Limits of Non-Adaptive Querying for Noisy 20 Questions Estimation
Authors Lin Zhou, Alfred Hero, University of Michigan, Ann Arbor, United States
Session S.6: Finite-blocklength Analysis
Presentation Lecture
Track Shannon Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract We study fundamental limits of estimation accuracy for the noisy 20 questions problem with measurement-dependent noise and introduce optimal non-adaptive procedures that achieve these limits. The minimal achievable resolution is defined as the absolute difference between the estimated and the true values of the target random variable, given a finite number of queries constrained by the excess-resolution probability. Inspired by the relationship between the 20 questions problem and the channel coding problem, we derive non-asymptotic bounds on the minimal achievable resolution. Furthermore, applying the Berry--Esseen theorem to our non-asymptotic bounds, we obtain a second-order asymptotic approximation to finite blocklength performance, specifically the achievable resolution of optimal non-adaptive query procedures with a finite number of queries subject to the excess-resolution probability constraint.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!