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 the binary relative entropy $D\big(\frac{1}{2}\|\max(p,q)\big)$, where $p$ and $q$ are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihel \emph{et al.}, 2019]. In addition, we show that the computation time required by the teacher and student is linear in $n$. We also study a more general setting in which the binary symmetric channels are replaced by general binary-input discrete memoryless channels. We provide an achievability bound and a converse bound, and show that the two coincide in certain cases, including (i) when the two channels are identical, and (ii) when the student-teacher channel is a binary symmetric channel. More generally, we give sufficient conditions under which our achievable learning rate is the best possible for block-structured protocols.
Problem Formulation
The paper addresses a fundamental challenge in information theory: determining the optimal rate at which a student can learn a hidden variable from a teacher over noisy channels. This model is motivated by scenarios such as social learning, relay channels, and the velocity of information propagation.
Consider a 1-bit state of the world $\Theta \in \{0, 1\}$. A teacher observes this bit repeatedly through a noisy Binary Symmetric Channel (BSC) with error rate $p$, yielding observations $Y$. The teacher then sequentially transmits information to a student through a second BSC with error rate $q$. The teacher's transmissions $\hat{X}$ must be causal, depending only on past observations. After $n$ transmissions, the student receives $Z$ and produces an estimate $\hat{\Theta}$. The objective is to find the optimal learning rate—the exponential rate at which the student's error probability decays as $n \to \infty$.
Proposed Block-Structured Strategy
To achieve the theoretical upper bound of $D(1/2 || \max(p,q))$, the authors introduce a novel block-structured teaching strategy. Instead of bit-by-bit transmission, the teacher groups observations into blocks of length $k$.
Within each block, the teacher calculates the fraction of 1s received, $\alpha$. This confidence level is communicated to the student by sending a sorted sequence of bits: a string of 1s followed by a string of 0s. The transition point in this sequence is determined by a carefully chosen non-linear function $f(\alpha)$ derived from relative entropy considerations. This sorted structure acts as a powerful prior; since the student knows the sequence must be sorted, they can use Maximum Likelihood (ML) decoding to effectively filter out channel noise. This method is also extended to general binary-input Discrete Memoryless Channels (DMCs) by mapping block log-likelihood ratios (LLRs) to sorted sequences.
Key Insights and Results
The primary contribution of this work is proving that the trivial upper bound based on the Data Processing Inequality is indeed achievable for BSCs, settling two major conjectures in the field.
- Optimal Learning Rate: For the BSC setup, the optimal rate is exactly $D(1/2 || \max(p,q))$.
- Computational Efficiency: The proposed protocol is highly efficient, with both teacher and student computation times being $O(n)$.
- Non-linear Mapping: The optimal strategy requires a non-linear mapping $f(\alpha)$ between the teacher's confidence and the transmitted sequence, balancing simple forwarding and cumulative teaching.
- General DMCs: For general DMCs $P$ and $Q$, an achievable rate of $-\min_{s \in [0,1]} \max(\mu_P(s), \mu_Q(s))$ is established, which is shown to be optimal in several cases, such as when $P=Q$ or when $Q$ is a BSC.
Conclusion and Future Work
While this work settles the optimal rate for BSCs and specific DMCs, several open questions remain. The absolute optimal rate for arbitrary asymmetric DMCs is not yet fully characterized, as the achievability and converse bounds do not always match. Furthermore, the current protocol assumes known noise parameters $p$ and $q$. Future research could explore adaptive protocols for unknown noise levels and extensions to non-binary input channels.
Summary updated