Optimal Rates of Teaching and
Learning Under Uncertainty

We first formalize the model, which is depicted in Figure 1. The unknown quantity of interest is a binary random variable $\Theta$ that takes either value in $\{0,1\}$, each with probability $\frac{1}{2}$.

At each time step $i\in\{1,\dotsc,n\}$, the teacher observes $\Theta$ through BSC($p$), a binary symmetric channel with error rate $p\in\big{(}0,1/2\big{)}$:

The binary symmetric channel is memoryless, meaning that the $Y_{i}$’s are conditionally independent given $\Theta$. In Section III, we will study more general and possibly non-symmetric binary-input discrete memoryless channels.

At time $i$, the teacher then transmits binary information $\hat{X}_{i}$ to the student through another binary symmetric channel BSC($q$), where $q\in\big{(}0,1/2\big{)}$. Thus, denoting the student’s observations by $Z_{i}$, we have

and the $Z_{i}$ are conditionally independent given $\hat{X}_{i}$. Importantly, $\hat{X}_{i}$ must only be a function of $Y_{1},,\ldots,Y_{i}$; the teacher cannot look into the future.

At time $n$, having received $Z_{1},\ldots,Z_{n}$, the student makes an estimate of $\Theta$, which we denote by $\hat{\Theta}_{n}$ (or sometimes simply $\hat{\Theta}$). Then, the learning rate is defined as

We assume that the noise parameters $p$ and $q$ are known to both the teacher and student; removing this assumption may be an interesting direction for future work.

The preceding motivation and setup follows that of Jog and Loh [1], and the same problem was also considered with different motivation and terminology by Huleihel, Polyanskiy, and Shayevitz [2], who framed the problem using the terminology of relay channels. While relay channels are already a central topic in information theory, the authors of [2] further motivated their study via the more recent information velocity problem, which was posed by Yury Polyanskiy [2] and is also captured under a general framework studied by Rajagopalan and Schulman [3]. In that problem, the goal is to reliably transmit a single bit over a long chain of relays while maintaining a non-vanishing ratio between the number of hops and the total transmission time. Below we will discuss a conjecture (for the 2-hop setting) made in [2] that is directly inspired by the connection with information velocity.

It is known that the student’s optimal strategy is the maximum likelihood decoder (assuming the teacher’s strategy is known) [2, 1]. In [1], it was discussed that optimal strategies can be difficult to analyze in general, and accordingly, the following two simpler student strategies were considered:

• •

  Majority rule: $\Theta_{n}$ is chosen according to the majority of the observations $Z_{1},\ldots,Z_{n}$.

• •

  $\epsilon$-majority rule: $\Theta_{n}$ is the majority of the last $\epsilon\cdot n$ observations for some $\epsilon\in(0,1)$, with the rough idea being to allow time for the teacher to learn $\Theta$ first.

These student strategies were analyzed together with the following teacher strategies:

• •

  Simple forwarding: The teacher directly forwards its observation at each time step, i.e., $\hat{X}_{i}=Y_{i}$.

• •

  Cumulative teaching: The teacher transmits its best estimate of $\Theta$ at each time step, i.e., $\hat{X}_{i}$ is the majority value among $Y_{1},\ldots,Y_{i}$.

It was demonstrated in [1] that none of these strategies uniformly outperform one an another, and that any combination of them falls short of the $D(1/2\|\max(p,q))$ upper bound (i.e., converse) based on data processing arguments (here and subsequently, $D(p_{1}\|p_{2})$ denotes the relative entropy between Bernoulli distributions with parameters $p_{1}$ an $p_{2}$). The optimal learning rate was left as an open problem, and it was conjectured that at least part of the weakness is in the upper bound, i.e., that one cannot attain a rate of $D(1/2\|\max(p,q))$.

In [2], both simple forwarding and cumulative teaching (i.e., relaying) were considered, along with a block-structured variant that only updates the majority every $\sqrt{n}$ time steps. These strategies were analyzed alongside the optimal maximum-likelihood learning (i.e., decoding) rule. While the learning rates attained again fall short of the $D(1/2\|\max(p,q))$ upper bound, it was shown that one comes within a factor $\frac{3}{4}$ when $p=q$ and $p\to\frac{1}{2}$ (i.e., the high noise setting). It was conjectured in [2] that using a more sophisticated protocol, this constant $\frac{3}{4}$ could be made arbitrarily close to one in this high-noise limit. As hinted above, the motivation for this conjecture was the fact that positive information velocity is known to be attainable; the authors of [2] discuss that for this to be possible, the 1-hop and 2-hop exponents should match in the high-noise limit so that “information propagation does not slow down”.

The study of [1] was inspired by earlier works on social learning [4, 5, 6], and most similar to [7]. Since these are less directly relevant to our work, we refer the reader to [1] for a detailed discussion of the differences.

As we will see shortly, our main result disproves the above-mentioned conjecture of [1], and not only confirms the conjecture of [2] for the regime $p\to\frac{1}{2}$, but also significantly strengthens it by extending it to all $p\in\big{(}0,\frac{1}{2}\big{)}$.

Our first main result is stated as follows.

We achieve this result via a novel block-structured teaching strategy. In contrast with [2], the teacher transmits bits based on a single block at a time, ignoring earlier blocks. The teacher encodes the number of 1s received in the block by sending a sorted sequence (i.e., a string of $1$s followed by a string of $0$s), with the transition point chosen according to a carefully-chosen non-linear function of the number of 1s observed. The student performs maximum-likelihood decoding, and we study the error probability via the Bhattacharyya coefficient. The details are given in Sections II-B and II-C, and in Section II-D we show that the overall computation time required by the teacher and student is linear in $n$.

Comparison to upper bound (converse). If $q=0$, then the optimal learning rate is given by the majority decoder, which achieves a learning rate of [1, 2]

Through data processing inequalities, we have $\mathcal{R}^{*}(p,q)\leq\mathcal{R}^{*}(p,0)=D\big{(}\frac{1}{2}\|p\big{)}$, and an analogous argument yields $\mathcal{R}^{*}(p,q)\leq D\big{(}\frac{1}{2}\|q\big{)}$. We therefore obtain the upper bound

Theorem 1 shows that this bound is tight, disproving the above-mentioned conjecture of [1], and both confirming and strengthening the conjecture of [2].

In the remainder of the section, we only consider the case $p=q$. This is without loss of generality, since in the general case, one can simulate additional noise into the system to make the noise parameters both equal to $\max(p,q)$.

Before describing the protocol, we first need to introduce some statistical tools.

Continuing the study of a single block $W$ defined according to (12), observe that we have the Markov chain

and in accordance with (15), we would like the distributions $P_{W|\Theta=1}$ and $P_{W|\Theta=0}$ to be as ‘far apart’ as possible. We break the error analysis into two parts, analyzing the relations $\Theta\rightarrow\alpha$ and $\alpha\rightarrow W$ separately.

In this section, we argue that it is possible to execute the described protocol with an overall computation time of $\mathcal{O}(n)$ (i.e., no higher than that of simply reading the received bits). This is immediate for the teacher, so we focus our attention on the student.

To implement the maximum likelihood decoder, it suffices to compute the associated log likelihood ratio (LLR) $\log\frac{\mathbb{P}(\vec{Z}=\vec{z}|\Theta=1)}{\mathbb{P}(\vec{Z}=\vec{z}|\Theta=0)}$ given the $n$ received bits $\vec{z}$. In addition, since the $n/k-1$ blocks are independent by construction and memorylessness, the overall LLR is the sum of per-block LLRs. Hence, we only need to show that each of these can be computed in time $\mathcal{O}(k)$.

The only minor difficulty in computing the LLR for a single block is that we need to account for all possible $k+1$ choices of the latent/hidden variable $\alpha\in\big{\{}0,\frac{1}{k},\dotsc,1\big{\}}$: Letting $W$ denote a generic length-$k$ block according to (12), we have

and similarly for $\mathbb{P}(W|\Theta=0)$. In addition, since the channel is memoryless, we have

where $W(i)$ is the $i$-th bit comprising $W$. Naively, we could evaluate (37) and (38) directly, but this would give a per-block complexity of $\mathcal{O}(k^{2})$.

To improve this, we recall that for two values $\alpha_{1},\alpha_{2}\in\big{\{}0,\frac{1}{k},\dotsc,1\big{\}}$, the associated values of $\mathbb{P}(W(i)|\alpha)$ only differ for values of $i$ in between $k\cdot f(\alpha_{1})$ and $k\cdot f(\alpha_{2})$. Therefore, we can initially compute $\mathbb{P}(W|\alpha)$ for $\alpha=0$, and then use it to compute the value for $\alpha=\frac{1}{k}$ by only looking at the first $k\cdot f\big{(}\frac{1}{k}\big{)}$ bits of $W$, and so on for $\alpha\in\big{\{}\frac{2}{k},\frac{3}{k},\dotsc,1\big{\}}$; at each step, we only need to look at the bits affected by incrementing $\alpha$. In this manner, it only takes $\mathcal{O}(k)$ time to compute all $k+1$ values of $\mathbb{P}(W|\alpha)$. In addition, $\mathbb{P}(\alpha|\Theta=1)$ in (37) follows a scaled binomial distribution, whose probability mass function can be pre-computed in $\mathcal{O}(k)$ time (assuming constant-time arithmetic operations). Hence, we obtain an overall per-block computation time of $\mathcal{O}(k)$.

In addition to the low computational overhead, another advantage of our strategy is that it is anytime. Specifically, it can be run without knowledge of $n$, and we can stop the algorithm any time and ask the student for the estimate $\hat{\Theta}_{n}$. Letting $\epsilon_{k,n}$ be the resulting error probability with block size $k$ and total time $n$, it still holds in this scenario that $-\frac{1}{n}\ln\epsilon_{k,n}\rightarrow D(1/2||p)$, as long as $k\rightarrow\infty$ and $n/k\rightarrow\infty$.

We first consider a 1-hop scenario in which a single agent makes repeated observations of the unknown variable $\Theta$ through repeated uses of a binary-input DMC $P$. This is a well-studied problem, and we will summarize some of the results from [10].

We begin with a generalization of the Bhattacharyya coefficient. For a real number $s\in(0,1)$ and two random variables $A,B$ defined on the same finite alphabet $\Omega$, let

where the upper bound of one follows by applying Jensen’s inequality to $\mathbb{E}_{A}\big{[}\big{(}\frac{P_{B}(B)}{P_{A}(A)}\big{)}^{s}\big{]}$. This function can be extended to $s=0$ and $s=1$ by continuity; for instance, $\rho(A,B,0)=\sum_{x\in\Omega}\mathbb{P}(A=x)\mathbbm{1}_{\mathbb{P}(B=x)>0}$. We also note that setting $s=\frac{1}{2}$ recovers the Bhattacharyya coefficient. We write $\rho(A,B,s)$ and $\rho(P_{A},P_{B},s)$ interchangeably. Similarly to (10)–(11), we have the following properties for independent pairs and length-$m$ i.i.d. vectors:

Given the DMC $P$ with inputs $0$ and $1$, we define

and denote its logarithm by²²2See Figure 4 on Page 4 for some examples of how $\mu_{P}(s)$ varies as a function of $s$.

where $P(\cdot|0)$ and $P(\cdot|1)$ are treated as probability distributions on the output alphabet. The first and second derivatives of $\mu_{P}(s)$ for $s\in(0,1)$ are denoted by $\mu^{\prime}_{P}(s)$ and $\mu^{\prime\prime}_{P}(s)$, and once again, the values for the endpoints $s\in\{0,1\}$ are defined with respect to the appropriate limits.

Suppose that the agent makes a single observation of $\Theta\in\{0,1\}$ through $P$, and uses it to estimate $\Theta$. Using the identity $\mathbbm{1}_{\mathbb{P}(B=x)>\mathbb{P}(A=x)}\leq\big{(}\frac{\mathbb{P}(B=x)}{\mathbb{P}(A=x)}\big{)}^{s}$, we find that for any $s\geq 0$, $\rho_{P}(s)$ is an upper bound to the probability of a maximum-likelihood decision rule selecting $B$ when $A$ is true. An analogous property holds for the reverse error event with $1-s$ in place of $s$, and it follows that $\rho_{P}(s)$ is an upper bound to the overall error probability for all $s\in[0,1]$.

In view of the property in (41), if the agent instead makes $n$ independent observations, the upper bound becomes $\rho_{P^{n}}(s)=\rho_{P}(s)^{n}$, implying a learning rate of at least

The following well-known result reveals that this learning rate is optimal upon optimizing over $s\in[0,1]$.

Since the $\sqrt{2n\mu_{P}^{\prime\prime}(s^{*})}$ term is sub-linear in $n$, this immediately gives the following corollary.

We now state the second main result of our paper, giving an achievability result for general binary-input DMCs.

While (46) clearly implies (45), we find the expression (45) easier to work with and prove. Once (45) is proved, (46) follows from the fact that one can choose to flip the inputs of $Q$, which amounts to replacing $\mu_{Q}(s)$ by $\mu_{Q}(1-s)$.⁴⁴4At first this leads to the seemingly different learning rate of $-\min\big{(}\min_{s\in[0,1]}\max(\mu_{P}(s),\mu_{Q}(s)),\min_{s\in[0,1]}\max(\mu_{P}(s),\mu_{Q}(1-s))\big{)}$, but then (46) can be recovered by taking the two $\min_{s\in[0,1]}$ outside the outer minimum (swapping minimization order has no effect), and applying the identity $\max(a,\min(b,c))=\min(\max(a,b),\max(a,c))$ (verified by checking all 6 orderings of $a$, $b$, and $c$).

When the channels $P$ and $Q$ are identical, (45) reduces to the expression in Corollary 1. Since the learning rate cannot be smaller than the 1-hop case (due to a data-processing argument similar to the binary symmetric setting), we conclude that Theorem 46 provides the optimal learning rate in this case. Other scenarios in which Theorem 46 gives the optimal learning rate will be discussed in Section III-D.

Fix an arbitrary value of $\bar{s}\in[0,1]$ and define

To prove (45), it suffices to show that $-\mu_{\max}$ is an achievable learning rate. We assume without loss of generality that $\mu_{\max}<0$, since a learning rate of zero is trivial.

We again adopt the block structure used in Section II, with $k$ denoting the block size. Suppose that in a single block, the teacher receives $\vec{Y}=(Y_{1},Y_{2},\ldots,Y_{k})$. We define the log-likelihood ratio (LLR) as

and let $L_{1}$ (respectively, $L_{0}$) be the distribution of $l(\vec{Y})$ under $\Theta=1$ (respectively, $\Theta=0$).

Upon receiving $\vec{Y}$, the teacher computes $l=l(\vec{Y})$, and sends $g(l)$ bits of $0$ followed by $k-g(l)$ bits of $1$, where $g(l)$ is defined as follows:

Since $1-\bar{s}\geq 0$, $\mu_{\max}<0$, and $\ln\mathbb{P}(L_{0}\geq l)\leq 0$, we have

and similarly,

which implies that $0\leq g(l)\leq k$ for all $l$. It may be necessary to round $g(l)$ to the nearest integer, but similarly to Section II, this does not affect the result, and it is omitted in our analysis.

The main difference in the analysis compared to Section II is establishing the following technical lemma.

We claim that this result implies

To see this, we check the possible cases in the definition of $g(l)$ in (49). If $l\leq 0$, then the left inequality in (53) is trivial, and the right inequality follows by considering two sub-cases: If the $\min(k,\cdot)$ in (49) is attained by $k$, then we apply (51), and otherwise, we apply (52). The case $l>0$ is handled similarly.

From here, the analysis is similar to that of Section II. Observe that we have the Markov chain $\Theta\rightarrow l(\vec{Y})\rightarrow W$, where $W$ denotes the $k$ symbols received by the student in a single block. Since $W$ takes on two different distributions depending on whether $\Theta=1$ or $\Theta=0$, we may also view $W$ as the output of a ‘single-use’ discrete memoryless channel with input $\Theta$ and an output of length $k$. With a slight abuse of notation, we define the quantities $\mu_{W}(s)$ and $\rho_{W}(s)$ according to this channel.

To upper bound $\rho_{W}(s)$, we use the following straightforward generalization of Lemma 1.