| Paper ID | D3-S6-T1.3 |
| Paper Title |
Optimal Rates of Teaching and Learning Under Binary Symmetric Noise |
| Authors |
Yan Hao Ling, Jonathan Mark Scarlett, National University of Singapore, Singapore |
| Session |
D3-S6-T1: Relaying I |
| Chaired Session: |
Wednesday, 14 July, 23:40 - 00:00 |
| Engagement Session: |
Thursday, 15 July, 00:00 - 00:20 |
| Abstract |
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$.
|
