|| Optimal Rates of Teaching and Learning Under Binary Symmetric Noise
||Yan Hao Ling, Jonathan Mark Scarlett, National University of Singapore, Singapore|
||D3-S6-T1: Relaying I
||Wednesday, 14 July, 23:40 - 00:00
||Thursday, 15 July, 00:00 - 00:20
In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number $n$ of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as $n$ increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is $D(1/2||max(p,q))$, where $p$ and $q$ are the noise parameters. This matches a trivial converse result based on the data processing inequality, and disproves a conjecture of [Jog and Loh, 2020]. In addition, we show that computation time required by the teacher and student is linear in $n$.