TY - GEN
T1 - The price of uncertainty in communication
AU - Braverman, Mark
AU - Juba, Brendan
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/4/4
Y1 - 2016/4/4
N2 - We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a prior distribution that is known to be close to the source distribution, a problem first considered by Juba et al. [5]. This problem generalizes the classical source coding problem in information theory, in which the receiver knows the source distribution exactly, that was first considered in Shannon's work [6]. This uncertain priors coding problem was intended to illuminate aspects of natural language communication, and has applications to adaptive compression schemes. We consider the question of how much longer the messages need to be in order to cope with the uncertainty that the sender and receiver have about the receiver's prior and the source distribution, respectively, as compared to the source coding problem. We obtain lower bounds for one-way communication using uncertain priors that are tight up to low-order terms. Specifically, we consider two variants of the uncertain priors problem. First, we consider the original setting of Juba et al. [5] in which the receiver is required to correctly recover the message with probability 1. We find that in this setting, the overhead of 2 log α + O(1) bits achieved by that scheme when the prior is α-close to the source is optimal up to an additive O(log log α) bits. We also consider a setting introduced in the work of Haramaty and Sudan [3], in which the receiver is permitted to fail to recover the message with some positive probability ϵ. In this setting, we find that the optimal overhead is essentially log α + log 1/ϵ bits by presenting both a variant of the coding scheme of Juba et al. with an overhead of log α+log 1/ϵ+1 bits, and a lower bound that matches up to an additive O(log log α) bits. Our lower bounds are obtained by observing that a worst-case, one-way communication complexity problem can be embedded in the sources and priors that any any uncertain priors coding scheme must address.
AB - We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a prior distribution that is known to be close to the source distribution, a problem first considered by Juba et al. [5]. This problem generalizes the classical source coding problem in information theory, in which the receiver knows the source distribution exactly, that was first considered in Shannon's work [6]. This uncertain priors coding problem was intended to illuminate aspects of natural language communication, and has applications to adaptive compression schemes. We consider the question of how much longer the messages need to be in order to cope with the uncertainty that the sender and receiver have about the receiver's prior and the source distribution, respectively, as compared to the source coding problem. We obtain lower bounds for one-way communication using uncertain priors that are tight up to low-order terms. Specifically, we consider two variants of the uncertain priors problem. First, we consider the original setting of Juba et al. [5] in which the receiver is required to correctly recover the message with probability 1. We find that in this setting, the overhead of 2 log α + O(1) bits achieved by that scheme when the prior is α-close to the source is optimal up to an additive O(log log α) bits. We also consider a setting introduced in the work of Haramaty and Sudan [3], in which the receiver is permitted to fail to recover the message with some positive probability ϵ. In this setting, we find that the optimal overhead is essentially log α + log 1/ϵ bits by presenting both a variant of the coding scheme of Juba et al. with an overhead of log α+log 1/ϵ+1 bits, and a lower bound that matches up to an additive O(log log α) bits. Our lower bounds are obtained by observing that a worst-case, one-way communication complexity problem can be embedded in the sources and priors that any any uncertain priors coding scheme must address.
UR - http://www.scopus.com/inward/record.url?scp=84969834372&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969834372&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2015.7447106
DO - 10.1109/ALLERTON.2015.7447106
M3 - Conference contribution
AN - SCOPUS:84969834372
T3 - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
SP - 924
EP - 927
BT - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
Y2 - 29 September 2015 through 2 October 2015
ER -